Dijkstra’s Algorithm

Find the single-source shortest path from a source node to all other nodes in a connected graph that must have non-negative weights.

Dijkstra’s Algorithm summary card

Table of Contents
· How Dijkstra’s Algorithm works?
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Data structure
    ∘ Complexity
    ∘ Golang
    ∘ Python
· Dijkstra’s Algorithm Fail on Negative Weight
  ∘ Graphical Explanation

How Dijkstra’s Algorithm works?

Dijkstra’s Algorithm is a type of greedy algorithm that picks the edge that has the minimum distance from the source node at each step to find the shortest path between the source node and all other nodes in a graph.

Based on the principle of relaxation, Dijkstra’s Algorithm overestimates the distance between every node and the source node initially. Then visit every node and perform this relaxation process on all its outgoing edges. It gradually replaces with an approximate distance by the minimum of the old path length and a new found path length until the shortest distance is reached to a node.

Once a node is visited, the current path to the node is the shortest path from source node to the node. This visited node will never be visited again.

Graphical Explanation

Positive weights graph

• Step 1: Set the distance to the source/start node itself to 0 and the distance to all other nodes to infinity. Keep track of already visited nodes.

Initial setting for positive weights graph

• Step2: Select a non-visited node that has the shortest distance to the source node based on the current known distances.
• Step 3: Mark the selected node as visited.
• Step 4: Look at the edges that are outgoing from the selected node and check if a shorter path to reach its adjacent nodes can be found. If the length of newly found path is shorter, we update the distance. (Avoid updating distances of already visited nodes)

min(
distance[adjacent_node], 
distance[selected_node] + edge_weight(selected_node, adjacent_node),
)

Iteration 1

• Step 5: Repeat Step 2 to Step3 until all the nodes have been visited.

Iteration 2

Iteration 3

Iteration 4

Iteration 5

Iteration 6

At the end, the algorithm has visited all nodes in the graph and found the smallest distance to each node.

Code Implementation

Data structure

Use priority queue(heap) to greedily select the closest nodes that haven’t visited.

Complexity

Time: O((v+e)*log(v)), Space: O(v)

v: the total number of vertices, e: the total number of edges

Golang

When we use a heap data structure to select a node with the shortest distance to the source node, the visited map will become redundant. Because we already found the smallest distance to reach the visited node, it will not have a chance to add back to the min heap. (When we found a new shorter path to a node, we will add it to the min heap)

Therefore, we can remove the visited map in the code. Check the length of the min heap to decide whether if the loop should be terminated or not.

Python

Dijkstra’s Algorithm Fail on Negative Weight

Dijkstra’s Algorithm is only applicable to a positive weighted graph because the algorithm adds the weights of the edges to find the shortest path during the execution. Once a node has been marked as visited, the current path to the node is taken as the shortest path from source node to reach the node.

In a positive weight graph, adding more edges in the path will only increase the path. However, if there are negative weights in the graph, adding more edges in a path may lead to decreasing the path. Therefore, the shortest path may be alter for the visited nodes.

However, in Dijkstra’s Algorithm, every node is only visited once. If a negative weight alter the length of shortest path, it will not be observed for the visited nodes. That’s why Dijkstra’s Algorithm will not work properly in a graph that contains negative weights.

Graphical Explanation

negative weights graph

Initial setting for negative weights graph

Iteration 1

Iteration 2

Iteration 3

Iteration 4

result

When we visited node 2 , we skip the edge that connected to node 3 that is already visited. Because the smallest distance to the visited node is already found, so there is no need to look at any subpath that can reach the visited node. However, this way will lead to an incorrect result as we have negative weights in the graph.

In this example, if the node 2 still check the edge that connected to node 3 that is a visited node, the result will be altered because it will find a shorter path. However, visiting a node more than once is not how Dijkstra’s Algorithm work.

You can access the source code here.

Other shortest path algorithms

• Breadth First Search(BFS) algorithm
• Bellman-Ford algorithm
• A* search algorithm
• The comparison of shortest path algorithms