Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights. It uses a min-heap (priority queue) to greedily select the closest unvisited node and relax its neighbors. Time complexity is O((V+E) log V) with a binary heap.
vector<int> dijkstra(vector<vector<pair<int,int>>>& adj, int src, int n) {
vector<int> dist(n, INT_MAX);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
dist[src]=0; pq.push({0,src});
while (!pq.empty()) {
auto [d,u]=pq.top(); pq.pop();
if (d>dist[u]) continue;
for (auto [v,w]:adj[u])
if (dist[u]+w<dist[v]) { dist[v]=dist[u]+w; pq.push({dist[v],v}); }
}
return dist;
}Dijkstra greedily picks the unvisited node with the smallest known distance. Once a node is finalized, its distance is optimal — no future path through unvisited nodes can be shorter (requires non-negative weights).
For each neighbor v of the current node u: if dist[u] + weight(u,v) < dist[v], update dist[v]. This relaxation step is at the core of all shortest-path algorithms.
A min-heap (priority queue) selects the minimum-distance node in O(log V). Each relaxation pushes to the heap. Stale entries (where d > dist[u]) are skipped.
Dijkstra fails on negative-weight edges because a later path could reduce an already-finalized distance. Use Bellman-Ford for graphs with negative edges.
Dijkstra's algorithm cannot handle:
With a binary min-heap, Dijkstra's time complexity is:
Dijkstra's algorithm is a: