Dijkstra's Algorithm
Weighted graphs are graphs with edges that have a value associated with them. This value is called the weight of the edge.
One of the most famous algorithms for finding the shortest path in a weighted graph is Dijkstra's algorithm. It was invented by Edsger Dijkstra, a Dutch computer scientist.
Dijkstra's algorithm uses a priority queue to keep track of the vertices to visit next.
The algorithm works as follows:
- Initialize the priority queue with the source node and its distance from the source node.
- While the priority queue is not empty:
- Dequeue the vertex with the smallest distance from the priority queue.
- For each neighbor of the dequeued vertex:
- Calculate the tentative distance from the source node to the neighbor through the dequeued vertex.
- Update the distance from the source node to the neighbor if the calculated distance is smaller than the current distance.
Example use cases include: