Dijkstra's Algorithm for Non-Negative Weights

Dijkstra's algorithm computes the shortest-path distance from a source vertex $s$ to every other vertex in a graph with non-negative edge weights $w(u,v) \geq 0$.

Each vertex $v$ carries a tentative label $d(v)$, the length of the shortest path from $s$ to $v$ found so far. Vertices are split into visited (label finalized) and unvisited (label may still decrease).

Algorithm:

1. Initialize $d(s) = 0$ and $d(v) = \infty$ for all $v \neq s$. Mark every vertex unvisited.
2. While some vertex is unvisited:
   • Let $u$ be the unvisited vertex with the smallest label $d(u)$.
   • For each outgoing edge $(u, v)$, relax: if $d(u) + w(u,v) < d(v)$, update

$$d(v) \leftarrow d(u) + w(u,v).$$

• Mark $u$ as visited.

When all vertices are visited, $d(v)$ equals the true shortest-path distance from $s$ to $v$.

Why non-negative weights? When $u$ is selected with the smallest unvisited label, no path through other unvisited vertices can reach $u$ more cheaply: any such alternative crosses an unvisited vertex with label $\geq d(u)$, and the remaining edges contribute non-negative weight. Negative edges would invalidate this guarantee.