Step 5 of 6

Dijkstra's shortest paths

When edges have different weights (kilometers, milliseconds, dollars), the path with the fewest edges isn't necessarily the cheapest, so BFS is no longer enough. Dijkstra's algorithm fixes that: it's BFS with a priority queue, always expanding the unfinished vertex with the smallest known distance.

dist[src] = 0; heap = {(0, src)}
while heap not empty:
    (d, v) = pop smallest
    if d > dist[v]: continue            // stale entry, skip it
    for each edge (v, w, cost):
        if dist[v] + cost < dist[w]:
            dist[w] = dist[v] + cost; push (dist[w], w)

#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::vector<std::string> town = {"A", "B", "C", "D"};
    // adj[v] = list of (neighbor, minutes)
    std::vector<std::vector<std::pair<int, int>>> adj = {
        {{1, 10}, {2, 3}},     // A -> B 10 min, A -> C 3 min
        {{3, 2}},              // B -> D 2 min
        {{1, 4}, {3, 8}},      // C -> B 4 min, C -> D 8 min
        {},
    };

    const long long INF = 1'000'000'000;
    std::vector<long long> dist(town.size(), INF);
    using Item = std::pair<long long, int>;                       // (distance, vertex)
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> heap;
    dist[0] = 0;
    heap.push({0, 0});
    while (!heap.empty()) {
        auto [d, v] = heap.top();
        heap.pop();
        if (d > dist[v]) continue;                                // an outdated entry
        for (auto [w, cost] : adj[v]) {
            if (dist[v] + cost < dist[w]) {
                dist[w] = dist[v] + cost;
                heap.push({dist[w], w});
            }
        }
    }
    for (std::size_t v = 0; v < town.size(); v++) std::cout << town[v] << " " << dist[v] << "\n";
}

A 0
B 7
C 3
D 9

Reading the result

The direct road A → B takes 10 minutes, but A → C → B takes 3 + 4 = 7. And D is best reached through B: 7 + 2 = 9, beating A → C → D at 11. BFS, which counts edges, would have picked the direct 10-minute road.

The details

• The heap holds (distance, vertex) pairs. Pairs compare by their first element, and std::greater makes it a min-heap, so top() is the closest unfinished vertex.
• A vertex can be pushed several times as better routes are found. The if (d > dist[v]) continue; line skips the outdated entries. This "lazy deletion" is simpler than updating entries inside the heap.
• Use long long for distances: many large weights can add up past the int limit.
• It requires non-negative weights. A negative edge could make a "finished" vertex cheaper later, which breaks the algorithm's core assumption.

O((V + E) log V). It's the algorithm behind route planners and network routing protocols like OSPF. For your task, build the adjacency list from the edge list first, and turn every distance still at "infinity" into -1 at the end.

Your turn: write std::vector<long long> dijkstra(int n, const std::vector<Edge>& edges, int src) for a directed graph. Unreachable vertices get -1.

Previous: Topological sort Next: Challenge: union-find