Shortest Paths

The shortest-path problem asks how cheaply one vertex can reach another when each directed or undirected edge carries a cost. “Cheaply” may mean distance, time, energy, risk, or any additive quantity. The correct algorithm depends less on graph size than on the structure of the edge weights: unit weights, nonnegative weights, negative weights, acyclicity, and whether one source or every source matters.

Shortest-path algorithms share one core operation—relaxation—but differ in the order and number of times edges are relaxed. That order is what their correctness proofs justify.

Path Models

For a path

its weight is the sum of its edge weights:

The shortest-path distance from s to v is:

If v is unreachable, the distance is infinity. If a reachable negative-weight cycle can lie on a route to v, no finite minimum exists: circling the cycle makes path weight arbitrarily small, so delta(s,v) = -infinity in the extended model.

Common formulations are:

• single-source: one s to every vertex;
• single-pair: one s to one t;
• single-destination: every vertex to one t, equivalent to single-source on the transposed graph;
• all-pairs: every ordered pair (u,v).

An undirected negative edge immediately creates a negative closed walk—traverse it forward and backward—so shortest paths with negative weights are principally a directed-graph concern.

Optimal Subpaths

Every subpath of a shortest path is itself shortest between its endpoints. If a cheaper replacement subpath existed, substituting it would make the full path cheaper, contradicting optimality.

This optimal-substructure property makes predecessor trees and dynamic programming possible. It does not imply that a locally cheapest outgoing edge is safe; Dijkstra’s greedy decision needs the stronger nonnegative-weight condition.

Path Relaxation

Maintain an upper bound dist[v] on the true shortest distance. Initially:

dist[source] = 0
dist[every other vertex] = infinity
parent[every vertex] = none

Relaxing edge (u,v) checks whether the best known route to u, followed by (u,v), improves v:

RELAX(u, v, w):
    if dist[u] is finite and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        parent[v] = u
        return changed
    return unchanged

For a three-vertex example with edges S->A=8, S->B=3, and B->A=2, initialization gives (dist[S],dist[A],dist[B])=(0,infinity,infinity). Relaxing edges from S changes the vector to (0,8,3). Relaxing B->A then tests 3+2<8 and changes it to (0,5,3), recording parent[A]=B. The value 5 is not guessed locally at A; it is propagated from a previously discovered route and one final edge. Every larger shortest-path method in this chapter organizes repetitions of exactly this operation.

Relaxation Invariants

Provided arithmetic does not overflow:

1. every finite dist[v] is the weight of an actual discovered s-to-v walk;
2. therefore dist[v] >= delta(s,v) whenever a finite shortest path exists;
3. distances only decrease;
4. if all edges of one shortest path are relaxed in path order after their predecessor distances become correct, the destination distance becomes correct.

The algorithms differ in how they guarantee that decisive relaxation order.

Overflow Safety

Never compute INF + weight. Even a finite dist[u] + weight can exceed its integer range. Use a numeric contract, checked addition, or a wider type. Choosing INT_MAX as infinity does not make overflow disappear.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

static bool safe_add(int64_t a, int64_t b, int64_t *sum) {
    if (sum == NULL ||
        (b > 0 && a > INT64_MAX - b) ||
        (b < 0 && a < INT64_MIN - b)) {
        return false;
    }
    *sum = a + b;
    return true;
}

Path Recovery

Whenever relaxation improves v, setting parent[v]=u records the final edge of the best known path. After the algorithm:

target, parent[target], parent[parent[target]], ... , source

is reversed to obtain the forward path.

A safe interface distinguishes three outcomes:

• target unreachable (dist[target] is infinity);
• target affected by a negative cycle (no finite optimum);
• finite path available (parent chain reaches source).

The parent chain should contain at most V vertices. A longer chain signals a bug or negative-cycle contamination. For Floyd–Warshall, store a next[u][v] or predecessor matrix instead of one single-source parent array.

DAG Paths

In a directed acyclic graph, shortest paths can contain negative edges without negative cycles. Topologically sort the vertices, then relax outgoing edges in that order.

DAG-SHORTEST(G, source):
    order = topological sort of G
    initialize distances
    for u in order:
        if dist[u] is finite:
            for each edge (u,v,w):
                RELAX(u,v,w)

Correctness

