vii. Shortest Path Techniques

Problems that reduce to shortest paths after a construction: systems of difference constraints, graphs with range edges (segment-tree graphs), XOR-weighted walks (cycle basis), shortest cycles, minimum mean / ratio cycles, and replacement paths (distance when one edge is removed). Shortest paths modulo the smallest coin are in Knapsack.

Difference constraints

$x_v-x_u\le c$ is an edge $u\to v$ of weight $c$. With a virtual source joined to all vertices by weight-0 edges, the Bellman–Ford distances are a solution; a negative cycle means infeasible. The solution found is the componentwise maximum among solutions with all $x\le 0$; for the minimum solution with $x\ge 0$ solve for $y=-x$. Over integers, $x_v-x_u<c$ is $\le c-1$; $x_v-x_u\ge c$ is $x_u-x_v\le -c$.

optional<vector<ll>> diffConstraints(int n, const vector<array<ll, 3>>& E) {   // {u, v, c}: x_v - x_u <= c
    vector<ll> x(n, 0);
    for (int it = 0; it <= n; it++) {
        bool ch = false;
        for (auto [u, v, c] : E) if (x[u] + c < x[v]) x[v] = x[u] + c, ch = true;
        if (!ch) return x;
    }
    return nullopt;
}

Proof: feasibility iff no negative cycle, and maximality

Summing the constraints around a cycle gives $0\le \sum c$, so a negative cycle makes the system infeasible. Without one, shortest distances $d$ from the virtual source exist and satisfy $d_v\le d_u+c$ for every edge, i.e. every constraint, with $d\le 0$. For any solution $y$ with $y\le 0$, induction along a shortest path $s=v_0,v_1,\dots ,v_k=v$ (starting from $y_{v_1}\le 0=d_{v_0}+0$) gives $y_{v_i}\le d_{v_i}$, so $d$ is the componentwise maximum.

Typical: scheduling with “at least / at most $c$ apart”, prefix-sum constraints on 0/1 arrays ($S_r-S_l\in [a,b]$ plus $0\le S_{i+1}-S_i\le 1$), and verifying consistency of relative measurements. If all constraints have the form $x_v-x_u\le c$ with $c\ge 0$ only, Dijkstra applies.

Range edges: segment-tree graph

Edges “vertex $\to$ every vertex in $[l,r)$”, “every vertex in $[l,r)$ $\to$ vertex”, or range $\to$ range: build two segment trees of helper nodes, an out-tree with weight-0 edges parent $\to$ children (reaching a node reaches all its leaves) and an in-tree with weight-0 edges children $\to$ parent. Each range is $O(\log n)$ nodes; range $\to$ range uses one extra hub node. Dijkstra on $O(n+E\log n)$ edges (CF 786B).

struct RangeGraph {
    int n, S = 1; vector<vector<pair<int, ll>>> adj;
    int outNode(int k) const { return k >= S ? k - S : n + k; }        // leaves are the real vertices
    int inNode(int k) const { return k >= S ? k - S : n + S + k; }
    RangeGraph(int n) : n(n) {
        while (S < n) S <<= 1;
        adj.assign(n + 2 * S, {});
        for (int k = 1; k < S; k++) for (int c : {2 * k, 2 * k + 1}) {
            if (c >= S && c - S >= n) continue;
            adj[outNode(k)].push_back({outNode(c), 0}); adj[inNode(c)].push_back({inNode(k), 0});
        }
    }
    vector<int> cover(int l, int r, bool out) const {
        vector<int> res;
        for (l += S, r += S; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res.push_back(out ? outNode(l) : inNode(l)), l++;
            if (r & 1) --r, res.push_back(out ? outNode(r) : inNode(r));
        }
        return res;
    }
    void edge(int u, int v, ll w) { adj[u].push_back({v, w}); }
    void toRange(int u, int l, int r, ll w) { for (int x : cover(l, r, true)) adj[u].push_back({x, w}); }
    void fromRange(int l, int r, int v, ll w) { for (int x : cover(l, r, false)) adj[x].push_back({v, w}); }
    void rangeToRange(int l1, int r1, int l2, int r2, ll w) {
        int hub = sz(adj); adj.push_back({});
        for (int x : cover(l1, r1, false)) adj[x].push_back({hub, w});
        for (int y : cover(l2, r2, true)) adj[hub].push_back({y, 0});
    }
};   // run Dijkstra on adj; the first n entries are the real vertices

