Skip to content

Instantly share code, notes, and snippets.

@bbottema
Created September 6, 2018 17:50
Show Gist options
  • Save bbottema/b0105cd40bfb808f456d21353e97c2a6 to your computer and use it in GitHub Desktop.
Save bbottema/b0105cd40bfb808f456d21353e97c2a6 to your computer and use it in GitHub Desktop.
Minimal Dijkstra Java (uses Lombok)
// cleaned up generics version of Baeldung's Dijkstra (https://www.baeldung.com/java-dijkstra)
public class Dijkstra {
public static <T> void findShortestPathToAllOtherNodes(Node<T> startingPoint) {
startingPoint.setCost(0);
Set<Node<T>> settledNodes = new HashSet<>();
Set<Node<T>> unsettledNodes = new HashSet<>();
unsettledNodes.add(startingPoint);
while (unsettledNodes.size() != 0) {
Node<T> currentNode = getLowestDistanceNode(unsettledNodes);
unsettledNodes.remove(currentNode);
for (Entry<Node<T>, Integer> adjacencyPair : currentNode.getToNodes().entrySet()) {
Node<T> adjacentNode = adjacencyPair.getKey();
if (!settledNodes.contains(adjacentNode)) {
Integer edgeWeight = adjacencyPair.getValue();
calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
unsettledNodes.add(adjacentNode);
}
}
settledNodes.add(currentNode);
}
}
private static <T> void calculateMinimumDistance(Node<T> evaluationNode, Integer edgeWeigh, Node<T> sourceNode) {
if (sourceNode.getCost() + edgeWeigh < evaluationNode.getCost()) {
evaluationNode.setCost(sourceNode.getCost() + edgeWeigh);
LinkedList<Node<T>> shortestPath = new LinkedList<>(sourceNode.getLeastExpensivePath());
shortestPath.add(sourceNode);
evaluationNode.setLeastExpensivePath(shortestPath);
}
}
private static <T> Node<T> getLowestDistanceNode(Set<Node<T>> unsettledNodes) {
Node<T> lowestDistanceNode = null;
int lowestDistance = Integer.MAX_VALUE;
for (Node<T> node : unsettledNodes) {
if (node.getCost() < lowestDistance) {
lowestDistance = node.getCost();
lowestDistanceNode = node;
}
}
return lowestDistanceNode;
}
}
@Data
@EqualsAndHashCode(onlyExplicitlyIncluded = true)
@ToString(onlyExplicitlyIncluded = true)
public class Node<T> {
@Nonnull
@EqualsAndHashCode.Include
@ToString.Include
private T type;
private LinkedList<Node<T>> leastExpensivePath = new LinkedList<>();
private Integer cost = Integer.MAX_VALUE;
private Map<Node<T>, Integer> toNodes = new HashMap<>();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment