Dijkstra’s algorithm to find the shortest path7 min read
Let’s imagine you and your best friend live quite far apart, you haven’t seen him for a while, your best friend is organizing a party at his house and you’re excited to be a part of this. The problem is while commuting to your friend’s house, you start to realize that there are multiple routes you can go to reach the destination, and each of the possible routes is likely to have different distances, so which path should you choose? For the most part, we may choose a route that is the shortest and the communication time is minimal. And in this article, we are going to learn about Dijkstra’s algorithm – the algorithm to find the shortest path between 2 vertices, in our example, it’s the shortest path between your house and your friend’s house.
Before moving on to the actual detail of the algorithm, we need to familiarize ourselves with some related terms, such as a graph – which consists of a collection of vertices (nodes), and the path between any two vertices is called an edge. In our example, each location is represented as a node, and there are potentially many possible nodes and edges between these two.
There are many variants of Dijkstra’s algorithm, but in this article, we are interested in the traditional one, which is the algorithm to find the shortest path between a node to every other node in the graph. For example, the algorithm not only finds the shortest path between node A (your house) to node B (your friend’s house) but also from node A to other nodes such as C (the gas station), D (the grocery store), etc…that are existed in our graph. Let’s move to the detailed steps of the algorithm on how to find the shortest path between the origin node (node A) to the destination node (node B):
- Step 1: Mark all nodes as unvisited. Create a set of all the unvisited nodes called it
unvistedSet - Step 2: Assign to every node the tentative distance value, and set the distance value for the initial vertex to zero, and to infinity for all other vertices in the graph.
- Step 3: For the current node, find out all the unvisited neighbors of it and calculate the tentative distance value of unvisited neighbors through the current node, compare the newly calculated tentative distance to the current assigned value, and assign the smaller one. For example, if the current node A has a distance of 5 and the edge connecting with neighbor B has a length of 2, then the distance to B through A will be 7. If B was marked previously greater than 7, then the distance to B will be replaced with 7. Otherwise, the current value will be kept.
- Step 4: When we’re done exploring all unvisited neighbors of the current node, then we will mark the current node as
visitedand remove it from theunvisitedSet, the visited node would never be visited again. - Step 5: Then select the unvisited node that is marked with the smallest tentative distance, and set it as the current node, then go back to step 3.
- Step 6: If the destination node has been marked as visited or the smallest tentative distance among nodes in the
unvisitedSetis infinity (meaning there is no connection between the initial node and remaining unvisited nodes), then stop, and the algorithm has finished.
Now we are ready to code it up, first, we need to define the Node as well as the graph data structure that will hold nodes as well as edges, there are different ways to label the graph, but in our case, we will go with the adjacent list to present nodes and their connections to other nodes in the graph.
public class Node {
public Node(String label) {
this.label = label;
}
private final String label;
private final Map<Node, Integer> adjacentNodes = new HashMap<>();
private int distance;
private Node prev;
// getters and setters
}Then, we define a graph that will contain a set of nodes:
public record Graph(Set<Node> nodes) {
public Graph() {
this(new HashSet<>());
}
public void addNode(Node node) {
this.nodes.add(node);
}
public void addNode(List<Node> node) {
this.nodes.addAll(node);
}
}We now have both node and graph data structure, that’s enough for us to start implementing Dijkstra’s algorithm, the calculateShortestPath method will take a graph and a source node, it then calculates the shortest path between the source node to every other node in the graph:
public void calculateShortestPath(Graph graph, Node source) {
Set<Node> unsettledNodes = new HashSet<>();
Set<Node> settledNodes = new HashSet<>();
for(final Node node : graph.nodes()) {
node.setDistance(Integer.MAX_VALUE);
}
source.setDistance(0);
unsettledNodes.add(source);
while (!unsettledNodes.isEmpty()) {
Node node = getNearestNode(unsettledNodes);
unsettledNodes.remove(node);
settledNodes.add(node);
findMinNeighborDistance(unsettledNodes, settledNodes, node);
}
}
private void findMinNeighborDistance(Set<Node> unsettledNodes, Set<Node> settledNodes, Node node){
if (node == null) return;
Map<Node, Integer> adjacentNodes = node.getAdjacentNodes();
for(final Map.Entry<Node, Integer> entry : adjacentNodes.entrySet()) {
Node neighbor = entry.getKey();
int distance = entry.getValue();
int sourceDistance = node.getDistance();
if (!settledNodes.contains(neighbor)) {
if (sourceDistance + distance < neighbor.getDistance()) {
neighbor.setDistance(sourceDistance + distance);
neighbor.setPrev(node);
unsettledNodes.add(neighbor);
}
}
}
}Let’s break down what has happened in this piece of code:
- We initially set the distance to every node in the graph to infinity.
- The distance from the source node to itself is 0, hence we set the 0 distance for it.
- We have 2 sets of nodes,
unsettleNodescontains nodes that the node whose neighbors haven’t been visited, once all neighbors of a node are visited the node will be moved fromunsettledNodesto thesettledNodes. - While the
unsettledNodesis not empty, inside the loop, we take the node that has the nearest distance to the current node, in the first try, the node will be our source node. Note that in this case we also can use a priority queue for theunsettledNodes. - In the
findMinNeighborDistance, we basically check every neighbor node for the current node and update the distance value if necessary. In our case, we first check the neighbor node is not yet settled, and then the distance from the source plus the distance between the current node with the neighbor is less than the current neighbor distance, if it does, we reassign the value for the neighbor distance and add the neighbor to the set of unsettled nodes.
Finally, we create a test class that will check the code that we’ve just created, we populate the test with some initial setups:
public class DijkstraShortestPathTest {
static final Dijkstra dijkstra = new Dijkstra();
static Graph graph;
static List<Node> nodes = new ArrayList<>();
@BeforeAll
static void setup() {
graph = new Graph();
nodes.add(new Node("A"));
nodes.add(new Node("B"));
nodes.add(new Node("C"));
nodes.add(new Node("D"));
nodes.add(new Node("E"));
nodes.add(new Node("F"));
nodes.add(new Node("G"));
nodes.get(0).addAdjacentNode(nodes.get(1), 10);
nodes.get(0).addAdjacentNode(nodes.get(2), 15);
nodes.get(1).addAdjacentNode(nodes.get(3), 12);
nodes.get(1).addAdjacentNode(nodes.get(5), 15);
nodes.get(2).addAdjacentNode(nodes.get(4), 10);
nodes.get(3).addAdjacentNode(nodes.get(4), 2);
nodes.get(3).addAdjacentNode(nodes.get(5), 1);
nodes.get(5).addAdjacentNode(nodes.get(4), 5);
nodes.get(5).addAdjacentNode(nodes.get(6), 3);
graph.addNode(nodes);
}
}Here is what the graph looks like visually:
Up to this point, our tests should be passed:
@Test
void testGetShortestPath() {
Node nodeA = nodes.get(0);
Node nodeE = nodes.get(4);
Node nodeF = nodes.get(5);
Node nodeG = nodes.get(6);
dijkstra.calculateShortestPath(graph, nodeA);
assertEquals(24, dijkstra.getTotalDistance(nodeE));
assertEquals(23, dijkstra.getTotalDistance(nodeF));
assertEquals(26, dijkstra.getTotalDistance(nodeG));
}The code example is available here.
