- Dijkstra’s algorithm finds the shortest path in a
**weighted graph**from a single source. - The weighted graph for Dijkstra’s algorithm contains only positive edge weights.
- It uses a priority queue to select a node (vertex) nearest to the source that has not been edge relaxed.
**The edge relaxation for a node is done as below**

**If**( distance [adjacent-node] > length-of-path-to-adjacent-node-from-source + distance [source-node] )**then**

distance [adjacent-node] = length-of-path-to-adjacent-node-from-source + distance [source-node]

**Note :**

a) The distance [ ] array stores the shortest distance of every node from the source-node.

b) Dijkstra’s algorithm begins by initializing distance [ source ] = 0 i.e the distance from source node to itself is 0 and distance [ all_other_nodes ] = ∞. - Since Dijkstra’s algorithm cannot handle negative edge weights,
**Bellman-Ford**algorithm is used for finding the shortest path in a graph containing negative edge weights. - In a graph with only positive edge weights, Dijkstra’s algorithm with a priority queue implementation runs faster in O ((E+V) log V) than Bellman-Ford O (E.V).

E represents the edges and V represents the vertices in the graph.

**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_of_path_to_adjacent_node_from_source + distance [source_node] ) **then**

7. distance [adjacent_node] = length_of_path_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** ).

Current source node |
Adjacent node |
Distance to the adjacent node from the original source ( 0 ) |
Edge relaxation |
---|---|---|---|

0 | 1 | distance [ 1 ] = ∞ | distance [ 1 ] > distance_between [ 0 - 1 ] + distance [ 0 ] i.e Since ∞ > 5 + 0 Update 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 + 0 Update 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 + 0 Update 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** ).

Current source node |
Adjacent node |
Distance to the adjacent node from 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 + 1 Update 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 + 1 Update 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 + 1 Update 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** ).

Current source node |
Adjacent node |
Distance to the adjacent node from 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 + 2 Update 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** ).

Current source node |
Adjacent node |
Distance to the adjacent node from 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 + 3 Update 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** ).

Current source node |
Adjacent node |
Distance to the adjacent node from 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** ).

Current source node |
Adjacent node |
Distance to the adjacent node from 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
```

All rights reserved.