All-pairs shortest-paths problem

Given a weighted directed graph $G=(V,E)$ and $w(v,u)$ being the weight of edge $(v,u)$, we want to either find:

• information whether $G$ contains a negative cycle; if it doesn’t,
• an $n\times n$ matrix $D=(d_{i,j})$ such that $d_{i,j}$ is equal to $\delta (i,j)$ (shortest-path from node $i$ to node $j$); and shortest-paths trees, one from each node in graph

  We skip computation of shortest-paths trees.

Solving the problem by repeatedly applying single-source shortest-paths algorithm

• If all edge weights are non-negative:
  • Use Dijkstra’s algorithm
  • Total running time is $n\times O(\min \{m\log n,n^2\})=O(\min \{nm\log n,n^3\})$
  • No method with a better (worst-case) running time is known
• In general case, when edge weights may be negative:
  • We may use Bellman-Ford algorithm Total running time is $n\times O(nm)=O(n^{2}m)$ This is $\Theta (n^4)$ if $m=\Theta (n^2)$
  • Floyd-Warshall algorithm: $\Theta (n^3)$
  • Johnson’s algorithm: $O(nm\log n)$

Changing weights of edges without changing shortest-paths

Say we have a graph as follows, and we want to change the weight of edges (ideally without removing negative weights) without changing shortest paths? Adding the same (large) number to the weight of each edge doesn’t work. In Johnson’s algorithm, we add and subtract on each edge:

Johnson’s algorithm

The main idea behind Johnson’s algorithm is that it reduces the general case (where edge weights may be negative) to the case where all edge weights are non-negative.

Re-weighting: compute new edge weights $\hat{w}$ with properties:

1. For all $u,v\in V$, shortest path from $u$ to $v$ using original weights $w$ is also a shortest path from $u$ to $v$ using the new weights $\bar{w}$
2. $\bar{w}(u,v)\ge 0$ for each $(u,v)\in E$

Explaining re-weighting

General idea for re-weighting:

• for each node $v\in V$, assign a number $h(v)$ to $v$
• for each $(v,u)\in E$, let $\hat{w}(u,v)=w(u,v)+h(u)-h(v)$

For any numbers $h(v)$, the new edge weights satisfy Property 1. If no negative cycle in $G$, then we can find numbers $h(v)$ which also satisfy Property 2.

For any $P=(v_1,v_2,\dots ,v_k)$:

$$\begin{array}{rl}\hat{w}(P)& =\hat{w}(v_1,v_2)+\hat{w}(v_2,v_3)+\dots +\hat{w}(v_{k-1},v_k)\\ & =w(v_1,v_2)+h(v_1)-h(v_2)+w(v_2,v_3)+h(v_2)-h(v_3)+\dots +w(v_{k-1},v_k)+h(v_{k-1})-h(v_k)\\ & =w(v_1,v_2)+w(v_2,v_3)+\dots +w(v_{k-1},v_k)+h(v_{k-1})+h(v_1)-h(v_k)\\ & =w(P)+h(v_1)-h(v_k)\end{array}$$

Thus when we change the edge weights from $w$ to $\hat{w}$, then for each pair of nodes $u$ and $v$, the weight of each path from $u$ to $v$ changes by the same amount: $h(u)-h(v)$

Hence a path $P$ is a shortest path from $u$ to $v$ according to weights $w$, if and only if, $P$ is a shortest path from $u$ to $v$ according to weights $\hat{w}$.

We also have, from $(\ast )$: $\hat{\delta }(u,v)=\delta (u,v)+[h(u)-h(v)]$.

Example: computation of new edge weights

Johnson's Algoithm

