Dijkstra's Shortest Path

When roads have lengths

BFS counts edges. With road lengths, two short roads can beat one long road. Dijkstra's algorithm finds the shortest total distance from a start to every place, as long as no length is negative.

• Every place starts at distance ∞, the start at 0.
• Repeatedly take the closest unfinished place (a min-heap gives it fast).
• From it, try each road: if it gives a neighbour a shorter distance, update it and push it.

Think of it like this: Water spilled at the start spreads along the roads at a steady speed; it reaches each place first along the shortest route. Dijkstra always finishes the place the water would reach next.

#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // places: 0=A, 1=B, 2=C, 3=D
    int n = 4;
    vector<vector<pair<int, int>>> g(n);          // (neighbour, length)
    g[0] = {{1, 4}, {2, 1}};
    g[2] = {{1, 2}, {3, 5}};
    g[1] = {{3, 1}};

    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > dist[v]) continue;                // old, longer entry
        for (auto [w, len] : g[v]) {
            if (d + len < dist[w]) {
                dist[w] = d + len;
                pq.push({dist[w], w});
            }
        }
    }
    for (int v = 0; v < n; v++) cout << char('A' + v) << ": " << dist[v] << endl;
    return 0;
}

Output

A: 0
B: 3
C: 1
D: 4

A → C → B → D is 1 + 2 + 1 = 4, shorter than A → B → D (5). Time: O((V + E) log V).

Common mistake: Dijkstra fails with negative edge lengths. (Bellman-Ford handles those.)