When u is reached in topological order, every possible predecessor of u appears earlier, so every edge that could improve u has already been relaxed. Thus dist[u] is final. Relaxing its outgoing edges propagates correct candidates forward. Induction over topological order proves every reachable distance correct.

The time is Theta(V+E), including topological sorting—faster than general weighted methods. Failure to verify acyclicity invalidates the argument.

DAG longest paths are obtained by replacing minimum with maximum because no cycle can be repeated indefinitely. This supports critical-path scheduling.

Dijkstra Algorithm

Dijkstra solves single-source shortest paths when every edge weight is nonnegative.

DIJKSTRA(G, source):
    reject if any edge has negative weight
    dist[source] = 0; every other distance = infinity
    settled[v] = false for every vertex
    priority queue contains (0, source)
    while queue is not empty:
        (du,u) = extract minimum
        if settled[u] or du != dist[u]: continue
        settled[u] = true
        for each edge (u,v,w):
            if not settled[v] and RELAX(u,v,w):
                insert (dist[v],v)

“Finalize the closest unsettled vertex” is the greedy choice. A binary heap implements the priority queue; lazy duplicate entries avoid requiring decrease-key.

Dijkstra Trace

Use directed edges:

A->B 4, A->C 1, C->B 2, B->D 1, C->D 5, D->E 3, B->E 7

Distances are A=0, C=1, B=3, D=4, E=7. The path to E is A-C-B-D-E.

Greedy Correctness

Let u be the unsettled vertex with minimum tentative distance. Suppose dist[u] is not the true distance. On a true shortest path from s to u, let y be the first unsettled vertex and x its settled predecessor. When x was settled, relaxing (x,y) gave:

Since tentative distances are path weights, dist[y] >= delta(s,y), hence equality holds. The remainder of the shortest path from y to u has nonnegative weight, so:

But u was chosen with minimum tentative distance among unsettled vertices, contradicting dist[y] < dist[u]. Therefore dist[u] is final.

The nonnegative assumption is used exactly when concluding that extending the path from y cannot make it cheaper.

Negative Counterexample

Use edges S->A=2, S->B=5, B->A=-10, and A->T=0. If the required negative-edge validation is bypassed, Dijkstra settles A at 2 and propagates T=2; it may settle T before B. Processing B later reveals S-B-A=-5, but settled vertices are not processed again, so the improvement cannot propagate through A->T. The reported distance to T remains 2 although the true value is -5. A negative edge invalidates the “settled means final” decision on which the algorithm depends; a robust implementation rejects the input before producing distances.

C17 Matrix Implementation

This Theta(V^2) version keeps the algorithm visible and correctly supports zero-weight edges through a separate has_edge matrix.

#include <stdbool.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>

#define SP_MAX_VERTICES 128
#define DIST_INF INT64_MAX

typedef enum {
    DIJKSTRA_OK,
    DIJKSTRA_INVALID,
    DIJKSTRA_NEGATIVE_EDGE,
    DIJKSTRA_OVERFLOW
} DijkstraStatus;

DijkstraStatus dijkstra_matrix(
    size_t n,
    const bool has_edge[SP_MAX_VERTICES][SP_MAX_VERTICES],
    const int64_t weight[SP_MAX_VERTICES][SP_MAX_VERTICES],
    size_t source, int64_t dist[], int parent[]) {
    if (n == 0U || n > SP_MAX_VERTICES || source >= n ||
        has_edge == NULL || weight == NULL || dist == NULL || parent == NULL) {
        return DIJKSTRA_INVALID;
    }
    for (size_t u = 0; u < n; u++) {
        for (size_t v = 0; v < n; v++) {
            if (has_edge[u][v] && weight[u][v] < 0) {
                return DIJKSTRA_NEGATIVE_EDGE;
            }
            if (has_edge[u][v] && weight[u][v] == DIST_INF) {
                return DIJKSTRA_OVERFLOW;
            }
        }
    }

    bool settled[SP_MAX_VERTICES] = {false};
    for (size_t v = 0; v < n; ++v) {
        dist[v] = DIST_INF;
        parent[v] = -1;
    }
    dist[source] = 0;

    for (size_t iteration = 0; iteration < n; ++iteration) {
        size_t u = n;
        for (size_t v = 0; v < n; ++v) {
            if (!settled[v] && (u == n || dist[v] < dist[u])) {
                u = v;
            }
        }
        if (u == n || dist[u] == DIST_INF) {
            break;
        }
        settled[u] = true;

        for (size_t v = 0; v < n; ++v) {
            if (!has_edge[u][v]) {
                continue;
            }
            int64_t candidate = 0;
            if (!safe_add(dist[u], weight[u][v], &candidate) ||
                candidate == DIST_INF) {
                return DIJKSTRA_OVERFLOW;
            }
            if (candidate < dist[v]) {
                dist[v] = candidate;
                parent[v] = (int)u;
            }
        }
    }
    return DIJKSTRA_OK;
}

