Dijkstra's Algorithm

Shortest path algorithms

The shortest path problem is about finding a path between 2 vertices in a graph such that the total sum of the weights of the edges is minimum. This problem could be solved easily using BFS if all edge weights were (1), but here weights can take any value. Let’s discuss Dijkstra’s Algorithm that works to find the shortest path between two vertices.

Dijkstra’s Algorithm

Dijkstra’s Algorithm solves the single-source shortest-path problem on a weighted, directed graph G = (V, E) for the case where all edge weights are non-negative. This algorithm follows the steps listed below:

• Set all vertices distances = infinity except for the source vertex. Set the source distance = 0.
• Push the source vertex in a min-priority queue in the form (distance, vertex), as the comparison in the min-priority queue will be according to the distance of the vertices.
• Pop the vertex with the minimum distance from the Priority Queue (at first the popped vertex = source).
• Update the distances of the connected vertices to the popped vertex in case of current vertex distance + edge weight < next vertex distance, and then push the vertex with the new distance to the Priority Queue.
• If the popped vertex is visited before, just continue without using it.
• Apply the same algorithm again until the priority queue is empty.

Let us now visualize this algorithm and see how it is working. The number written in the vertex denotes the cost to reach that node.