Dijkstra's Algorithm
Understand how to implement and apply Dijkstra's Algorithm to solve single-source shortest path problems in weighted graphs. Explore its step-by-step method using priority queues and adjacency lists to find minimum distances from a source vertex. Gain practical skills to handle graphs with non-negative edge weights and optimize pathfinding.
We'll cover the following...
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