Other virtual-node patterns: one node per colour/value (enter with the cost, leave free), one node per divisor for “jump between multiples”, and a node per row/column for “teleport within a row”.

XOR of walks

For an undirected graph with XOR edge weights, the XOR of any walk from $u$ to $v$ equals ${\text{dist}}_u\oplus {\text{dist}}_v$ (along a spanning tree) XOR some combination of fundamental cycle values, and every combination is achievable. So the maximum (or minimum) XOR walk is ${\text{dist}}_u\oplus {\text{dist}}_v$ reduced greedily against a linear basis of the cycle values (CF 845G).

struct XorWalks {
    vector<ull> dist; vector<int> comp; vector<array<ull, 64>> basis;
    static void insert(array<ull, 64>& b, ull x) { for (int i = 63; i >= 0 && x; i--) if (x >> i & 1) { if (!b[i]) { b[i] = x; return; } x ^= b[i]; } }
    XorWalks(int n, const vector<array<ull, 3>>& E) : dist(n), comp(n, -1) {
        vector<vector<pair<int, ull>>> g(n);
        for (auto [u, v, w] : E) g[u].push_back({(int)v, w}), g[v].push_back({(int)u, w});
        for (int s = 0; s < n; s++) {
            if (comp[s] >= 0) continue;
            int id = sz(basis); basis.push_back({}); comp[s] = id; vector<int> st{s};
            while (sz(st)) {
                int u = st.back(); st.pop_back();
                for (auto [v, w] : g[u]) {
                    if (comp[v] < 0) comp[v] = id, dist[v] = dist[u] ^ w, st.push_back(v);
                    else insert(basis[id], dist[u] ^ dist[v] ^ w);
                }
            }
        }
    }
    ull maxXor(int u, int v) const { ull x = dist[u] ^ dist[v]; for (int i = 63; i >= 0; i--) x = max(x, x ^ basis[comp[u]][i]); return x; }
    ull minXor(int u, int v) const { ull x = dist[u] ^ dist[v]; for (int i = 63; i >= 0; i--) x = min(x, x ^ basis[comp[u]][i]); return x; }
};

Proof: walk XORs are tree path XOR plus the cycle space

Any walk’s XOR is the XOR of the edges used an odd number of times; that edge set minus the tree path $u⇝v$ is an even-degree subgraph, hence a combination of fundamental cycles (Cycles), whose XOR value is the XOR of the cycles’ values. Conversely any cycle $C$ in the component can be added to a walk: go from the walk to $C$, around it, and back along the same path (the connecting path cancels). The cycle value of non-tree edge $(a,b,w)$ is ${\text{dist}}_a\oplus {\text{dist}}_b\oplus w$. Greedy reduction from the top bit maximises (minimises) the XOR over the span.

Shortest cycles (girth)

• Unweighted undirected: BFS from every vertex; a non-tree edge $(x,y)$ gives a closed walk of length $d_x+d_y+1$ through the root, and the minimum over all roots is the girth. $O(nm)$. (The walk through a root might not be simple for that root, but the overall minimum is attained by a simple cycle when the root lies on it.)
• Weighted undirected, through a vertex $s$: Dijkstra from $s$, label every vertex by the first edge of its shortest path (“branch”); a non-tree edge $(x,y)$ joining different branches (or touching $s$) gives a cycle through $s$ of length $d_x+w+d_y$.
• Through an edge $(u,v,w)$: $w$ + shortest $u$–$v$ path avoiding that edge.
• Directed: Dijkstra from each $s$; the shortest cycle through $s$ is $\min d_u+w_{us}$. $O(n\cdot m\log n)$; with unit weights BFS, $O(nm)$.

ll girthUnweighted(const vector<vector<int>>& g) {         // undirected, unweighted; LLONG_MAX if acyclic
    int n = sz(g); ll best = LLONG_MAX;
    for (int s = 0; s < n; s++) {
        vector<int> d(n, -1), p(n, -1); queue<int> q; d[s] = 0; q.push(s);
        while (sz(q)) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (d[v] < 0) d[v] = d[u] + 1, p[v] = u, q.push(v);
                else if (p[u] != v) best = min(best, (ll)d[u] + d[v] + 1);   // simple graph assumed
            }
        }
    }
    return best;
}

Proof: the BFS girth bound is exact

