Dijkstra's Shortest Path Algorithm

In unweighted graphs, BFS finds the shortest path. But many real-world graphs have weighted edges — roads have distances, network links have latencies, and pipelines have capacities. Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a graph with non-negative edge weights.

---

The Problem

Given a weighted graph and a source vertex, find the shortest (minimum total weight) path from the source to every other vertex.

Example: In a road network, find the shortest driving distance from your home to every other location.

---

How Dijkstra's Algorithm Works

Dijkstra's algorithm maintains a distance table and a priority queue (or a simple unvisited set). It works as follows: