public static void dijkstra(Set<Node> graph, Node start, Node end) {
start.setDistance(0);
Set<Node> visited = new HashSet<>();
dijkstraHelper(graph, visited, start, end);
}
public static void dijkstraHelper(Set<Node> unvisited, Set<Node> visited, Node currentNode, Node end) {
if (visited.contains(end)) {
Node prevNode = end;
System.out.println(prevNode);
while (prevNode.getPreviousNode() != null) {
System.out.println(prevNode.getPreviousNode());
prevNode = prevNode.getPreviousNode();
}
return;
}
Map<Node, Integer> neighbours = currentNode.getAdjacentNodes();
neighbours.forEach((node, distance) -> {
if (unvisited.contains(node)) {
int computeDistance = distance + currentNode.getDistance();
if (computeDistance <= node.getDistance()) {
node.setDistance(computeDistance);
node.setPrevNode(currentNode);
}
}
});
unvisited.remove(currentNode);
visited.add(currentNode);
AtomicReference<Node> nextNode = new AtomicReference<>();
neighbours.forEach((node, integer) -> {
if (nextNode.get() == null && unvisited.contains(node)) {
nextNode.set(node);
} else if (unvisited.contains(node) && node.getDistance() < nextNode.get().getDistance()){
nextNode.set(node);
}
});
dijkstraHelper(unvisited, visited, nextNode.get(), end);
}
public static void dijkstra(Set<Node> graph, Node start, Node end) {
start.setDistance(0);
Set<Node> visited = new HashSet<>();
dijkstraHelper(graph, visited, start, end);
}
public static void dijkstraHelper(Set<Node> unvisited, Set<Node> visited, Node currentNode, Node end) {
if (visited.contains(end)) {
Node prevNode = end;
System.out.println(prevNode);
while (prevNode.getPreviousNode() != null) {
System.out.println(prevNode.getPreviousNode());
prevNode = prevNode.getPreviousNode();
}
return;
}
Map<Node, Integer> neighbours = currentNode.getAdjacentNodes();
neighbours.forEach((node, distance) -> {
if (unvisited.contains(node)) {
int computeDistance = distance + currentNode.getDistance();
if (computeDistance <= node.getDistance()) {
node.setDistance(computeDistance);
node.setPrevNode(currentNode);
}
}
});
unvisited.remove(currentNode);
visited.add(currentNode);
AtomicReference<Node> nextNode = new AtomicReference<>();
neighbours.forEach((node, integer) -> {
if (nextNode.get() == null && unvisited.contains(node)) {
nextNode.set(node);
} else if (unvisited.contains(node) && node.getDistance() < nextNode.get().getDistance()){
nextNode.set(node);
}
});
dijkstraHelper(unvisited, visited, nextNode.get(), end);
}