Week 2 - Shortest Paths

Shortest path problem

Given a directed graph with edge weights and a start vertex - the shortest path problem is to find the shortest distance between and for every . This is called with the formal definition where is a path that starts at and ends at .

The classic solution to this is Dijkstra’s algorithm which runs in time - however this requires that for all . We are looking at a more generic problem.

Negative weight cycles

If there is a cycle that has negative total weight then the problem is not well defined as you can always extend you path with another loop of the cycle to reduce your weight.

The first step of our algorithm will be looking up if there is such a cycle.

Case 1: No negative weight cycles

In this case you can guarantee that paths will only visit each vertex at most once. So they will use at most edges. So it is enough to solve the subproblem.

Let be the length of the shortest path between and that use at most edges.

Base case: with for .

Recursion: Let .

Solution:

This algorithm is called the Bellman-Ford algorithm and has the following pseudo code. For this let

D(0,s) = 0
D(0,z) = inf for all z /= s
for i=1 -> n-1
	for all z in V
		D(i,z) = D(i-1,z)
		for (y,z) in E:
			D(i,z) = min(D(i,z), w(y,z) + D(i-1,y))
return D(n-1, . )

This takes as you could rewrite this psudo-code like this:

D(0,s) = 0
D(0,z) = inf for all z /= s
for i=1 -> n-1
	D(i,z) = D(i-1,z) for all z
	for all (x,y) in E
		D(i,y) = min(D(i,y), w(x,y) + D(i-1,x))
return D(n-1, . )

Case 2: Negative weight cycles

If we run to the case (note before we stopped at ) if any weights decrease then there was a shorter path visiting a vertex twice. This implies there is a negative weight cycle.

All-pairs shortest path

Shortest path problem (all pairs)

Given a directed graph with edge weights - the shortest path problem is to find the shortest distance between for every . This is called with the formal definition where is a path that starts at and ends at .

If you used the Bellman-Ford algorithm for each vertex this would take . Instead we will define the Floyd-Warshall algorithm which takes run time - which at worst the same as the Bellman-Ford algorithm as if it is connected without any double edges.

Let in the set up of a new subproblem.

Let be the length of the shortest path to only using as intermediate vertices.

Base case, The recursion set then is:

Why do you only visit once?

The pseudo code is as follows:

for s= 1 -> n:
	for t= 1 -> n:
		D(0,s,t) = inf
for (x, y) in E:
	D(0,x,y) = w(x,y)
for i = 1 -> n:
	for s = 1 -> n:
		for t = 1 -> n:
			D(i,s,t) = min(D(i-1,s,t), D(i-1, s, i) + D(i-1, i, t))
return D(n, . , . )

The run time of this algorithm is as we have that the run time is .

Negative weight cycles

Within the Floyd-Warshall algorithm you detect negative weight cycles by looking at the values if a negative weight cycle exists - this diagonal will have negative values.

Bellman-Ford algorithm vs Floyd-Warshall algorithm

Bellman-Ford algorithm only finds negative weight cycles reachable from that start vertex. Whereas Floyd-Warshall algorithm will find any negative weight cycle in the graph.

Further questions

From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

4.21 Currency exchange

Shortest path algorithms can be applied in currency trading. Let be various currencies; for instance, might be dollars, pounds, and lire. For any two currencies and , there is an exchange rate ; this means that you can purchase units of currency in exchange for one unit of . These exchange rates satisfy the condition that , so that if you start with a unit of currency , change it into currency and then convert back to currency , you end up with less than one unit of currency (the difference is the cost of the transaction).

(a) Give an efficient algorithm for the following problem: Given a set of exchange rates , and two currencies and , find the most advantageous sequence of currency exchanges for converting currency into currency . Toward this goal, you should represent the currencies and rates by a graph whose edge lengths are real numbers.

The exchange rates are updated frequently, reflecting the demand and supply of the various currencies. Occasionally the exchange rates satisfy the following property: there is a sequence of currencies such that . This means that by starting with a unit of currency and then successively converting it to currencies , and finally back to , you would end up with more than one unit of currency . Such anomalies last only a fraction of a minute on the currency exchange, but they provide an opportunity for risk-free profits.

(b) Give an efficient algorithm for detecting the presence of such an anomaly. Use the graph representation you found above.