Dijkstra's Algorithm
Dijkstra's Algorithm computes single-source shortest paths in graphs with non-negative edge weights using a greedy min-heap relaxation strategy.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code · Play Dijkstra's Algorithm Game
Dijkstra's Algorithm
Dijkstra's Algorithm finds the shortest path from a single source vertex src to all other vertices in a weighted graph with non-negative edge weights ($w \ge 0$). It greedily finalizes the unvisited vertex with the smallest tentative distance using a min-Heap (std::priority_queue) and relaxes its outgoing edges.
At a Glance
| Property | Value |
| :--- | :--- |
| Time Complexity | $O((V + E) \log V)$ with binary heap / $O(V^2)$ on dense graphs |
| Auxiliary Space | $O(V + E)$ |
| Handles Negative Edges? | No (use Bellman–Ford instead) |
| Works on Directed & Undirected? | Yes |
| Best Used When | Single-source shortest paths with $w \ge 0$ (maps, network routing, game pathfinding) |
---
How It Works
1. Set dist[0..V-1] = INF and dist[src] = 0.
2. Push (0, src) into a min-priority queue ordered by distance.
3. While the priority queue is not empty:
- Pop
(d, u). - Skip stale entries: if
d > dist[u], continue. - For each edge
(u → v)with weightw: - If
dist[u] + w < dist[v], updatedist[v] = dist[u] + wand push(dist[v], v).
procedure dijkstra(adj, src):
dist = array of INF
dist[src] = 0
minHeap.push((0, src))
while minHeap is not empty:
(d, u) = minHeap.popMin()
if d > dist[u]: continue
for (v, w) in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
minHeap.push((dist[v], v))
return dist
Step-by-Step Trace
Directed graph: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), starting from 0:
- Init:
dist = [0, ∞, ∞, ∞], heap[(0,0)] - Pop
(0, 0): Relax1→4,2→1→dist = [0, 4, 1, ∞] - Pop
(1, 2): Relax1→3(better than 4!),3→6→dist = [0, 3, 1, 6] - Pop
(3, 1): Relax3→4(better than 6!) →dist = [0, 3, 1, 4] - Pop
(4, 1): Stale (4 > dist[1] = 3) → skip! - Pop
(4, 3): No outgoing edges →dist = [0, 3, 1, 4]
---
Complexity & Key Insights
- Why Negative Weights Break Dijkstra: Once a vertex
uis popped with minimum tentative distanced, Dijkstra assumes no future path can ever reachuwith a smaller distance. A negative edge later in the graph violates that assumption. - Lazy Deletion (
if (d > dist[u]) continue;): Standard library heaps don't supportdecrease-key. Pushing duplicates and discarding stale pops keeps code concise and maintains $O((V + E) \log V)$ time. - Use
long longfor Distances: Summed edge weights frequently exceed 32-bitINT_MAX($2.1 \times 10^9$); always uselong longandINF = 1e18in competitive programming.
---
Practice Problems
Easy
1. Single-Source Shortest Paths
Given a weighted directed graph with non-negative weights and source src, return the shortest distance to every vertex (-1 if unreachable).
Approach: Standard min-heap Dijkstra with lazy stale-entry skipping. Time: $O((V + E) \log V)$. Space: $O(V + E)$.
<details>
<summary>Show C++ Solution</summary>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
std::vector<long long> dijkstra(int n, const std::vector<std::vector<std::pair<int, int>>>& adj, int src) {
const long long INF = std::numeric_limits<long long>::max() / 4;
std::vector<long long> dist(n, INF);
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (const auto& [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
for (auto& d : dist) if (d == INF) d = -1;
return dist;
}
int main() {
int n = 4;
std::vector<std::vector<std::pair<int, int>>> adj(n);
adj[0].push_back({1, 4}); adj[0].push_back({2, 1});
adj[2].push_back({1, 2}); adj[1].push_back({3, 1});
adj[2].push_back({3, 5});
for (long long d : dijkstra(n, adj, 0)) std::cout << d << " ";
std::cout << "\n";
return 0;
}
</details>
2. Reconstruct the Shortest Path
Find both the shortest distance and the actual sequence of vertices from src to target.
Approach: Maintain a parent array; whenever dist[u] + w < dist[v], record parent[v] = u. After Dijkstra finishes, walk backward from target to src and reverse. Time: $O((V + E) \log V)$. Space: $O(V + E)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
std::vector<int> shortestPath(int n, const std::vector<std::vector<std::pair<int, int>>>& adj, int src, int target) {
const long long INF = std::numeric_limits<long long>::max() / 4;
std::vector<long long> dist(n, INF);
std::vector<int> parent(n, -1);
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
if (u == target) break;
for (const auto& [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
if (dist[target] == INF) return {};
std::vector<int> path;
for (int cur = target; cur != -1; cur = parent[cur]) path.push_back(cur);
std::reverse(path.begin(), path.end());
return path;
}
int main() {
int n = 4;
std::vector<std::vector<std::pair<int, int>>> adj(n);
adj[0].push_back({1, 4}); adj[0].push_back({2, 1});
adj[2].push_back({1, 2}); adj[1].push_back({3, 1});
adj[2].push_back({3, 5});
for (int u : shortestPath(n, adj, 0, 3)) std::cout << u << " ";
std::cout << "\n";
return 0;
}
</details>
---
Intermediate
3. Network Delay Time (LeetCode 743)
Given directed travel times (u, v, w) and a starting node k, return the minimum time for a signal to reach all $n$ nodes (or -1 if some node is unreachable).
Approach: Run Dijkstra from k; the answer is max(dist[1..n]) (or -1 if any distance remains INF). Time: $O((V + E) \log V)$. Space: $O(V + E)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
int networkDelayTime(const std::vector<std::tuple<int, int, int>>& times, int n, int k) {
std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
for (const auto& [u, v, w] : times) adj[u].push_back({v, w});
std::vector<int> dist(n + 1, INT_MAX);
using State = std::pair<int, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[k] = 0;
pq.push({0, k});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (const auto& [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (dist[i] == INT_MAX) return -1;
ans = std::max(ans, dist[i]);
}
return ans;
}
int main() {
std::cout << networkDelayTime({{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2) << "\n";
return 0;
}
</details>
4. Path with Minimum Effort (Minimax Grid Dijkstra, LeetCode 1631)
In a height grid, the effort of a path is the maximum absolute height difference between consecutive cells. Find the minimum effort from (0, 0) to (R - 1, C - 1).
Approach: Because max(effort, abs(h[nr][nc] - h[r][c])) is non-decreasing along any path, Dijkstra works directly by replacing + with max! Time: $O(RC \log(RC))$. Space: $O(RC)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
int minimumEffortPath(const std::vector<std::vector<int>>& heights) {
int R = static_cast<int>(heights.size()), C = static_cast<int>(heights[0].size());
std::vector<std::vector<int>> effort(R, std::vector<int>(C, INT_MAX));
using State = std::tuple<int, int, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
effort[0][0] = 0;
pq.push({0, 0, 0});
const int dr[4] = {1, -1, 0, 0};
const int dc[4] = {0, 0, 1, -1};
while (!pq.empty()) {
auto [e, r, c] = pq.top();
pq.pop();
if (e > effort[r][c]) continue;
if (r == R - 1 && c == C - 1) return e;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
int ne = std::max(e, std::abs(heights[nr][nc] - heights[r][c]));
if (ne < effort[nr][nc]) {
effort[nr][nc] = ne;
pq.push({ne, nr, nc});
}
}
}
}
return 0;
}
int main() {
std::cout << minimumEffortPath({{1, 2, 2}, {3, 8, 2}, {5, 3, 5}}) << "\n";
return 0;
}
</details>
---
Hard
5. Shortest Path with One Discount Coupon (State-Space Dijkstra)
In a weighted directed graph, you have one coupon that halves the weight of any single edge (w / 2). Find the shortest path from 0 to n - 1.
Approach: Expand each vertex u into two states: (u, 0) (coupon unused) and (u, 1) (coupon used). From (u, 0) you can transition to (v, 0) with cost w or to (v, 1) with cost w / 2; from (u, 1) you can only transition to (v, 1) with cost w. Run standard Dijkstra on this $2V$-state graph. Time: $O((V + E) \log V)$. Space: $O(V + E)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
long long minCostWithCoupon(int n, const std::vector<std::vector<std::pair<int, int>>>& adj) {
const long long INF = std::numeric_limits<long long>::max() / 4;
std::vector<std::vector<long long>> dist(n, std::vector<long long>(2, INF));
using State = std::tuple<long long, int, int>; // (cost, node, usedCoupon)
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[0][0] = 0;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto [d, u, used] = pq.top();
pq.pop();
if (d > dist[u][used]) continue;
for (const auto& [v, w] : adj[u]) {
if (d + w < dist[v][used]) {
dist[v][used] = d + w;
pq.push({dist[v][used], v, used});
}
if (used == 0 && d + w / 2 < dist[v][1]) {
dist[v][1] = d + w / 2;
pq.push({dist[v][1], v, 1});
}
}
}
return std::min(dist[n - 1][0], dist[n - 1][1]);
}
int main() {
int n = 3;
std::vector<std::vector<std::pair<int, int>>> adj(n);
adj[0].push_back({1, 3});
adj[1].push_back({2, 10});
adj[0].push_back({2, 9});
std::cout << minCostWithCoupon(n, adj) << "\n"; // 9/2 = 4 (cheaper than 3 + 10/2 = 8)
return 0;
}
</details>
---
Related Algorithms
- Bellman–Ford Algorithm — handles negative edge weights and detects negative cycles.
- A* Search — accelerates Dijkstra toward a single target using an admissible heuristic.
- Floyd–Warshall Algorithm — computes all-pairs shortest paths in $O(V^3)$.
- Prim's Algorithm — uses a nearly identical min-heap greedy loop to build an MST.