def johnson(G, w):
	(V, E) = G
	
	G' = G # clone the graph
	(V', E') = G'
	V' = V | {s} # s is a new node
	E' = E | {(s, v) | v in V} # edges from s to all v
	
	for v in V:
		w(s, v) = 0
	
	if not bellman_ford(G', w, s):
		# terminate: input graph G contains negative cycle
	else: # bellman_ford has computed values δ(s,v)
		for v in V:
			h(v) = δ(s, v)
		
		w' = w # clone weights
		for (u, v) in E:
			w'(u, v) = w(u, v) + h(u) - h(v)
		
		for u in V:
			dijkstra(G, w', u) # compute δ(u, v) for all v in V
			
			for v in V:
				d_uv = δ(u, v) - [h(u) - h(v)]
		
	return D = d_uv

Correctness of Johnson's algorithm

1. Input graph $G$ contains a negative cycle, if and only if, there is a negative cycle in graph $G^{\prime }$ reachable from $s$. This means the algorithm correctly identifies whether the input graph has a negative cycle.
2. For each edge $(u,v)$ in $G$, the new weight $\hat{w}(u,v)$ assigned to this edge in Johnson’s algorithm is non-negative. $\boxed{\delta (s,u)+w(u,v)\ge \delta (s,v)}$ (Triangle inequality for shortest-path weights) so $\hat{w}(u,v)=w(u,v)+h(u)-h(v)=w(u,v)+\delta (s,u)-\delta (s,v)\ge 0$ Non-negative weights imply that the algorithm correctly computes $\delta (u,v)$ for any pairs of vertices.
3. For any numbers $h(.)$ and for each pair of nodes $u$ and $v$ in $G$: $\delta (u,v)=\delta (u,v)=[h(u)-h(v)]$ Thus the algorithm correctly computes $\delta (h,v)$ for all pairs of vertices.

Point-to-point shortest-paths in geographical networks

Geographical networks: geographical coordinates of nodes are known; weights of edges are at least straight-line (geographical) distances between the nodes

Dijkstra’s for single-source single-destination

We can run in parallel, two Dijkstra’s computations, one from the source and one from the destination(s) (considering edges backward). We stop when shortest $s\to d$ path is found. We may or may not check the whole network.

However, we need to figure out if the combined path (one part from the shortest-path tree from $s$ and the other part from the shortest-path tree to $d$) is the shortest $s-d$ path.

Dijkstra’s for ‘geographical’ networks (basis of A* algorithm)

Given the nodes are geographical places and we know their coordinates: the weights of edges are at least straight-line distances between the nodes. We want to consider this information to speed-up Dijkstra’s computation for shortest source-destination path.

We can use re-weighting of edges to prioritise those which are ‘geographically’ closer to the destination, we use $h(v)=-\text{dist}(v,d)$ where $\text{dist}(v,d)$ is the straight-line distance from node $v$ to destination $d$.

As the search is directed towards the destination, not many additional edges (away from the shortest path) are considered. This can lead to considerable improvement in average running time.

Worst-case running time remains as in the main Dijkstra's algorithm for single-source (all destinations) case.

Correctness of re-weighting with distance

Re-weighting by straight-line distances to destination works because the straight-line distances satisfy the triangle inequality: $\text{dist}(u,d)\le \text{dist}(u,v)+\text{dist}(v,d)\le w(u,v)+\text{dist}(v,d)$ So the new weights are non-negative: $\hat{w}(u,v)=w(u,v)-\text{dist}(u,d)+\text{dist}(v,d)\ge 0$ The straight-line distances are used here as (under)-estimates of the shortest-path weights.

A* search algorithm

The modified Dijkstra’s algorithm with re-weighting using a cost estimate function $b$ is the A search algorithm*. In A*, the function $b(.)$ is called a heuristic function, often denoted by $h(.)$.

The property of the heuristic function $h$ which guarantees that when the target $t$ is taken from $Q$, then the shortest path to $t$ is computed: For each edge $(u,v)$, $h(u)\le w(u,v)+h(v)$.

A heuristic function $h(.)$ which satisfies this property is called consistent or monotone, and is equivalent to the property that all new weights $\hat{w}(u,v)=w(u,v)-h(u)+h(v)$ are non-negative.

Slides 12-18 this is all waffle?