DIST_INF is a reserved sentinel, so every edge weight and finite path distance must be strictly below INT64_MAX. The status distinguishes an invalid interface, a negative edge, and an unrepresentable sum. The fixed 128-vertex limit also keeps int parent[] labels representable.

Priority Queues

With adjacency lists and a binary heap:

• every vertex’s final useful entry is extracted once;
• up to E successful relaxations insert entries;
• heap operations cost O(log V) with decrease-key, or O(log E)=O(log V) for lazy duplicates on simple graphs;
• total time is O((V+E) log V), commonly O(E log V) for connected graphs;
• space is O(V+E) including graph and potentially stale heap entries.

For dense graphs, Theta(V^2) array-based selection can outperform a heap because E=Theta(V^2) and memory access is simpler. For integer weights in a bounded range, specialized bucket queues can improve the bound.

Stopping when the target is extracted with its current key is safe for a single-pair query; stopping when it is first inserted is not.

Bellman-Ford

Bellman–Ford permits negative edges and detects reachable negative cycles. It relaxes every edge for V-1 rounds.

BELLMAN-FORD(G, source):
    initialize distances
    repeat V-1 times:
        changed = false
        for each edge (u,v,w):
            changed |= RELAX(u,v,w)
        if not changed: break
    for each edge (u,v,w):
        if it can still relax:
            report a reachable negative cycle

Round Invariant

After round i, every vertex whose shortest path uses at most i edges has its correct distance.

• At round zero, only the source’s zero-edge path is known.
• Suppose the claim holds after round i-1. Take a shortest path of at most i edges to v, ending with (u,v). Its prefix to u uses at most i-1 edges and is correct by induction. During round i, relaxing (u,v) establishes the correct candidate for v.

A simple shortest path in a V-vertex graph contains at most V-1 edges. If no reachable negative cycle exists, every finite shortest path can be simple, so V-1 rounds suffice.

Bellman Trace

Take edges S->A=4, S->B=5, A->B=-2, B->C=3, and A->C=4. To expose why several rounds may be needed, scan them in the order B->C, A->B, S->A, S->B, A->C:

The shortest path to C uses three edges and appears by the third round. A friendlier edge order could propagate through several edges in one round because the implementation updates in place. The invariant promises that paths of at most i edges are correct after round i; it does not promise that longer paths remain unknown until later. This distinction makes the proof independent of edge-list order.

Bellman–Ford in C

#include <stdbool.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    size_t from;
    size_t to;
    int64_t weight;
} DirectedEdge;

typedef enum {
    BELLMAN_OK,
    BELLMAN_INVALID,
    BELLMAN_OVERFLOW,
    BELLMAN_NEGATIVE_CYCLE
} BellmanStatus;

BellmanStatus bellman_ford(const DirectedEdge edges[], size_t edge_count,
                           size_t vertex_count, size_t source,
                           int64_t dist[], int parent[]) {
    if (source >= vertex_count || dist == NULL || parent == NULL ||
        (edge_count > 0U && edges == NULL) ||
        vertex_count - 1U > (size_t) INT_MAX) {
        return BELLMAN_INVALID;
    }
    for (size_t i = 0; i < edge_count; i++) {
        if (edges[i].from >= vertex_count || edges[i].to >= vertex_count) {
            return BELLMAN_INVALID;
        }
    }
    for (size_t v = 0; v < vertex_count; ++v) {
        dist[v] = DIST_INF;
        parent[v] = -1;
    }
    dist[source] = 0;

    for (size_t round = 1; round < vertex_count; ++round) {
        bool changed = false;
        for (size_t i = 0; i < edge_count; ++i) {
            size_t u = edges[i].from;
            size_t v = edges[i].to;
            int64_t candidate = 0;
            if (dist[u] == DIST_INF) {
                continue;
            }
            if (!safe_add(dist[u], edges[i].weight, &candidate) ||
                candidate == DIST_INF) {
                return BELLMAN_OVERFLOW;
            }
            if (candidate < dist[v]) {
                dist[v] = candidate;
                parent[v] = (int)u;
                changed = true;
            }
        }
        if (!changed) {
            break;
        }
    }

    for (size_t i = 0; i < edge_count; ++i) {
        size_t u = edges[i].from;
        size_t v = edges[i].to;
        int64_t candidate = 0;
        if (dist[u] == DIST_INF) {
            continue;
        }
        if (!safe_add(dist[u], edges[i].weight, &candidate) ||
            candidate == DIST_INF) {
            return BELLMAN_OVERFLOW;
        }
        if (candidate < dist[v]) {
            return BELLMAN_NEGATIVE_CYCLE;
        }
    }
    return BELLMAN_OK;
}