Every value recorded is the length of a closed walk containing a cycle, so it is $\ge$ the girth $g$. For a shortest cycle $C$ and $s\in C$, BFS from $s$ gives every vertex of $C$ distance $\le \lfloor g/2\rfloor$ (along $C$), and the cycle contains an edge $(x,y)$ that is not a BFS tree edge with $d_x+d_y+1\le g$ (the edge “opposite” $s$ on $C$). Since every recorded value is $\ge g$, the minimum equals $g$.

Minimum mean cycle (Karp)

${\mu }^{\ast }={\min }_{C}w(C)/|C|$. With $d_k(v)$ = minimum weight of a walk with exactly $k$ edges ending at $v$ (starting anywhere, $d_0=0$):

${\mu }^{\ast }={\min }_v{\max }_{0\le k<n}\frac{d_n(v)-d_k(v)}{n-k}.$

$O(nm)$. For minimum ratio cycles $\sum a_e/\sum b_e$ ($b_e>0$), binary search $\lambda$ and test for a negative cycle with weights $a_e-\lambda b_e$ (also how min mean cycle is often done).

pair<ll, ll> minMeanCycle(int n, const vector<array<ll, 3>>& E) {   // {num, den}; den == 0 if acyclic
    const ll INF = LLONG_MAX / 4;
    vector<vector<ll>> d(n + 1, vector<ll>(n, INF)); d[0].assign(n, 0);
    for (int k = 1; k <= n; k++) for (auto [u, v, w] : E) if (d[k - 1][u] < INF) d[k][v] = min(d[k][v], d[k - 1][u] + w);
    ll bn = 0, bd = 0;                                       // best = bn / bd
    for (int v = 0; v < n; v++) {
        if (d[n][v] >= INF) continue;
        ll wn = 0, wd = 0;                                   // max over k
        for (int k = 0; k < n; k++) if (d[k][v] < INF) {
            ll num = d[n][v] - d[k][v], den = n - k;
            if (!wd || (__int128)num * wd > (__int128)wn * den) wn = num, wd = den;
        }
        if (wd && (!bd || (__int128)wn * bd < (__int128)bn * wd)) bn = wn, bd = wd;
    }
    return {bn, bd};
}

Proof: Karp's formula

Subtracting $\mu$ from every weight subtracts $\mu$ from both sides, so assume ${\mu }^{\ast }=0$: no negative cycles, and some cycle $C$ has weight 0. Let $\delta (v)={\min }_{k<n}{d}_k(v)$, the shortest walk weight to $v$ (shortest walks can be taken with $<n$ edges). A walk of $n$ edges contains a cycle of weight $\ge 0$, so $d_n(v)\ge \delta (v)$, hence ${\max }_k(d_n(v)-d_k(v))\ge d_n(v)-\delta (v)\ge 0$ for every $v$: the right side is $\ge 0$. For equality, take any $x\in C$ and a shortest walk to $x$ with $j<n$ edges, and extend it along $C$ by $n-j$ edges to a vertex $v$. The triangle inequality gives $\delta (v)\le \delta (x)+w(x\to v)$ and $\delta (x)\le \delta (v)+w(v\to x)$ (arcs of $C$), and $w(x\to v)+w(v\to x)=w(C)=0$, so $\delta (v)=\delta (x)+w(x\to v)$: so this $n$-edge walk has weight $\delta (v)$: $d_n(v)=\delta (v)$, and then every term $d_n(v)-d_k(v)\le 0$ with equality at the $k$ attaining $\delta (v)$. So the minimum over $v$ is exactly 0.

Where it shows up: repeatedly finding and cancelling minimum mean cycles is a strongly-polynomial min-cost flow algorithm; negating weights gives the maximum mean cycle; minimum mean cycle on a log-transformed exchange-rate graph finds the best arbitrage rate (not just whether one exists, unlike the plain negative-cycle check); and min/max mean cycle bounds are the standard tool in digital-circuit and pipeline timing verification. The related Karp–Orlin algorithm reuses the same mean-weight machinery for parametric shortest paths.

Replacement paths

Undirected, positive weights: the $s$–$t$ distance after deleting each edge, in $O((n+m)\log n)$. Only edges of one fixed shortest path $P=(e_0,\dots ,e_{k-1})$ matter. For each vertex $v$ let $l_v$ = index of the last path edge on the shortest-path-tree route from $s$ to $v$ that leaves $P$ as late as possible, and $r_v$ symmetric from $t$. A non-path edge $(u,v,w)$ offers detour $d_s(u)+w+d_t(v)$ for all path edges with index in $(l_u,r_v)$: a sweep with a multiset gives every answer. Changing edge $e$‘s weight to $x$ (CF 1163F): $\min (\text{without}(e),d_s(u)+x+d_t(v),d_s(v)+x+d_t(u))$.

