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

...