The function validates all endpoints before any relaxation, including when V=1 and the main rounds are skipped. It reserves INT64_MAX for infinity and reports an unrepresentable finite sum as BELLMAN_OVERFLOW. Time is O(VE) and extra state is O(V); early exit improves settled instances but not the worst-case bound.

Negative Cycles

A relaxation on the extra pass proves a reachable negative cycle affects some route, because any improvement would require a walk longer than V-1 edges; such a walk repeats a vertex, and continued improvement implies a negative repeated cycle.

To recover one cycle:

1. remember a vertex x relaxed during the extra pass;
2. follow parent exactly V times, ensuring entry into the cycle;
3. continue following parents until that vertex repeats;
4. reverse the sequence if forward edge order is desired.

The basic status says some reachable negative cycle exists. It does not mean every reachable vertex has distance -infinity. To mark all affected vertices, start from vertices relaxable on the extra pass and traverse forward; all vertices reachable from them have no finite minimum.

An unreachable negative cycle does not affect single-source distances and should not cause Bellman–Ford to fail for that source; the dist[u] != INF guard ensures this.

For a concrete cycle, use S->A=1, A->B=2, B->C=2, and C->A=-6. The cycle weight is 2+2-6=-2. Each additional trip around it reduces the costs to A, B, and C by two, so none has a finite minimum. If C->T=4 is present, T is also unbounded below even though it does not lie on the cycle: take the cycle repeatedly, then exit to T.

A useful failure result includes more than a Boolean flag:

• a recovered directed cycle whose edge weights sum to a negative value;
• the vertices reachable from one or more such cycles, marked as having distance -infinity;
• ordinary finite or unreachable states for all unaffected vertices.

The cycle is a checkable certificate. The affected-set traversal explains which queries have no finite answer. Code that returns its partially decreasing numeric labels as if they were distances exposes iteration-count artifacts rather than graph properties.

Floyd-Warshall

Floyd–Warshall computes all-pairs shortest paths with dynamic programming. Let:

be the shortest path from i to j whose internal vertices come only from {0,...,k-1}. When allowing vertex k, an optimal path either avoids k or passes through it:

The table can be updated in place:

initialize dist[i][i] = 0
initialize dist[u][v] = minimum direct edge weight u->v
initialize other cells = infinity

for k = 0 .. V-1:
    for i = 0 .. V-1:
        for j = 0 .. V-1:
            if i->k and k->j are finite:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Floyd Update

Suppose initially A->B=3, B->C=-2, A->C=8. When B becomes an allowed intermediate:

dist[A][C] = min(8, dist[A][B] + dist[B][C])
           = min(8, 3 + (-2))
           = 1

The algorithm does not need to know how many edges the path contains; it organizes possibilities by their highest-indexed allowed intermediate.

C17 Core

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef enum {
    FLOYD_OK,
    FLOYD_INVALID,
    FLOYD_OVERFLOW
} FloydStatus;

