8.19

Idea. A shortest x → y walk that is forced to visit z must consist of a shortest path x → z followed by a shortest path z → y. Because all edge–weights are positive, these two sub-paths cannot overlap in a way that would allow a cheaper detour.

Algorithm (Dijkstra twice) 1. run Dijkstra(G, x) → distX[·], predX[·] // cost and predecessor from x 2. run Dijkstra(G, z) → distZ[·], predZ[·] // cost and predecessor from z 3. totalLength = distX[z] + distZ[y] 4. construct path: a) follow predX from z back to x (reverse to get x … z) b) follow predZ from y back to z (already z … y) c) concatenate, omitting the duplicate z

Complexity. Each Dijkstra run costs [math]\mathcal{O}((|V|+|E|)\log|V|)[/math] with a binary heap, so the whole algorithm is still [math]\mathcal{O}((|V|+|E|)\log|V|)[/math]. The memory usage is [math]\mathcal{O}(|V|)[/math] for the distance and predecessor arrays.

Correctness proof (sketch). Let P be the path produced by the algorithm and suppose, for contradiction, that there exists a cheaper x → y path P′ that also visits z. Split P′ at its first visit to z into P′₁ (x → z) and P′₂ (z → y). By construction of Dijkstra,     w(P′₁) ≥ distX[z] and w(P′₂) ≥ distZ[y]. Hence w(P′)=w(P′₁)+w(P′₂) ≥ distX[z]+distZ[y] = w(P), contradicting the assumption. Therefore P is optimal.

Python snippet.

import heapq, collections def shortest_via_z(G, x, y, z): def dijkstra(src): dist = {v: float('inf') for v in G} pred = {} dist[src] = 0 pq = [(0, src)] while pq: d,u = heapq.heappop(pq) if d!=dist[u]: continue for v,w in G[u]: nd = d + w if nd < dist[v]: dist[v], pred[v] = nd, u heapq.heappush(pq,(nd,v)) return dist, pred distX,predX = dijkstra(x) distZ,predZ = dijkstra(z) if distX[z]==float('inf') or distZ[y]==float('inf'): return None, float('inf') # no feasible path # rebuild x→z path = [] cur = z while cur!=x: path.append(cur) cur = predX[cur] path.append(x) path.reverse() # rebuild z→y (skip z duplicate) cur = y tail = [] while cur!=z: tail.append(cur) cur = predZ[cur] path.extend(reversed(tail)) return path, distX[z]+distZ[y]

The function returns the required shortest path and its total length.

Back to Chapter 8