(Single-source) shortest-paths problem

Preamble

Given a directed graph, $G=(V,E)$; $|V|=n,|E|=m$:

• The weight of an edge $(u,v)$ is $w(u,v)$
• The source vertex is $s\in V$

We want to compute the shortest paths, that is, the paths with the smallest total weights, from $s$ to all other vertices.

In this graph, we have two shortest-paths from $s$ to $v$, $\delta (s,v)=14$. Unreachable nodes have an infinite cost, $\delta (s,y)=+\infty$.

Path

A path $p=⟨v_1,v_2,\dots ,v_k,v_{k+1}⟩$ is a sequence of vertices where $(v_i,v_{i+1})$ is an edge for each $i=1,2,\dots ,k$.

Link to original

Weight (path)

The weight of a path $p=⟨v_1,v_2,\dots ,v_k,v_{k+1}⟩$ is $w(p)=w(v_1,v_2)+w(v_2,v_3)+\dots +w(v_k,v_{k+1})$.

Link to original

Shortest-path weight

The shortest-path weight (distance) from $u$ to $v$ is $\delta (u,v)=\{\begin{array}{l}\text{min }w(p)\text{ over all }p\text{ from }u\text{ to }v,\text{ if there is any such path;}\\ +\infty ,\text{ if there is no path from }u\text{ to }v\end{array}$

Link to original

Shortest path

A shortest path from $u$ to $v$ is any path $p$ from $u$ to $v$ with weight $w(p)=\delta (u,v)$.

Link to original

A subpath of a shortest path, is itself, a shortest path.

Triangle inequality

For each edge $(u,v)\in E$: $\delta (s,v)\le \delta (s,u)+w(u,v)$

Holds also if $u$ or $v$ is not reachable from $s$.

Weights of edges may be negative

Example: negative weights in an application

We use an example from financial analysis, a graph of exchange rates.

Find paths maximising exchange rates:	Find shortest paths:

• For an edge $(x,y):\gamma (x,y)=$ exchange rate from $x$ to $y$, e.g. $\gamma (S,D)=1.6$.
• Set the weight of the edge $(x,y)$: $w(x,y)=-\ln (\gamma (x,y))$ (we use natural log, but any fixed base $>1$ works) e.g. $w(S,D)=-\ln (\gamma (S,D))=-\ln (1.6)\approx -0.47$
• A path from $v$ to $u$ maximises the combined exchange rate from $v$ to $u$, if and only if, this is a shortest path from $v$ to $u$ according to these edge weights.
• If $\gamma (x,y)>1$, then $w(x,y)<0$. We cannot avoid negative weights here, so we solve shortest-paths problem in a graph with (some) edge weights negative.

For a path $P=⟨v_1,v_2,\dots ,v_k⟩$:

Negative weight cycles

If there is a negative cycle on a path from $s$ to $v$, then by going increasingly many times around a cycle, we get paths from $s$ to $v$ of arbitrarily small (negative) weights.

If there is a negative cycle on a path from $s$ to $v$, then by convention, $\delta (s,v)=-\infty$.

In this case, we give up. Computing shortest simple paths in graphs containing negative cycles is NP-hard. (computationally difficult by reduction from Hamiltonian Path problem)

As such we only consider shortest-paths algorithms which:

• Compute shortest paths for graphs with no negative cycles reachable from source
• For graphs with negative cycles, detect this and do not compute anything else.

Representing computed shortest paths

If there is no negative cycle reachable from $s$, then shortest paths from $s$ to all nodes reachable from $s$ are well defined and can be represented by a shortest-paths tree which is a tree rooted at $s$ such that for any node $v$ reachable from $s$, the tree path from $s$ to $v$ is a shortest path from $s$ to $v$ (there may be other shortest paths which are not included in the tree).

A shortest-paths tree $T$ can be represented by an array $PARENT[v],v\in V$ in $\Theta (n)$ space (memory), where $n$ is the number of nodes in the graph.

$PARENT[v]$ is the predecessor of node $v$ in tree $T$.

An explicit representation of shortest-paths from $s$ with each path represented as a full sequence of all its edges would take $\Theta (n^2)$ space in the worst case.

Output of a shortest-paths algorithm

We compute the shortest-path weights and a shortest-paths tree, or detect a negative cycle reachable from $s$.

Relaxation Technique

For each node $v$, we maintain $d[v]$ the shortest-path estimate for $v$ (upper bound on weight of shortest path from $s$ to $v$) and $PARENT[v]$ the current predecessor of node $v$.

The relaxation technique consists of repeated repeated ‘relaxation’ of edges until we stop making any changes.

Relaxation Algorithm

def relax_init(G, s):
	'''
	Populate table with initial values for parents and distances
	'''
	
	d[s] = 0
	PARENT[s] = None
	
	for node v in V - {s}:
		d[v] = Infty
		PARENT[v] = None
 
def relax_edge(u, v, w):
	'''
	Attempt to relax the edge (u, v) given weights
	'''
	
	if d[v] > d[u] + w(u, v):
		d[v] = d[u] + w(u, v)
		PARENT[v] = u

Properties of Relaxation technique

1. Non-increasing shortest-path estimates For each node $v$, the shortest-path estimate $d[v]$ can only ever decrease.
2. For each node $v$, the shortest-path estimate $d[v]$ is always either equal to $\infty$ (at the beginning) or equal to the weight of some path from $s$ to $v$ (by induction).
3. Upper bound property For each node $v$, we always have $d[v]\ge \delta (s,v)$
4. No-path property If there is no path from $s$ to $v$, then we always have $d[v]=\delta (s,v)=\infty$
5. Convergence property If $(s,\dots ,u,v)$ is a shortest path from $s$ to $v$ and if $d[u]=\delta (s,u)$ at any time prior to relaxing edge $(u,v)$, then $d[v]=\delta (s,v)$ at all times afterwards.
6. Path-relaxation property If $p=(v_0,v_1,\dots ,v_k)$ is a shortest path from $s=v_0$ to $v_k$ and we relax the edges of $p$ in the order $(v_0,v_1),(v_1,v_2),\dots ,(v_{k-1},v_k)$, then $d[v_k]=\delta (s,v_k)$. This property holds regardless of any other relaxation steps that occur, even if they are intermixed with relaxations of the edges of path $p$.
7. For each edge $(u,v)$ in the current parent subgraph (that is $u=PARENT[v]$): $d[u]+w(u,v)\le d[v]$

   By induction, see LGT.

8. If the graph contains no negative-weight cycle reachable from $s$, then:

• the parent subgraph is always a tree $T$ rooted at $s$
• for each node $v$ in tree $T$, $d[v]\ge$ the weight of the path in $T$ from $s$ to $v$

• $\text{red}$ part of current parent tree (near source vertex $s$) is already part of computed shortest-paths tree
• $\text{blue}$ part may change during subsequent relax operations

By induction, see LGT.

9. When $d[v]=\delta (s,v)$ for all $v\in V$ then:

   • the parent subgraph is a shortest-paths tree rooted at $s$ (by $8$)
   • no further updates possible (by $3$)

10. The computation can progress, if the shortest-paths weights are not reached yet:

    1. there exists a vertex $x\in V$ such that $d[x]>\delta (s,x)$, if and only if,
    2. there exists an edge $(u,v)\in E$ such that $d[v]>d[u]+w(u,v)$ (that is, another effective relax operation is possible)

    $(b)\Rightarrow (a)$: from ($3$) and Triangle inequality $(a)\Rightarrow (b)$: assume $d[x]>\delta (s,x)$ for some node $x$ (so $\delta (s,x)<+\infty$)

    • In the case $\delta (s,x)>-\infty$ (no negative cycle on a path from $s$ to $x$) Consider shortest $s$-to-$x$ path $P$: Must have an edge $(u,v)$ on $P$ such that $d[u]=\delta (s,u)$ but $d[v]>\delta (s,v)$. For such an edge: $d[v]>\delta (s,v)=\delta (s,u)+w(u,v)=d[u]+w(u,v)$.
    • In the case $\delta (s,x)=-\infty$ for some vertex $x$: (consider a path $(s,u_1,\dots ,u_k,v_1,\dots ,v_r,v_1)$ where $(v_1,\dots ,v_r,v_1)$ is a negative cycle)

Incomplete

The last point in (10) is an “exercise”

Summary for cases with/without negative cycles

If no negative cycle is reachable from $s$:

• only finite many effective relax operations during computation.
• PARENT-subgraph is a tree always rooted at $s$ (property 8)
• when eventually no effective relax operation possible, then for each node $v$, $d[v]=\delta (s,v)$ (property 10) and PARENT pointers form a shortest-paths tree (property 9)

If a negative cycle is reachable from $s$:

• there is always an edge $(u,v)$ such that $d[v]>d[u]+w(u,v)$, that is, effective RELAX operation is not always possible (property 10)
• PARENT subgraph eventually contains a cycle (not easy to prove; omitted)
• we can detect the existence of a negative cycle by periodically checking if PARENT pointers form a cycle

Bellman-Ford algorithm

The running time is $\Theta (mn)$ where $n$ is the number of nodes and $m$ is number of edges. Worst case running time of any algorithm for the single-source shortest-paths problem with negative weights is $\Omega (mn)$.

Bellman-Ford Algorithm

def bellman_ford(G, w, s):
	'''
	Algorithm to solve single-source shortest-paths problem
	Based on the relaxation technique
	'''
	relax_init(G, s) # from relaxation technique
 
	(V, E) = G
	n = |V|
	
	# nodes indexed from 1
	for i = 1 to (n - 1):
		for edge (u, v) in E: # consider in arbitrary order
			relax_edge(u, v, w) # from relaxation technique
	
	for edge (u, v) in E:
		if d[v] > d[u] + w(u, v):
			return False # negative cycle reachable from s
	
	return True # no negative cycles

Correctness of Bellman-Ford algorithm

• If there is a negative cycle reachable from $s$, then Bellman-Ford algorithm returns false because an effective relax operation will always be possible. In this case, the algorithm is correct.

• If no negative cycle reachable from $s$, then the following claim is true: At the termination of loop 1, $d[v]=\delta (s,v)$ for each vertex $v\in V$.

  Lemma: if the length (no. of edges) of a shortest (simple) path from $s$ to a node $v$ is $k$, then at the end of iteration $k$ (of main loop 1) in the Bellman-Ford algorithm, $d[v]=\delta (s,v)$.

  This lemma follows from the path-relaxation property of the relaxation technique (property 6).

  This lemma implies the claim states above because each simple shortest path has at most $n-1$ edges.

  The claim implies that at the termination of loop 1, no effective relax operation is possible so the algorithm returns true.

  At the end of the computation:

  1. array $d$ contains the shortest path distances from $s$ to all other nodes;
  2. array $PARENT$ contains a shortest-paths tree with node $s$ as the source (from above and property 9 of relaxation technique)

  That is, in the case of “no negative cycles”, the algorithm is also correct.

Speeding up Bellman-Ford algorithm

• Try to decrease number of iterations of loop 1:
  • If no effective relax operations in the current iteration, then terminate (the shortest-path weights are already computed)
  • Periodically check (at end of each iteration of loop 1) if PARENT pointers form a cycle. If they do, terminate and return FALSE: there is a negative cycle reachable from $s$
• Try to decrease the running time of one iteration of loop 1: consider only edges which may give effective relax operations.
  • Vertex $u$ is active if the edges outgoing from $u$ have not been relaxed since the last time $d[u]$ has been decreased.
  • Perform RELAX on edges outgoing from active vertices.

Bellman-Ford algorithm with FIFO Queue

def bellman_ford_fifo(G, w, s):
	'''
	Algorithm to solve single-source shortest-paths problem
	Builds on Bellman-Ford with some optimisations to cut operations
	'''
	relax_init(G, s) # from relaxation technique
	
	(V, E, Adj) = G
	
	Q = {} # empty queue
	q.enqueue(s)
	
	while Q not empty:
		u = q.dequeue()
		
		for v in Adj[u]:
			if relax_edge(u, v, w):
				# this may be implemented in relax_edge
				# OR relax_edge may return True to trigger
				# this condition:
				if v not in Q:
					Q.enqueue(v)
	
	return True