FloydStatus floyd_warshall(
    size_t n, int64_t dist[SP_MAX_VERTICES][SP_MAX_VERTICES],
    int next[SP_MAX_VERTICES][SP_MAX_VERTICES]) {
    if (n > SP_MAX_VERTICES || dist == NULL || next == NULL) {
        return FLOYD_INVALID;
    }

    for (size_t k = 0; k < n; ++k) {
        for (size_t i = 0; i < n; ++i) {
            if (dist[i][k] == DIST_INF) {
                continue;
            }
            for (size_t j = 0; j < n; ++j) {
                if (dist[k][j] == DIST_INF) {
                    continue;
                }
                int64_t candidate = 0;
                if (!safe_add(dist[i][k], dist[k][j], &candidate) ||
                    candidate == DIST_INF) {
                    return FLOYD_OVERFLOW;
                }
                if (candidate < dist[i][j]) {
                    dist[i][j] = candidate;
                    next[i][j] = next[i][k];
                }
            }
        }
    }
    return FLOYD_OK;
}

Initialization for path recovery sets next[u][v]=v for a direct edge and -1 when unreachable; set next[i][i]=i. Reconstruct (u,v) by repeatedly assigning u=next[u][v] until u==v.

DIST_INF represents no path, so initialization must reserve that value and every finite direct or derived distance must be representable below it. The function returns FLOYD_OVERFLOW instead of silently ignoring an unrepresentable improving path. Time is Theta(V^3) and distance storage is Theta(V^2). After completion, dist[v][v] < 0 exactly when v can reach and return through a negative cycle. Pairs (i,j) affected by negative cycles are those for which some negative-diagonal vertex k is reachable from i and can reach j.

All-Pairs Paths

Floyd–Warshall is attractive for dense graphs, negative edges without acceptable negative-cycle ambiguity, and modest V. Alternatives include:

• run BFS from every source for unweighted graphs: O(V(V+E));
• run Dijkstra from every source for nonnegative sparse graphs: O(V(V+E) log V) with a standard binary-heap implementation, simplifying to O(VE log V) when E = Omega(V);
• use Johnson’s algorithm for sparse graphs with negative edges but no negative cycles: one Bellman–Ford reweighting plus Dijkstra from every source.

Johnson chooses vertex potentials h(v) so reweighted edges

are nonnegative while all path comparisons are preserved—the potential terms telescope along a path. It combines algorithms rather than accepting Floyd–Warshall’s cubic dense bound.

To obtain the potentials, add a temporary super-source q with a zero-weight edge to every original vertex and run Bellman–Ford from q. Set h(v)=delta(q,v). For every edge (u,v), shortest-path optimality gives h(v) <= h(u)+w(u,v), hence:

Now consider A->B=-2, A->C=4, and B->C=3. Bellman–Ford from the super-source yields h(A)=0, h(B)=-2, and h(C)=0. The reweighted edges are:

Dijkstra can now run from every source. For any path from s to v, all internal potential terms cancel, so w'(P)=w(P)+h(s)-h(v). Convert a computed distance back with:

Johnson stops if the preliminary Bellman–Ford run detects a negative cycle. An implementation must use checked arithmetic in both reweighting and conversion; mathematically nonnegative reweighted values do not prevent a finite machine integer from overflowing.

Path Queries

The requested query shape can matter as much as the weight restriction.

• For one source and one target, Dijkstra may stop when the target is extracted with its current minimum label—not when it is first inserted. Bellman–Ford generally cannot make the same early-finalization claim.
• For several sources seeking the closest source-to-vertex distance, add a super-source with zero-weight edges to the real sources, or initialize the queue with all of them at distance zero. The result is equivalent to taking the minimum over independent source distances.
• For many sources on a fixed sparse graph, preprocessing and repeated Dijkstra or Johnson may beat a dense all-pairs table in memory.
• For repeated path reconstruction, storing parents per source costs Theta(V^2) across all sources, even if distance computation itself uses sparse adjacency lists.
• If edges change, an old distance remains an upper bound after a weight decrease only when its represented path is still valid, and may become infeasible after deletion or increase. General dynamic shortest paths require more than rerunning relaxation from the edited endpoint.

Estimate the number of queries before selecting a representation. A theoretically faster single-source method can lose overall if every query rebuilds an index or if its output omits paths that the application later needs.

Path Preconditions

These conditions are not implementation notes; they are the exact hypotheses used in the correctness proofs.

Choosing a Path Method

Ask in order:

