Shortest paths and topological order

BFS finds shortest paths when every edge costs the same. Real graphs have weights — road lengths, latencies, prices — and often have a direction that means "must happen before". This lesson covers the two workhorses: Dijkstra's algorithm for shortest paths with non-negative weights, and topological sorting for ordering a directed acyclic graph (DAG). Both are short to write and easy to get subtly wrong.

1. Weighted graphs

Store a weighted directed graph as an adjacency list of (to, weight) pairs:

struct Edge { int from; int to; std::int64_t weight; };

std::vector<std::vector<std::pair<int, std::int64_t>>> out(n);
for (const Edge& e : edges) out[e.from].emplace_back(e.to, e.weight);

Two habits save a lot of debugging:

• Use 64-bit distances. A path of three edges of weight 10⁹ is already 3 × 10⁹, beyond int. Signed overflow is undefined behaviour, and it turns "huge" into "negative", which then looks like the best distance of all.
• Represent "unreachable" explicitly — std::optional<std::int64_t>, or a sentinel like INT64_MAX that you never add to. INF + w is the classic overflow.

2. Dijkstra's algorithm

Dijkstra grows a set of settled vertices whose distance is final. At each step it settles the unsettled vertex with the smallest tentative distance, then relaxes its outgoing edges: if dist[u] + w < dist[v], v has found a better route through u.

Why is the smallest tentative distance final? Every other route to that vertex leaves the settled set through some vertex that is at least as far, and the remaining edges can't make it shorter — because weights are non-negative. That one assumption is the whole correctness argument.

Worked example: Dijkstra with a heap and path reconstruction

Finding the smallest unsettled vertex by scanning is O(V) per step. A min-heap of (distance, vertex) does it in O(log V). std::priority_queue can't decrease a key, so we use lazy deletion: push a new entry whenever a distance improves, and skip entries that are out of date when they are popped.

#include <cstdint>
#include <functional>
#include <optional>
#include <print>
#include <queue>
#include <utility>
#include <vector>

struct Edge { int from; int to; std::int64_t weight; };

int main() {
    int n = 5;
    std::vector<Edge> edges{{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3}};
    std::vector<std::vector<std::pair<int, std::int64_t>>> out(n);
    for (auto e : edges) out[e.from].emplace_back(e.to, e.weight);

    std::vector<std::optional<std::int64_t>> dist(n);
    std::vector<int> parent(n, -1);
    using Entry = std::pair<std::int64_t, int>;  // (distance, vertex)
    std::priority_queue<Entry, std::vector<Entry>, std::greater<>> heap;

    dist[0] = 0;
    heap.emplace(0, 0);
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (d != *dist[u]) continue;          // stale: a better entry was pushed later
        for (auto [v, w] : out[u]) {
            if (!dist[v] || d + w < *dist[v]) {
                dist[v] = d + w;
                parent[v] = u;
                heap.emplace(d + w, v);
            }
        }
    }

    for (int v = 0; v < n; ++v) std::print("{} ", *dist[v]);
    std::println();

    std::vector<int> path;                    // walk parents back from 4, then reverse
    for (int v = 4; v != -1; v = parent[v]) path.push_back(v);
    for (auto it = path.rbegin(); it != path.rend(); ++it) std::print("{} ", *it);
    std::println();
}

Each edge pushes at most one entry, so the heap holds at most E + 1 entries and the total cost is O((V + E) log V). The continue matters for speed, not correctness: without it every stale pop would relax all of u's edges again.

Why negative edges break it

Dijkstra settles 2 at distance 2 (via the direct edge) before it has explored 1's edge of weight −5, which would give 3 + (−5) = −2. Once a vertex is settled, the algorithm never revisits it — so the answer is wrong. For negative weights use Bellman-Ford: relax every edge V − 1 times (O(VE)); if a V-th round still improves something, there is a negative cycle and shortest paths don't exist.

for (int round = 0; round < n - 1; ++round)
    for (const Edge& e : edges)
        if (dist[e.from] && (!dist[e.to] || *dist[e.from] + e.weight < *dist[e.to]))
            dist[e.to] = *dist[e.from] + e.weight;

3. 0-1 BFS

