fork(5) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. /**
  9.  *     
  10.  *     2 - 4
  11.  *    / \    \
  12.  *   /   5---- 7
  13.  * 1          /
  14.  *  \   8    /
  15.  *   \ /  \ /
  16.  *    3 -- 6
  17.  * 
  18.  */
  19. class FindAllShortestPathsInUnweightedGraph {
  20.     private static Object mock = new Object();
  21.     public static List<List<String>> findAllShortestPaths(Graph graph, String from, String to) {
  22.         LinkedHashMap<Node, Object> queue = new LinkedHashMap<>();
  23.         Set<Node> visited = new HashSet<>();
  24.         queue.put(new Node(from), mock);
  25.  
  26.         Node nodeTo = null;
  27.         while (queue.keySet().size() > 0) {
  28.             Node next = queue.keySet().iterator().next();
  29.  
  30.             if (next.key.equals(to)) {
  31.                 // base case: we found the end node and processed all edges to it -> we are done
  32.                 nodeTo = next;
  33.                 break;
  34.             }
  35.  
  36.             for (Node n: graph.adjacents(next.key)) {
  37.                 if (!visited.contains(n)) {
  38.                     if (queue.get(n) == null) {
  39.                         queue.put(n, mock);
  40.                     }
  41.                     n.addParent(next);
  42.                 }
  43.             }
  44.  
  45.             // removing the node from queue
  46.             queue.remove(next);
  47.             visited.add(next);
  48.         }
  49.         if (nodeTo == null) {
  50.             throw new IllegalStateException();
  51.         }
  52.  
  53.         // Now performing the dfs from target node to gather all paths
  54.         List<List<String>> result = new ArrayList<>();
  55.         dfs(nodeTo, result, new LinkedList<>());
  56.  
  57.         return result;
  58.     }
  59.  
  60.     private static void dfs(Node n, List<List<String>> result, LinkedList<String> path) {
  61.         path.addFirst(n.key);
  62.         if (n.getParents().size() == 0) {
  63.             // base case: we came to target vertex
  64.             result.add(new ArrayList<>(path));
  65.         }
  66.         for (Node p: n.getParents()) {
  67.             dfs(p, result, path);
  68.         }
  69.         // do not forget to remove the processed element from path
  70.         path.removeFirst();
  71.     }
  72.  
  73.     private static class Graph {
  74.         Map<String, Set<Node>> adjacencyList = new HashMap<>();
  75.  
  76.         public void add(String from, String to) {
  77.             addEdge(to, from);
  78.             addEdge(from, to);
  79.         }
  80.  
  81.         private void addEdge(String from, String to) {
  82.             Set<Node> list = adjacencyList.get(from);
  83.  
  84.             if (list == null) {
  85.                 list = new LinkedHashSet<>();
  86.                 adjacencyList.put(from, list);
  87.             }
  88.             list.add(Node.get(to));
  89.         }
  90.  
  91.         public Set<Node> adjacents(String v) {
  92.             return adjacencyList.get(v);
  93.         }
  94.  
  95.     }
  96.  
  97.     private static class Node {
  98.         Set<Node> parents = new LinkedHashSet<>();
  99.         private static Map<String, Node> map = new HashMap<>();
  100.         private final String key;
  101.  
  102.         public static Node get(String str) {
  103.             // inner interning of nodes
  104.             Node res = map.get(str);
  105.             if (res == null) {
  106.                 res = new Node(str);
  107.                 map.put(str, res);
  108.             }
  109.             return res;
  110.         }
  111.         private Node(String str) {
  112.             key = str;
  113.         }
  114.  
  115.         public void addParent(Node n) {
  116.             parents.add(n);
  117.         }
  118.         public Set<Node> getParents() {
  119.             return parents;
  120.         }
  121.  
  122.         public boolean equals(Object n) {
  123.             return key.equals(((Node)n).key);
  124.         }
  125.         public int hashCode() {
  126.             return key.hashCode();
  127.         }
  128.  
  129.         @Override
  130.         public String toString() {
  131.             return key;
  132.         }
  133.     }
  134.  
  135.     public static void main(String[] args) {
  136.         Graph graph = new Graph();
  137.  
  138.         graph.add("1", "2");
  139.         graph.add("1", "3");
  140.         graph.add("2", "4");
  141.         graph.add("2", "5");
  142.         graph.add("4", "7");
  143.         graph.add("5", "7");
  144.         graph.add("3", "8");
  145.         graph.add("3", "6");
  146.         graph.add("8", "6");
  147.         graph.add("6", "7");
  148.         graph.add("7", "5");
  149.  
  150.         System.out.println(findAllShortestPaths(graph, "1", "7"));
  151.     }
  152. }
  153.  
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[1, 2, 4, 7], [1, 2, 5, 7], [1, 3, 6, 7], [1, 3, 8, 6, 7]]
https://ideone.com/2IUfcd
language:
Java (HotSpot 12)
created:
9 years 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!