Created
September 6, 2018 17:50
-
-
Save bbottema/b0105cd40bfb808f456d21353e97c2a6 to your computer and use it in GitHub Desktop.
Minimal Dijkstra Java (uses Lombok)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
@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