struct ReplacementPaths {                                   // edges (u, v, w), w > 0; t reachable from s
    const ll INF = LLONG_MAX / 4; vector<ll> ds, dt, best; vector<int> path, pid; int t;
    vector<ll> dijk(int n, const vector<vector<array<int, 2>>>& g, const vector<array<ll, 3>>& E, int src, vector<int>* pe) {
        vector<ll> d(n, INF); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; d[src] = 0; pq.push({0, src});
        while (sz(pq)) { auto [du, u] = pq.top(); pq.pop(); if (du != d[u]) continue;
            for (auto [v, e] : g[u]) if (du + E[e][2] < d[v]) { d[v] = du + E[e][2]; if (pe) (*pe)[v] = e; pq.push({d[v], v}); } }
        return d;
    }
    ReplacementPaths(int n, const vector<array<ll, 3>>& E, int s, int t) : t(t) {
        int m = sz(E); vector<vector<array<int, 2>>> g(n);
        for (int e = 0; e < m; e++) g[E[e][0]].push_back({(int)E[e][1], e}), g[E[e][1]].push_back({(int)E[e][0], e});
        vector<int> pe(n, -1); ds = dijk(n, g, E, s, &pe); dt = dijk(n, g, E, t, nullptr);
        pid.assign(m, -1);
        for (int c = t; c != s;) { int e = pe[c]; path.push_back(e); c ^= E[e][0] ^ E[e][1]; }
        reverse(all(path)); int k = sz(path);
        for (int i = 0; i < k; i++) pid[path[i]] = i;
        vector<int> ord(n), l(n, k), r(n, -1); iota(all(ord), 0);
        sort(all(ord), [&](int a, int b) { return ds[a] < ds[b]; }); l[s] = -1;
        for (int u : ord) if (ds[u] < INF) for (auto [v, e] : g[u]) if (ds[u] + E[e][2] == ds[v]) l[v] = min(l[v], pid[e] >= 0 ? pid[e] : l[u]);
        sort(all(ord), [&](int a, int b) { return dt[a] < dt[b]; }); r[t] = k;
        for (int u : ord) if (dt[u] < INF) for (auto [v, e] : g[u]) if (dt[u] + E[e][2] == dt[v]) r[v] = max(r[v], pid[e] >= 0 ? pid[e] : r[u]);
        vector<vector<pair<ll, int>>> ev(k + 1);
        for (int e = 0; e < m; e++) if (pid[e] < 0) for (auto [u, v] : {pair{(int)E[e][0], (int)E[e][1]}, pair{(int)E[e][1], (int)E[e][0]}}) {
            if (ds[u] >= INF || dt[v] >= INF || l[u] + 1 > r[v] - 1) continue;
            ll c = ds[u] + E[e][2] + dt[v]; ev[l[u] + 1].push_back({c, 1}); ev[r[v]].push_back({c, -1});
        }
        best.assign(k, INF); multiset<ll> act;
        for (int i = 0; i < k; i++) {
            for (auto [c, a] : ev[i]) { if (a > 0) act.insert(c); else act.erase(act.find(c)); }
            if (sz(act)) best[i] = *act.begin();
        }
    }
    ll without(int e) const { return pid[e] < 0 ? ds[t] : best[pid[e]]; }
};

Proof sketch: the detour intervals

After deleting path edge $e_i$, an optimal replacement path leaves $P$‘s prefix structure at some point and rejoins later; it can be chosen to consist of a shortest $s$–$u$ path, one non-path edge $(u,v)$, and a shortest $v$–$t$ path (a standard exchange: any optimal replacement path contains such an edge crossing from the ”$s$ side” to the ”$t$ side” of the cut defined by $e_i$). The shortest $s$–$u$ route avoids $e_i$ exactly when it leaves $P$ before $e_i$, i.e. $l_u<i$, where taking the route that departs $P$ as late as possible makes $l_u$ well defined via the shortest-path DAG; symmetrically the $v$–$t$ route avoids $e_i$ iff $r_v>i$. So edge $(u,v)$ serves exactly the indices $i\in (l_u,r_v)$, and the sweep takes the minimum over active candidates.