/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/**
* 2 - 4
* / \ \
* / 5---- 7
* 1 /
* \ 8 /
* \ / \ /
* 3 -- 6
* <p>
* A-B-C-E-F
* | |
* D------
*
*/
class FindAllShortestPathsInUnweightedGraph {
public static List
<List
<String
>> findAllShortestPaths
(Graph graph,
String from,
String to
) { LinkedHashMap<Node, Object> queue = new LinkedHashMap<>();
Set<Node> visited = new HashSet<>();
queue.put(new Node(from, 0), mock);
Node nodeTo = null;
while (queue.keySet().size() > 0) {
Node next = queue.keySet().iterator().next();
if (next.key.equals(to)) {
// base case: we found the end node and processed all edges to it -> we are done
nodeTo = next;
break;
}
for (Node n : graph.adjacents(next.key)) {
if (!visited.contains(n)) {
if (queue.get(n) == null) {
queue.put(n, mock);
}
n.addParent(next);
}
}
// removing the node from queue
queue.remove(next);
visited.add(next);
}
if (nodeTo == null) {
}
// Now performing the dfs from target node to gather all paths
List<List<String>> result = new ArrayList<>();
dfs(nodeTo, result, new LinkedList<>());
return result;
}
private static void dfs(Node n, List<List<String>> result, LinkedList<String> path) {
path.addFirst(n.key);
if (n.getParents().size() == 0) {
// base case: we came to target vertex
result.add(new ArrayList<>(path));
}
for (Node p : n.getParents()) {
dfs(p, result, path);
}
// do not forget to remove the processed element from path
path.removeFirst();
}
private static class Graph {
Map
<String, Set
<Node
>> adjacencyList
= new HashMap
<>();
addEdge(to, from);
addEdge(from, to);
}
Set<Node> list = adjacencyList.get(from);
if (list == null) {
list = new LinkedHashSet<>();
adjacencyList.put(from, list);
}
list.add(Node.get(to));
}
public Set
<Node
> adjacents
(String v
) { Set<Node> nodes = adjacencyList.get(v);
}
}
private static class Node {
List<Node> parents = new ArrayList<>();
private static Map
<String, Node
> map
= new HashMap
<>(); int level = -1;
public static Node get
(String str
) { // inner interning of nodes
Node res = map.get(str);
if (res == null) {
res = new Node(str, -1);
map.put(str, res);
}
return res;
}
private Node
(String str,
int level
) { key = str;
this.level = level;
}
public void addParent(Node n) {
// forbidding the parent it its level is equal to ours
if (n.level == level) {
return;
}
parents.add(n);
level = n.level + 1;
}
public List<Node> getParents() {
return parents;
}
public boolean equals
(Object n
) { return key.equals(((Node) n).key);
}
public int hashCode() {
return key.hashCode();
}
@Override
return key;
}
}
public static void main
(String[] args
) { Graph graph = new Graph();
graph.add("1", "2");
graph.add("1", "3");
graph.add("2", "4");
graph.add("2", "5");
graph.add("4", "7");
graph.add("5", "7");
graph.add("3", "6");
graph.add("3", "8");
graph.add("8", "6");
graph.add("6", "7");
graph.add("7", "5");
System.
out.
println(findAllShortestPaths
(graph,
"1",
"7"));
graph = new Graph();
graph.add("A", "B");
graph.add("B", "D");
graph.add("B", "C");
graph.add("C", "E");
graph.add("E", "F");
graph.add("F", "D");
System.
out.
println(findAllShortestPaths
(graph,
"A",
"E")); }
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKioKICogMiAtIDQKICogLyBcICAgIFwKICogLyAgIDUtLS0tIDcKICogMSAgICAgICAgICAvCiAqIFwgICA4ICAgIC8KICogXCAvICBcIC8KICogMyAtLSA2CiAqIDxwPgogKiBBLUItQy1FLUYKICogfCAgICAgfAogKiBELS0tLS0tCiAqCiAqLwpjbGFzcyBGaW5kQWxsU2hvcnRlc3RQYXRoc0luVW53ZWlnaHRlZEdyYXBoIHsKICAgIHByaXZhdGUgc3RhdGljIE9iamVjdCBtb2NrID0gbmV3IE9iamVjdCgpOwoKIHB1YmxpYyBzdGF0aWMgTGlzdDxMaXN0PFN0cmluZz4+IGZpbmRBbGxTaG9ydGVzdFBhdGhzKEdyYXBoIGdyYXBoLCBTdHJpbmcgZnJvbSwgU3RyaW5nIHRvKSB7CiAgICAgICAgTGlua2VkSGFzaE1hcDxOb2RlLCBPYmplY3Q+IHF1ZXVlID0gbmV3IExpbmtlZEhhc2hNYXA8PigpOwogICAgICAgIFNldDxOb2RlPiB2aXNpdGVkID0gbmV3IEhhc2hTZXQ8PigpOwogICAgICAgIHF1ZXVlLnB1dChuZXcgTm9kZShmcm9tLCAwKSwgbW9jayk7CgogICAgICAgIE5vZGUgbm9kZVRvID0gbnVsbDsKICAgICAgICB3aGlsZSAocXVldWUua2V5U2V0KCkuc2l6ZSgpID4gMCkgewogICAgICAgICAgICBOb2RlIG5leHQgPSBxdWV1ZS5rZXlTZXQoKS5pdGVyYXRvcigpLm5leHQoKTsKCiAgICAgICAgICAgIGlmIChuZXh0LmtleS5lcXVhbHModG8pKSB7CiAgICAgICAgICAgICAgICAvLyBiYXNlIGNhc2U6IHdlIGZvdW5kIHRoZSBlbmQgbm9kZSBhbmQgcHJvY2Vzc2VkIGFsbCBlZGdlcyB0byBpdCAtPiB3ZSBhcmUgZG9uZQogICAgICAgICAgICAgICAgbm9kZVRvID0gbmV4dDsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CgogICAgICAgICAgICBmb3IgKE5vZGUgbiA6IGdyYXBoLmFkamFjZW50cyhuZXh0LmtleSkpIHsKICAgICAgICAgICAgICAgIGlmICghdmlzaXRlZC5jb250YWlucyhuKSkgewogICAgICAgICAgICAgICAgICAgIGlmIChxdWV1ZS5nZXQobikgPT0gbnVsbCkgewogICAgICAgICAgICAgICAgICAgICAgICBxdWV1ZS5wdXQobiwgbW9jayk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIG4uYWRkUGFyZW50KG5leHQpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICAvLyByZW1vdmluZyB0aGUgbm9kZSBmcm9tIHF1ZXVlCiAgICAgICAgICAgIHF1ZXVlLnJlbW92ZShuZXh0KTsKICAgICAgICAgICAgdmlzaXRlZC5hZGQobmV4dCk7CiAgICAgICAgfQogICAgICAgIGlmIChub2RlVG8gPT0gbnVsbCkgewogICAgICAgICAgICByZXR1cm4gQ29sbGVjdGlvbnMuZW1wdHlMaXN0KCk7CiAgICAgICAgfQoKICAgICAgICAvLyBOb3cgcGVyZm9ybWluZyB0aGUgZGZzIGZyb20gdGFyZ2V0IG5vZGUgdG8gZ2F0aGVyIGFsbCBwYXRocwogICAgICAgIExpc3Q8TGlzdDxTdHJpbmc+PiByZXN1bHQgPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICBkZnMobm9kZVRvLCByZXN1bHQsIG5ldyBMaW5rZWRMaXN0PD4oKSk7CgogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBkZnMoTm9kZSBuLCBMaXN0PExpc3Q8U3RyaW5nPj4gcmVzdWx0LCBMaW5rZWRMaXN0PFN0cmluZz4gcGF0aCkgewogICAgICAgIHBhdGguYWRkRmlyc3Qobi5rZXkpOwogICAgICAgIGlmIChuLmdldFBhcmVudHMoKS5zaXplKCkgPT0gMCkgewogICAgICAgICAgICAvLyBiYXNlIGNhc2U6IHdlIGNhbWUgdG8gdGFyZ2V0IHZlcnRleAogICAgICAgICAgICByZXN1bHQuYWRkKG5ldyBBcnJheUxpc3Q8PihwYXRoKSk7CiAgICAgICAgfQogICAgICAgIGZvciAoTm9kZSBwIDogbi5nZXRQYXJlbnRzKCkpIHsKICAgICAgICAgICAgZGZzKHAsIHJlc3VsdCwgcGF0aCk7CiAgICAgICAgfQogICAgICAgIC8vIGRvIG5vdCBmb3JnZXQgdG8gcmVtb3ZlIHRoZSBwcm9jZXNzZWQgZWxlbWVudCBmcm9tIHBhdGgKICAgICAgICBwYXRoLnJlbW92ZUZpcnN0KCk7CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgY2xhc3MgR3JhcGggewogICAgICAgIE1hcDxTdHJpbmcsIFNldDxOb2RlPj4gYWRqYWNlbmN5TGlzdCA9IG5ldyBIYXNoTWFwPD4oKTsKCiAgICAgICAgcHVibGljIHZvaWQgYWRkKFN0cmluZyBmcm9tLCBTdHJpbmcgdG8pIHsKICAgICAgICAgICAgYWRkRWRnZSh0bywgZnJvbSk7CiAgICAgICAgICAgIGFkZEVkZ2UoZnJvbSwgdG8pOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSB2b2lkIGFkZEVkZ2UoU3RyaW5nIGZyb20sIFN0cmluZyB0bykgewogICAgICAgICAgICBTZXQ8Tm9kZT4gbGlzdCA9IGFkamFjZW5jeUxpc3QuZ2V0KGZyb20pOwoKICAgICAgICAgICAgaWYgKGxpc3QgPT0gbnVsbCkgewogICAgICAgICAgICAgICAgbGlzdCA9IG5ldyBMaW5rZWRIYXNoU2V0PD4oKTsKICAgICAgICAgICAgICAgIGFkamFjZW5jeUxpc3QucHV0KGZyb20sIGxpc3QpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGxpc3QuYWRkKE5vZGUuZ2V0KHRvKSk7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgU2V0PE5vZGU+IGFkamFjZW50cyhTdHJpbmcgdikgewogICAgICAgICAgICBTZXQ8Tm9kZT4gbm9kZXMgPSBhZGphY2VuY3lMaXN0LmdldCh2KTsKICAgICAgICAgICAgcmV0dXJuIG5vZGVzID09IG51bGwgPyBDb2xsZWN0aW9ucy5lbXB0eVNldCgpIDogbm9kZXM7CiAgICAgICAgfQogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIGNsYXNzIE5vZGUgewogICAgICAgIExpc3Q8Tm9kZT4gcGFyZW50cyA9IG5ldyBBcnJheUxpc3Q8PigpOwogICAgICAgIHByaXZhdGUgc3RhdGljIE1hcDxTdHJpbmcsIE5vZGU+IG1hcCA9IG5ldyBIYXNoTWFwPD4oKTsKICAgICAgICBwcml2YXRlIGZpbmFsIFN0cmluZyBrZXk7CiAgICAgICAgaW50IGxldmVsID0gLTE7CgogICAgICAgIHB1YmxpYyBzdGF0aWMgTm9kZSBnZXQoU3RyaW5nIHN0cikgewogICAgICAgICAgICAvLyBpbm5lciBpbnRlcm5pbmcgb2Ygbm9kZXMKICAgICAgICAgICAgTm9kZSByZXMgPSBtYXAuZ2V0KHN0cik7CiAgICAgICAgICAgIGlmIChyZXMgPT0gbnVsbCkgewogICAgICAgICAgICAgICAgcmVzID0gbmV3IE5vZGUoc3RyLCAtMSk7CiAgICAgICAgICAgICAgICBtYXAucHV0KHN0ciwgcmVzKTsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gcmVzOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBOb2RlKFN0cmluZyBzdHIsIGludCBsZXZlbCkgewogICAgICAgICAgICBrZXkgPSBzdHI7CiAgICAgICAgICAgIHRoaXMubGV2ZWwgPSBsZXZlbDsKICAgICAgICB9CgogICAgICAgIHB1YmxpYyB2b2lkIGFkZFBhcmVudChOb2RlIG4pIHsKICAgICAgICAgICAgLy8gZm9yYmlkZGluZyB0aGUgcGFyZW50IGl0IGl0cyBsZXZlbCBpcyBlcXVhbCB0byBvdXJzCiAgICAgICAgICAgIGlmIChuLmxldmVsID09IGxldmVsKSB7CiAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcGFyZW50cy5hZGQobik7CgogICAgICAgICAgICBsZXZlbCA9IG4ubGV2ZWwgKyAxOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIExpc3Q8Tm9kZT4gZ2V0UGFyZW50cygpIHsKICAgICAgICAgICAgcmV0dXJuIHBhcmVudHM7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgYm9vbGVhbiBlcXVhbHMoT2JqZWN0IG4pIHsKICAgICAgICAgICAgcmV0dXJuIGtleS5lcXVhbHMoKChOb2RlKSBuKS5rZXkpOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIGludCBoYXNoQ29kZSgpIHsKICAgICAgICAgICAgcmV0dXJuIGtleS5oYXNoQ29kZSgpOwogICAgICAgIH0KCiAgICAgICAgQE92ZXJyaWRlCiAgICAgICAgcHVibGljIFN0cmluZyB0b1N0cmluZygpIHsKICAgICAgICAgICAgcmV0dXJuIGtleTsKICAgICAgICB9CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIEdyYXBoIGdyYXBoID0gbmV3IEdyYXBoKCk7CgogICAgICAgIGdyYXBoLmFkZCgiMSIsICIyIik7CiAgICAgICAgZ3JhcGguYWRkKCIxIiwgIjMiKTsKICAgICAgICBncmFwaC5hZGQoIjIiLCAiNCIpOwogICAgICAgIGdyYXBoLmFkZCgiMiIsICI1Iik7CiAgICAgICAgZ3JhcGguYWRkKCI0IiwgIjciKTsKICAgICAgICBncmFwaC5hZGQoIjUiLCAiNyIpOwogICAgICAgIGdyYXBoLmFkZCgiMyIsICI2Iik7CiAgICAgICAgZ3JhcGguYWRkKCIzIiwgIjgiKTsKICAgICAgICBncmFwaC5hZGQoIjgiLCAiNiIpOwogICAgICAgIGdyYXBoLmFkZCgiNiIsICI3Iik7CiAgICAgICAgZ3JhcGguYWRkKCI3IiwgIjUiKTsKCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKGZpbmRBbGxTaG9ydGVzdFBhdGhzKGdyYXBoLCAiMSIsICI3IikpOwoKICAgICAgICBncmFwaCA9IG5ldyBHcmFwaCgpOwoKICAgICAgICBncmFwaC5hZGQoIkEiLCAiQiIpOwogICAgICAgIGdyYXBoLmFkZCgiQiIsICJEIik7CiAgICAgICAgZ3JhcGguYWRkKCJCIiwgIkMiKTsKICAgICAgICBncmFwaC5hZGQoIkMiLCAiRSIpOwogICAgICAgIGdyYXBoLmFkZCgiRSIsICJGIik7CiAgICAgICAgZ3JhcGguYWRkKCJGIiwgIkQiKTsKCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKGZpbmRBbGxTaG9ydGVzdFBhdGhzKGdyYXBoLCAiQSIsICJFIikpOwogICAgfQp9