AntInLoop

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 weight w:
  • If dist[u] + w < dist[v], update dist[v] = dist[u] + w and 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): Relax 1→4, 2→1 → dist = [0, 4, 1, ∞]
  • Pop (1, 2): Relax 1→3 (better than 4!), 3→6 → dist = [0, 3, 1, 6]
  • Pop (3, 1): Relax 3→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 u is popped with minimum tentative distance d, Dijkstra assumes no future path can ever reach u with 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 support decrease-key. Pushing duplicates and discarding stale pops keeps code concise and maintains $O((V + E) \log V)$ time.
  • Use long long for Distances: Summed edge weights frequently exceed 32-bit INT_MAX ($2.1 \times 10^9$); always use long long and INF = 1e18 in 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