fork(25) 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. /**
  8.  * 2 - 4
  9.  * / \    \
  10.  * /   5---- 7
  11.  * 1          /
  12.  * \   8    /
  13.  * \ /  \ /
  14.  * 3 -- 6
  15.  * <p>
  16.  * A-B-C-E-F
  17.  * |     |
  18.  * D------
  19.  *
  20.  */
  21. class FindAllShortestPathsInUnweightedGraph {
  22.     private static Object mock = new Object();
  23.  
  24.  public static List<List<String>> findAllShortestPaths(Graph graph, String from, String to) {
  25.         LinkedHashMap<Node, Object> queue = new LinkedHashMap<>();
  26.         Set<Node> visited = new HashSet<>();
  27.         queue.put(new Node(from, 0), mock);
  28.  
  29.         Node nodeTo = null;
  30.         while (queue.keySet().size() > 0) {
  31.             Node next = queue.keySet().iterator().next();
  32.  
  33.             if (next.key.equals(to)) {
  34.                 // base case: we found the end node and processed all edges to it -> we are done
  35.                 nodeTo = next;
  36.                 break;
  37.             }
  38.  
  39.             for (Node n : graph.adjacents(next.key)) {
  40.                 if (!visited.contains(n)) {
  41.                     if (queue.get(n) == null) {
  42.                         queue.put(n, mock);
  43.                     }
  44.                     n.addParent(next);
  45.                 }
  46.             }
  47.  
  48.             // removing the node from queue
  49.             queue.remove(next);
  50.             visited.add(next);
  51.         }
  52.         if (nodeTo == null) {
  53.             return Collections.emptyList();
  54.         }
  55.  
  56.         // Now performing the dfs from target node to gather all paths
  57.         List<List<String>> result = new ArrayList<>();
  58.         dfs(nodeTo, result, new LinkedList<>());
  59.  
  60.         return result;
  61.     }
  62.  
  63.     private static void dfs(Node n, List<List<String>> result, LinkedList<String> path) {
  64.         path.addFirst(n.key);
  65.         if (n.getParents().size() == 0) {
  66.             // base case: we came to target vertex
  67.             result.add(new ArrayList<>(path));
  68.         }
  69.         for (Node p : n.getParents()) {
  70.             dfs(p, result, path);
  71.         }
  72.         // do not forget to remove the processed element from path
  73.         path.removeFirst();
  74.     }
  75.  
  76.     private static class Graph {
  77.         Map<String, Set<Node>> adjacencyList = new HashMap<>();
  78.  
  79.         public void add(String from, String to) {
  80.             addEdge(to, from);
  81.             addEdge(from, to);
  82.         }
  83.  
  84.         private void addEdge(String from, String to) {
  85.             Set<Node> list = adjacencyList.get(from);
  86.  
  87.             if (list == null) {
  88.                 list = new LinkedHashSet<>();
  89.                 adjacencyList.put(from, list);
  90.             }
  91.             list.add(Node.get(to));
  92.         }
  93.  
  94.         public Set<Node> adjacents(String v) {
  95.             Set<Node> nodes = adjacencyList.get(v);
  96.             return nodes == null ? Collections.emptySet() : nodes;
  97.         }
  98.     }
  99.  
  100.     private static class Node {
  101.         List<Node> parents = new ArrayList<>();
  102.         private static Map<String, Node> map = new HashMap<>();
  103.         private final String key;
  104.         int level = -1;
  105.  
  106.         public static Node get(String str) {
  107.             // inner interning of nodes
  108.             Node res = map.get(str);
  109.             if (res == null) {
  110.                 res = new Node(str, -1);
  111.                 map.put(str, res);
  112.             }
  113.             return res;
  114.         }
  115.  
  116.         private Node(String str, int level) {
  117.             key = str;
  118.             this.level = level;
  119.         }
  120.  
  121.         public void addParent(Node n) {
  122.             // forbidding the parent it its level is equal to ours
  123.             if (n.level == level) {
  124.                 return;
  125.             }
  126.             parents.add(n);
  127.  
  128.             level = n.level + 1;
  129.         }
  130.  
  131.         public List<Node> getParents() {
  132.             return parents;
  133.         }
  134.  
  135.         public boolean equals(Object n) {
  136.             return key.equals(((Node) n).key);
  137.         }
  138.  
  139.         public int hashCode() {
  140.             return key.hashCode();
  141.         }
  142.  
  143.         @Override
  144.         public String toString() {
  145.             return key;
  146.         }
  147.     }
  148.  
  149.     public static void main(String[] args) {
  150.         Graph graph = new Graph();
  151.  
  152.         graph.add("1", "2");
  153.         graph.add("1", "3");
  154.         graph.add("2", "4");
  155.         graph.add("2", "5");
  156.         graph.add("4", "7");
  157.         graph.add("5", "7");
  158.         graph.add("3", "6");
  159.         graph.add("3", "8");
  160.         graph.add("8", "6");
  161.         graph.add("6", "7");
  162.         graph.add("7", "5");
  163.  
  164.         System.out.println(findAllShortestPaths(graph, "1", "7"));
  165.  
  166.         graph = new Graph();
  167.  
  168.         graph.add("A", "B");
  169.         graph.add("B", "D");
  170.         graph.add("B", "C");
  171.         graph.add("C", "E");
  172.         graph.add("E", "F");
  173.         graph.add("F", "D");
  174.  
  175.         System.out.println(findAllShortestPaths(graph, "A", "E"));
  176.     }
  177. }
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]]
[[A, B, C, E]]
https://ideone.com/UluCBb
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!