10. Negative Edge Weights and All-Pairs

Bellman-Ford Algorithm

Shortest path with negative edge weights and source vertex

init d(s) = 0, d(v) = +INF for every vertex
for j = 1,..., n
	for (u, v) in edges
		if (u, v) incorrect, correct it
if any d(v) changed on nth iteration
	output negative cycle
else output d(v) for every vertex

Definition of correctness

An edge is correct if it’s actually the shortest path. Else needs update.

All-Pairs Shortest Paths

Given digraph with an negative cycle, compute shortest path distances for every v Compute Bellman-Ford n times: $O(n^4)$

Can we do better? If non-negative edge weights, run Djikstra’s n times

Bad idea: adding constant to all edge weights to make them non-negative

Adding greatest negative number to all edges such that they’re all non-negatives

I originally thought you couldn’t do this because negative edges have different behavior

• Actually because paths with more edges used will be more proportionally increased than paths with less edges, so it doesn’t preserve shortest path

Better idea: feasible potential

Given digraph G with weights w and function $f:V⟹\mathbb{R}$

A transformation of weights that preserves the weights (not just adding a constant C to all).

$$\hat{w}(p)=\sum _{j=1}^{k-1}{w}_{v_j,v_{j+1}}-\oslash (v_j)+\oslash (v_{j+1})$$

Telescoping sum:

$$\hat{w}(p)=\oslash (u)-\oslash (v)+\sum _{j=1}^{k-1}{w}_{v_j,v_{j+1}}$$

For any vertex $s\in V$ the function $\oslash (v)=d_w(s,v)$ defines a feasible potential. So feasible potential is computed shortest path.

Johnson’s Algorithm

For all-pairs shortest paths:

1. Fix $s\in V$, run Bellman-Ford to compute $d(s,v)$ for every vertex
2. Transform weights where ${\hat{w}}_{uv}=w_{uv}+\oslash (u)-{\oslash }_{(}v)$ where $\oslash (u)=d(s,u)$
3. Compute all shortest paths by running Djikstra’s n times with weights $\hat{w}$
4. Output $d_w(u,v)=d_{\hat{w}(w,v)-\oslash (u)-{\oslash }_{(}v)}$

Slight issue: what if there’s no path from s to v (disconnected graph)

• Add connecting edges with largest edge weight (greater than the sum of all pos edge weights in graph)

DP Solution: Floyd-Warshall Algorithm

Compute APSP iteratively by using intermediate vertices (from u to v)

Cases based on whether using current vertex or not. Take minimum of cases for shortest path: $D(u,v,j)=min(D(u,v_j,j-1)+D(v_j,v,j-1),D(u,v,j-1))$

Case 1: use the vertex, so compute shortest path from source to curr and curr to target`

Can probably memoize with hashmap