If every weight is 0 or 1, you don't need a heap. Keep a deque: relaxing over a 0-edge gives the same distance, so push to the front; a 1-edge gives distance + 1, so push to the back. The deque always holds at most two distinct distances in sorted order, so popping the front is popping the minimum. Total: O(V + E).

Typical uses: grids where some moves are free, "minimum number of edges to reverse", state graphs with free and costly transitions.

4. Topological order

A topological order of a DAG lists every vertex so that each edge u → v has u before v — a build order, a course schedule, a spreadsheet's evaluation order. It exists exactly when the graph has no cycle.

Kahn's algorithm works with in-degrees (the number of incoming edges):

1. Count in-degrees. Every vertex with in-degree 0 is ready.
2. Repeatedly take a ready vertex, append it, and "remove" its outgoing edges: decrement each successor's in-degree; those that reach 0 become ready.
3. If fewer than n vertices came out, the rest sit on a cycle — their in-degree never reaches 0.

Which ready vertex you take is up to you. A FIFO queue gives a valid order; a min-heap gives the lexicographically smallest one.

Faded example: Kahn's algorithm

The setup is done; fill in the three blanks of the loop, then the cycle check.

std::vector<int> order;
while (!ready.empty()) {
    int u = /* ??? the vertex to output next */;
    ready.pop();
    order.push_back(u);
    for (int v : out[u])
        if (/* ??? */) ready.push(v);
}
if (/* ??? */) return std::nullopt;
return order;

#include <functional>
#include <optional>
#include <print>
#include <queue>
#include <utility>
#include <vector>

std::optional<std::vector<int>> topo(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<std::vector<int>> out(n);
    std::vector<int> indegree(n, 0);
    for (auto [u, v] : edges) {
        out[u].push_back(v);
        ++indegree[v];
    }
    std::priority_queue<int, std::vector<int>, std::greater<>> ready;  // smallest first
    for (int v = 0; v < n; ++v)
        if (indegree[v] == 0) ready.push(v);

    std::vector<int> order;
    while (!ready.empty()) {
        int u = ready.top();               // take the smallest ready vertex
        ready.pop();
        order.push_back(u);
        for (int v : out[u])               // remove u's outgoing edges
            if (--indegree[v] == 0) ready.push(v);
    }
    if (static_cast<int>(order.size()) != n) return std::nullopt;  // stuck on a cycle
    return order;
}

int main() {
    auto order = topo(5, {{3, 1}, {2, 1}, {1, 4}, {0, 4}});
    for (int v : *order) std::print("{} ", v);
    std::println();
    std::println("{}", topo(3, {{0, 1}, {1, 2}, {2, 1}}).has_value());
}

The alternative is DFS post-order: run DFS, append each vertex when it finishes, then reverse. A back edge to a vertex that is still on the stack (colour "grey") is a cycle.

5. Shortest and longest paths in a DAG

In a DAG you can do better than Dijkstra: process vertices in topological order and relax their outgoing edges. When you reach u, every edge into u has already been relaxed, so u's value is final. This is O(V + E), and it works with negative weights — and also for longest paths (replace min with max), which in general graphs is NP-hard. That's dynamic programming over a DAG, which the next skills build on.

std::vector<std::int64_t> best(n, 0);            // a path may start anywhere
for (int u : order)
    for (auto [v, w] : out[u]) best[v] = std::max(best[v], best[u] + w);

6. Minimum spanning trees (preview)

Two more classics reuse these pieces on undirected weighted graphs:

• Kruskal: sort edges by weight; add an edge if its endpoints are in different components (union-find). O(E log E).
• Prim: Dijkstra's loop, but the key of a vertex is the weight of the cheapest edge connecting it to the tree so far, not the distance from a source.

7. Choosing

Summary

• Distances in 64 bits; "unreachable" explicit — never INF + w.
• Dijkstra: min-heap of (dist, vertex), relax dist[u] + w, skip stale entries with if (d != dist[u]) continue;. Non-negative weights only.
• 0-1 BFS: deque, 0-edges to the front.
• Kahn: in-degrees, take ready vertices (min-heap for the smallest order), fewer than n output ⇒ cycle.
• In a DAG, process in topological order: shortest or longest paths in O(V + E), negative weights allowed.