Dijkstra's algorithm finds the shortest paths from a single source to all other vertices in a graph with non-negative edge weights. It maintains a tentative distance for each vertex, repeatedly extracts the vertex with the smallest tentative distance (which becomes final), and relaxes its outgoing edges: if a shorter route via this vertex is found, the neighbour's distance is updated.
Dijkstra's algorithm loopdist[src] = 0, all others ∞
Repeat: pick unvisited vertex with smallest dist → finalize
For each neighbour v of u: if dist[u] + w(u,v) < dist[v] → relax
Works only with non-negative weights
Run time with a heap → O((V+E) log V)
The non-negative constraint
Dijkstra fails when negative edges exist — a later, cheaper path can be discovered after a vertex is already finalized. Negative weights need Bellman-Ford instead.