1. Are edges unweighted or unit cost? Use BFS. One common positive cost is equivalent after scaling; equal negative costs do not satisfy the model.
2. Is the graph a DAG? Use topological relaxation, even with negative edges.
3. Are all weights nonnegative? Use Dijkstra for one/few sources.
4. Can negative edges occur? Use Bellman–Ford for one source and cycle detection.
5. Do you need every pair and is V moderate or the graph dense? Use Floyd–Warshall.
6. Do you need every pair in a large sparse graph with negative edges but no negative cycles? Consider Johnson.

Also account for representation, numeric range, whether paths or only distances are needed, and whether the graph changes between queries.

Path Pitfalls

• Applying Dijkstra to negative weights because sample inputs happened to work.
• Using BFS for arbitrary weights or Dijkstra when all weights are unit and BFS is simpler.
• Representing “no edge” with weight zero and losing legitimate zero-weight edges.
• Adding to infinity or overflowing a finite distance.
• Updating a distance without its parent or next entry.
• Stopping Dijkstra when a target is inserted rather than when its current minimum is extracted.
• Running only one Bellman–Ford pass; edge-list order then determines how far information propagates.
• Reporting every negative cycle in the graph as a single-source failure, even when unreachable.
• Confusing a shortest-path tree with an MST.
• Running topological relaxation without verifying that the order includes all vertices.
• Assuming shortest paths are unique; equal-cost alternatives can produce different valid parents.

Path Review

• Relaxation replaces a current distance upper bound when an edge gives a cheaper actual path.
• Parent or next matrices recover paths, while infinity and negative-cycle states require separate handling.
• DAG shortest paths use topological order and permit negative edges in Theta(V+E) time.
• Dijkstra is greedy and correct only when weights are nonnegative.
• Bellman–Ford uses up to V-1 full relaxation rounds and detects reachable negative cycles with one extra pass.
• Floyd–Warshall is an all-pairs dynamic program over allowed intermediate vertices and takes Theta(V^3) time.
• The best algorithm follows from edge-weight structure, graph structure, query scope, representation, and numeric requirements.

Path Problems

Path Vocabulary

1. Define delta(s,v) for unreachable vertices and for vertices affected by reachable negative cycles.
2. State four invariants preserved by safe relaxation.
3. Identify the precise assumption used by Dijkstra’s greedy proof.
4. Why are V-1 Bellman–Ford rounds sufficient without reachable negative cycles?

Algorithm Traces

5. Trace Dijkstra on the worked graph, but add edge C->E=4. Record stale heap entries and recovered path to E.
6. Trace Bellman–Ford by rounds on S->A=4, S->B=5, A->B=-2, B->C=3, A->C=4 under two different edge-list orders.
7. Fill every Floyd–Warshall matrix for a three-vertex graph with A->B=2, B->C=-1, C->A=4, A->C=8.

Path Proofs

8. Prove the optimal-subpath property by replacement.
9. Prove the DAG relaxation invariant by induction over topological order.
10. Prove that if no distance changes in a Bellman–Ford round, no later round can change one.
11. Prove that Johnson reweighting preserves which path between fixed endpoints is shortest.

Distance Faults

12. Construct a three-vertex counterexample to Dijkstra with one negative edge.
13. Find an input that overflows int in dist[u]+weight and causes an apparently shorter negative result.
14. A Floyd–Warshall implementation places k in the innermost loop. Find a graph where its one-pass result depends incorrectly on update order.

Path Programming

15. Implement adjacency-list Dijkstra with lazy heap entries and explicit negative-edge validation.
16. Extend Bellman–Ford to recover one reachable negative cycle and mark every vertex whose distance is unbounded below.
17. Initialize and use a next matrix to print actual Floyd–Warshall paths, including unreachable and negative-cycle-affected cases.

Path Scenarios

18. Select algorithms for: unit-weight social links; a project DAG with gains and losses; nonnegative road travel times; currency-conversion edges that may reveal arbitrage; and dense all-pairs latency data.
19. Design an interface that cannot confuse unreachable, arithmetic overflow, invalid input, finite distance, and negative-cycle results.
20. A graph changes one edge weight between many shortest-path queries. Explain why recomputing may be acceptable for small graphs and what information an incremental algorithm would need to repair.

Path Extensions

21. Derive a shortest-path algorithm for weights only 0 or 1 using a deque. Prove why inserting zero-weight relaxations at the front and one-weight relaxations at the back preserves extraction order.
22. Show how to find a shortest directed cycle in a graph with nonnegative weights by removing or considering one edge and solving an appropriate reverse path problem.