fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static void findShortestPaths(int n, int[][] edges) {
  6.         List<List<Integer>> graph = new ArrayList<>();
  7.         for (int i = 0; i <= n; i++) {
  8.             graph.add(new ArrayList<>());
  9.         }
  10.  
  11.         for (int[] edge : edges) {
  12.             int u = edge[0], v = edge[1];
  13.             graph.get(u).add(v);
  14.             graph.get(v).add(u);
  15.         }
  16.  
  17.         Queue<Integer> queue = new LinkedList<>();
  18.         int[] level = new int[n + 1];
  19.         int[] ways = new int[n + 1];
  20.         boolean[] visited = new boolean[n + 1];
  21.  
  22.         Arrays.fill(level, -1);
  23.  
  24.         queue.offer(1);
  25.         visited[1] = true;
  26.         level[1] = 0;
  27.         ways[1] = 1;
  28.  
  29.         while (!queue.isEmpty()) {
  30.             int node = queue.poll();
  31.  
  32.             for (int neighbor : graph.get(node)) {
  33.                 if (!visited[neighbor]) {
  34.                     queue.offer(neighbor);
  35.                     visited[neighbor] = true;
  36.                     level[neighbor] = level[node] + 1;
  37.                     ways[neighbor] = ways[node];
  38.                 } else if (level[node] + 1 == level[neighbor]) {
  39.                     ways[neighbor] += ways[node];
  40.                 }
  41.             }
  42.         }
  43.  
  44.         for (int i = 1; i <= n; i++) {
  45.             System.out.println("Node: " + i + ", Shortest Path Count: " + ways[i]);
  46.         }
  47.     }
  48.  
  49.     public static void main(String[] args) {
  50.         int n = 6;
  51.         int[][] edges = {
  52.             {1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}
  53.         };
  54.  
  55.         findShortestPaths(n, edges);
  56.     }
  57. }
  58.  
Success #stdin #stdout 0.16s 57556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Node: 1, Shortest Path Count: 1
Node: 2, Shortest Path Count: 1
Node: 3, Shortest Path Count: 1
Node: 4, Shortest Path Count: 2
Node: 5, Shortest Path Count: 2
Node: 6, Shortest Path Count: 2
https://ideone.com/UTXzzp
language:
Java (HotSpot 12)
created:
281 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!