The key points of Dijkstra’s single source shortest path algorithm is as below :
Algorithm : Dijkstra’s Shortest Path Java
1. Initialize the distance from the source node S to all other nodes as infinite (999999999999) and to itself as 0.
2. Insert an object of < node, distance > for source i.e < S, 0 > in a priority based Queue
where the priority of the elements in the Queue is based on the length of the distance.
3. While the Priority Queue is not empty do
4. object_at_top = PriorityQueue. peek();
Remove the object from the top of the Priority Queue.
source_node = object_at_top . node.
5. For every adjacent_node to source_node do
6. If distance [adjacent_node] > length_to_adjacent_node_from_source + distance [source_node])
7. distance [adjacent_node] = length_to_adjacent_node_from_source + distance [source_node]
8. Update the Priority Queue with the new object < adjacent_node, distance [adjacent_node] >
Below data structures are used for storing the graph before running Dijkstra’s algorithm Adjacency List : List of pairs of adjacent nodes and their corresponding weights in the graph.
Dijkstra’s algorithm step-by-step
This example of Dijkstra’s algorithm finds the shortest distance of all the nodes in the graph from the single / original source node 0.
Step 1 : Initialize the distance of the source node to itself as 0 and to all other nodes as ∞.
Insert the object < distance_from_original_source, node > in the priority queue.
i.e Insert < 0, 0 > in the priority queue as the distance from the original source (0) to itself is 0.
Step 2 : Remove the object < 0, 0 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the original source node ( 0 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
0 | 1 | distance [ 1 ] = ∞ | distance [ 1 ] > distance_between [ 0 - 1 ] + distance [ 0 ]i.e Since ∞ > 5 + 0Update distance, i.e distance [ 1 ] = 5 and insert object < 1, 5 > in the priority queue. |
0 | 2 | distance [ 2 ] = ∞ | distance [ 2 ] > distance_between [ 0 - 2 ] + distance [ 0 ]i.e Since ∞ > 1 + 0Update distance, i.e distance [ 2 ] = 1 and insert object < 2, 1 > in the priority queue. |
0 | 3 | distance [ 3 ] = ∞ | distance [ 3 ] > distance_between [ 0 - 3 ] + distance [ 0 ]i.e Since ∞ > 4 + 0Update distance, i.e distance [ 3 ] = 4 and insert object < 3, 4 > in the priority queue. |
Step 3 : Remove the object < 2, 1 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 2 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
2 | 0 | distance [ 0 ] = 0 | distance [ 0 ] < distance_between [ 2 - 0 ] + distance [ 2 ]i.e Since 0 < 1 + 1 No edge relaxation needed. |
2 | 1 | distance [ 1 ] = 5 | distance [ 1 ] > distance_between [ 2 - 1 ] + distance [ 2 ]i.e Since 5 > 3 + 1Update distance, i.e distance [ 1 ] = 4 and insert object < 1, 4 > in the priority queue. |
2 | 3 | distance [ 3 ] = 4 | distance [ 3 ] > distance_between [ 2 - 3 ] + distance [ 2 ]i.e Since 4 > 2 + 1Update distance, i.e distance [ 3 ] = 3 and insert object < 3, 3 > in the priority queue. |
2 | 4 | distance [ 4 ] = ∞ | distance [ 4 ] > distance_between [ 2 - 4 ] + distance [ 2 ]i.e Since ∞ > 1 + 1Update distance, i.e distance [ 4 ] = 2 and insert object < 4, 2 > in the priority queue. |
Step 4 : Remove the object < 4, 2 > from the from of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 4 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
4 | 1 | distance [ 1 ] = 4 | distance [ 1 ] < distance_between [ 4 - 1 ] + distance [ 4 ]i.e Since 4 < 8 + 2 No edge relaxation needed. |
4 | 2 | distance [ 2 ] = 1 | distance [ 2 ] < distance_between [ 4 - 2 ] + distance [ 4 ]i.e Since 1 < 1 + 2 No edge relaxation needed. |
4 | 3 | distance [ 3 ] = 3 | distance [ 3 ] < distance_between [ 4 - 3 ] + distance [ 4 ]i.e Since 3 < 2 + 2 No edge relaxation needed. |
4 | 5 | distance [ 5 ] = ∞ | distance [ 5 ] > distance_between [ 4 - 5 ] + distance [ 4 ]i.e Since ∞ > 3 + 2Update distance, i.e distance [ 5 ] = 5 and insert object < 5, 5 > in the priority queue. |
Step 5 : Remove the object < 3, 3 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 3 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
3 | 0 | distance [ 0 ] = 0 | distance [ 0 ] < distance_between [ 3 - 0 ] + distance [ 3 ]i.e Since 0 < 4 + 3 No edge relaxation needed. |
3 | 2 | distance [ 2 ] = 1 | distance [ 2 ] < distance_between [ 3 - 2 ] + distance [ 3 ]i.e Since 1 < 2 + 3 No edge relaxation needed. |
3 | 4 | distance [ 4 ] = 2 | distance [ 4 ] < distance_between [ 3 - 4 ] + distance [ 3 ]i.e Since 2 < 2 + 3 No edge relaxation needed. |
3 | 5 | distance [ 5 ] = 5 | distance [ 5 ] > distance_between [ 3 - 5 ] + distance [ 3 ]i.e Since 5 > 1 + 3Update distance, i.e distance [ 5 ] = 4 and insert object < 5, 4 > in the priority queue. |
Step 6 : Remove the object < 4, 1 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 1 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
1 | 0 | distance [ 0 ] = 0 | distance [ 0 ] < distance_between [ 1 - 0 ] + distance [ 1 ]i.e Since 0 < 5 + 4 No edge relaxation needed. |
1 | 2 | distance [ 2 ] = 1 | distance [ 2 ] < distance_between [ 1 - 2 ] + distance [ 1 ]i.e Since 1 < 3 + 4 No edge relaxation needed. |
1 | 4 | distance [ 4 ] = 2 | distance [ 4 ] < distance_between [ 1 - 4 ] + distance [ 1 ]i.e Since 2 < 8 + 4 No edge relaxation needed. |
Step 7 : Remove the object < 4, 5 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 5 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
5 | 3 | distance [ 3 ] = 3 | distance [ 3 ] < distance_between [ 5 - 3 ] + distance [ 5 ]i.e Since 3 < 1 + 4 No edge relaxation needed. |
5 | 4 | distance [ 4 ] = 2 | distance [ 4 ] < distance_between [ 5 - 4 ] + distance [ 5 ]i.e Since 2 < 3 + 4 No edge relaxation needed. |
The algorithm terminates here as the priority queue is empty and we have calculated the shortest path to all the nodes from the original source 0 as shown below.
Data structure used for running Dijkstra’s shortest path : Distance based priority queue for choosing the vertex nearest to the source.
Graph type: Designed for weighted (directed / un-directed) graph containing positve edge weights.
Time complexity of Dijkstra’s algorithm : O ( (E+V) Log(V) ) for an adjacency list implementation of a graph. V is the
number of vertices and E is the number of edges in a graph.
Dijkstra’s shortest path in Java
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Comparator;
class NodeDist {
int node; // Adjacent node
long dist; // Distance to adjacent node
NodeDist (int node, long dist) {
this.node = node;
this.dist = dist;
}
}
class Dijkstras {
void ShortestPath (int source_node, int node_count, List<List<NodeDist>> graph) {
// Assume that the distance from the source_node to other nodes is infinite
// in the beginnging, i.e initialize the distance list to a max value
Long INF = (long) 999999999;
List<Long> dist = new ArrayList<Long>(Collections.nCopies(node_count, INF));
// Distance from the source vertex to itself is 0
dist.set(source_node, (long) 0); // (Node, Dist)
// Comparator lambda function that enables the priority queue to store the nodes
// based on the distance in the ascending order.
Comparator<NodeDist> NodeDistComparator = (obj1, obj2) -> {
if (obj1.dist < obj2.dist)
return 1;
if (obj1.dist > obj2.dist)
return -1;
return 0;
};
// Priority queue stores the object node-distance into the queue with
// the smallest distance node at the top.
PriorityQueue<NodeDist> pq = new PriorityQueue<>(NodeDistComparator);
pq.add(new NodeDist(source_node, 0));
while (!pq.isEmpty()) {
NodeDist obj = pq.peek();
pq.remove();
int current_source = obj.node;
for (NodeDist obj_node_dist : graph.get(current_source)) {
int adj_node = obj_node_dist.node;
long length_to_adjnode = obj_node_dist.dist;
// Edge relaxation
if (dist.get(adj_node) > length_to_adjnode + dist.get(current_source)) {
// If the distance to the adjacent node is not INF, means the object <node, dist> is in the priority queue.
// Remove the object before updating it in the priority queue.
if (dist.get(adj_node) != INF) {
pq.remove(new NodeDist(adj_node, dist.get(adj_node)));
}
dist.set(adj_node, length_to_adjnode + dist.get(current_source));
pq.add(new NodeDist(adj_node, dist.get(adj_node)));
}
}
}
for (int i=0; i<node_count; i++)
System.out.println("Source Node(" + source_node + ") -> Destination Node(" + i + ") : " + dist.get(i));
}
public static void main(String args[]) {
int node_count = 6;
List<List<NodeDist>> graph = new ArrayList<>(node_count);
for(int i=0; i<node_count; i++) {
graph.add(new ArrayList<>());
}
// Node 0: <1,5> <2,1> <3,4>
Collections.addAll(graph.get(0), new NodeDist(1, 5), new NodeDist(2, 1), new NodeDist(3, 4));
// Node 1: <0,5> <2,3> <4,8>
Collections.addAll(graph.get(1), new NodeDist(0, 5), new NodeDist(2, 3), new NodeDist(4, 8));
// Node 2: <0,1> <1,3> <3,2> <4,1>
Collections.addAll(graph.get(2), new NodeDist(0, 1), new NodeDist(1, 3), new NodeDist(3, 2), new NodeDist(4, 1));
// Node 3: <0,4> <2,2> <4,2> <5,1>
Collections.addAll(graph.get(3), new NodeDist(0, 4), new NodeDist(2, 2), new NodeDist(4, 2), new NodeDist(5, 1));
// Node 4: <1,8> <2,1> <3,2> <5,3>
Collections.addAll(graph.get(4), new NodeDist(1, 8), new NodeDist(2, 1), new NodeDist(3, 2), new NodeDist(5, 3));
// Node 5: <3,1> <4,3>
Collections.addAll(graph.get(5), new NodeDist(3, 1), new NodeDist(4, 3));
int source_node = 0;
Dijkstras d = new Dijkstras();
d.ShortestPath(source_node, node_count, graph);
System.out.println();
source_node = 5;
d.ShortestPath(source_node, node_count, graph);
}
}
Output
Source Node(0) -> Destination Node(0) : 0
Source Node(0) -> Destination Node(1) : 4
Source Node(0) -> Destination Node(2) : 1
Source Node(0) -> Destination Node(3) : 3
Source Node(0) -> Destination Node(4) : 2
Source Node(0) -> Destination Node(5) : 4
Source Node(5) -> Destination Node(0) : 4
Source Node(5) -> Destination Node(1) : 6
Source Node(5) -> Destination Node(2) : 3
Source Node(5) -> Destination Node(3) : 1
Source Node(5) -> Destination Node(4) : 3
Source Node(5) -> Destination Node(5) : 0