Implementation checklist
Week 10 Studio Sheet (Solutions)
Useful advice: The following solutions pertain to the theoretical problems given in the tutorial classes. You are strongly advised to attempt the problems thoroughly before looking at these solutions. Simply reading the solu- tions without thinking about the problems will rob you of the practice required to be able to solve complicated problems on your own. You will perform poorly on the exam if you simply attempt to memorise solutions to the tutorial problems. Thinking about a problem, even if you do not solve it will greatly increase your understanding of the underlying concepts. Solutions are typically not provided for Python implementation questions. In some cases, psuedocode may be provided where it illustrates a particular useful concept.
It will be most beneficial for your learning if you have completed this checklist before the studio.
By the end of week 10, write Python code for
• Dijkstra’salgorithmforsinglesourceshortestpaths • Bellman-Fordsinglesourceshortestpaths
• Floyd-Warshallall-pairsshortestpaths
Assessed Preparation
Problem 1. Use Dijkstra’s algorithm to determine the shortest paths from vertex s to all other vertices in this graph. You should clearly indicate the order in which the vertices are visited by the algorithm, the resulting distances, and the shortest path tree produced.
q 12 t 14 w 18 s 51 6 143
p 7 z 10 v 15 y
424555 r 11 u 11 x
Vertices are visited in the order:
The shortest path tree, with vertices labelled by their distances is shown
s,y,x,v,w,u,t,z,q,r,p
23 12 19 14 16 18 0 51 6 143
28 7 22 10 13 15 3
424555 24 11 18 11 8
Use Bellman-Ford to determine the shortest paths from vertex s to all other vertices in this graph. Afterwards, indicate to which vertices s has a well defined shortest path, and which do not by indicating the distance as −∞. Draw the resulting shortest path tree containing the vertices with well defined shortest paths. Forconsistency,youshouldrelaxtheedgesinthefollowingorder: s →a,s →b,a →c,b →a,b →d,c →b, c→d,c→e,d→f,e→dandf →e.
Problem 2.
s 4 −2 4 −5 10
b −10 d −6 f
The distances at each iteration are shown below. If you followed the order specified, you should have the same distances. Relaxing the edges in a different order may lead to a different table, but the end distances should be the same (except for the vertices reachable via negative cycles).
Iteration 0123556
s0000000 a∞555555 b∞222222 c∞444444
d ∞ -4 -8 -9 -9 -10 -10
e ∞ 0 -4 -4 -5 -5 -6
f ∞ -10 -14 -14 -15 -15 -16
Since another round of relaxation would decrease the distance of vertex d , it must be reachable via a negative cycle. All of the vertices reachable from d therefore have undefined distance estimates. The final distances are therefore
0 5 2 4 −∞ −∞ −∞
The shortest path tree is shown below
s 4 −2 4 −5 10
b −10 d −6 f
Studio Problems
Problem3. GiveanexampleofagraphwithnegativeweightsonwhichDijkstra’salgorithmproducesthewrong
Many graphs are possible. The key is to force Dijkstra’s to take a wrong path by hiding a beneficial negative weight edge behind a higher weight edge. The following example does this.
In this case, Dijkstra will take the highlighted path, which is not a shortest path.
Problem4. Considerthefollowingalgorithmforsingle-sourceshortestpathsonagraphwithnegativeweights: • Findtheminimumweightedgeinthegraph,sayithasweightw
• Subtract w from the weight of every edge in the graph. The graph now has no negative weights
• RunDijkstra’salgorithmonthemodifiedgraph
• Add w back to the weight of the edges and compute the lengths of the resulting shortest paths Prove by giving a counterexample that this algorithm is incorrect.
The problem with this algorithm is that it changes the length of paths with more edges a larger amount than it changes the lengths of paths with fewer edges, since it adds a constant amount to every edge weight. A good graph to break this would therefore be one where a shortest path has more edges than an alternative.
s −4 b a −3 d
Inthiscase,theshortestpathfroms tob iss →a →d →b withlength−12. Ifwesubtract−5fromevery edge weight in the graph, then it becomes the following, where the shortest path is now s → b , so we get the wrong answer.
s1b 01 a2d
Problem5. Supposethatwewishtosolvethesingle-sourceshortestpathproblemforgraphswithnonnegative bounded edge weights, i.e. we have w(u,v) ≤ c for some constant c. Explain how we can modify Dijkstra’s algorithm to run in O (V + E ) time in this case. [Hint: Improve the priority queue]
The part of Dijkstra’s algorithm that adds the log factor is the priority queue, so let’s try to improve that. Given that the edge weights are bounded above by c , and a shortest path can contain at most V −1 edges, the largest distance estimate that we can ever have is less than c V . Also observe that since we remove vertices from the priority queue in distance order, the minimum element in the priority queue never decreases. We can use these two facts to make a faster priority queue for Dijkstra’s.
Let’s just store an array of size c V , where at each entry, we store a linked list of vertices who have that distance estimate. Adding an element to this priority queue takes O (1) since we can simply append to the corresponding linked list. Updating a distance estimate can also be achieved in O (1) since we can remove an element from a linked list in O (1) and append it to a different one. Since the minimum distance for entries obtained from priority queue never decreases, we can simply move through the priority queue, starting at distance zero and moving onto the next distance when there are no vertices left to process at the current distance. We never move back to a previous distance.
All updates to the priority queue take O (1). Finding the minimum element in the priority queue could take up to O (V ), but note that since we never go backwards, the total time complexity of all find minimum operations will be O (V ), since scanning all of the distances takes O (c V ) = O (V ) since c is a constant. The total time complexity of Dijkstra’s using this priority queue will therefore be O (V + E ).
Problem 6. Describe an algorithm that given a graph G determines whether or not G contains a negative cycle. Your algorithm should run in O (V E ) time.
Remember that the Bellman-Ford algorithm can detect whether there is a negative cycle that is reach- able from the source vertex. The obvious tempting solution is to just run Bellman-Ford from every pos- sible source vertex and see whether a negative cycle is detected. This would be very slow though, taking O (V 2 E ) time. Instead, we would rather run just one Bellman-Ford, but how can we be sure that we can definitely reach the negative cycle if one exists? The easiest way to ensure this is to simply add a new vertex to the graph, and add an edge from that vertex to every other vertex in the graph. Running Bellman-Ford
on this vertex will then definitely visit every vertex, and hence will definitely detect a negative cycle if one is present. Since we only need to run Bellman-Ford once, this algorithm takes O (V E ) time.
Problem7. ImprovetheFloyd-Warshallalgorithmsothatyoucanalsoreconstructtheshortestpathsinaddition to the distances. Your improvement should not worsen the time complexity of Floyd-Warshall, and you should be able to reconstruct a path of length k in O (k ) time.
There are many approaches to make this work.
Solution 1: Track the intermediate vertex
The simplest way to keep track of the path information is to record, for each pair of vertices u , v , which intermediate vertex was optimal for going between them. This can be tracked during the algorithm like so.
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17:
functionFLOYD_WARSHALL(G=(V,E))
Set dist[1..n][1..n] = ∞
Set dist[v][v] = 0 for all vertices v
Set dist[u][v] = w(u,v) for all edges e = (u,v) in E
Set mid[1..n][1..n] = null // mid[u][v] = optimal intermediate vertex foreachvertexk=1ton do
foreachvertexu=1ton do foreachvertexv=1ton do
if dist[u][k] + dist[k][v] < dist[u][v] then dist[u][v] = dist[u][k] + dist[k][v] mid[u][v] = k
end if end for
end for end for
return dist[1..n][1..n], mid[1..n][1..n] endfunction
To reconstruct the path, we then need to do a sort of divide-and-conquer style path reconstruction.
1: 2: 3: 4: 5: 6: 7: 8: 9:
functionGET_PATH(u,v)
if mid[u][v] = null then
return [u, v] else
left = GET_PATH(u, mid[u][v]) right = GET_PATH(mid[u][v], v) return left.pop_back() + right
end if endfunction
// Remove the duplicate from the middle
Solution 2: Track the successor
Another slightly cleaner solution is to remember for each pair u , v , what is the first vertex on a shortest path from u to v. To maintain this, if we update the pair u, v and decide that vertex k is the new best intermediate vertex, then the first vertex on a shortest path from u to v is just the first vertex on a shortest path from u to k . We can implement this as follows.
1: functionFLOYD_WARSHALL(G=(V,E))
2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18:
Set dist[1..n ][1..n ] = ∞
Set dist[v][v] = 0 for all vertices v
Set dist[u][v] = w(u,v) for all edges e = (u,v) in E
Set succ[1..n ][1..n ] = null // succ[u][v] = successor of u on shortest path to v Set succ[u][v] = v for all edges e = (u,v) in E
foreachvertexk=1ton do
foreachvertexu=1ton do foreachvertexv=1ton do
if dist[u][k] + dist[k][v] < dist[u][v] then dist[u][v] = dist[u][k] + dist[k][v] succ[u][v] = succ[u][k]
end if end for
end for end for
return dist[1..n ][1..n ], succ[1..n ][1..n ] endfunction
Reconstructing the paths is now easier as we do not need any fancy recursion.
1: 2: 3: 4: 5: 6: 7:
functionGET_PATH(u,v) Set path = [u] whileu̸=vdo
u = succ[u][v]
path.append(u)
end while endfunction
In both cases, we add only a constant amount of overhead to the algorithm so we do not worsen the complexity. We can also reconstruct paths of length k in O (k ) time in both cases.
Problem8. Considertheproblemofplanningacross-countryroadtrip.YouhaveamapofAustraliaconsisting of the locations of towns, each of which has a petrol station, with the corresponding petrol prices (which may be different at each town). You are currently at a particular town s and would like to travel to town t . Your car has a fuel capacity of C litres, and for each road on the map, you know the amount of petrol it will take to travel along it. Your tank can only contain non-negative integer amounts of petrol, and all roads cost an integer amount of petrol to travel along. You can not travel along a road if you do not have enough petrol to make it all the way. You may refuel at any petrol station whether your tank is empty or not (but only to integer values), and you are not required to fill your tank. Assuming that your tank is initially empty, describe an algorithm for determining the cheapest way to travel to city t . [Hint: You should model the problem as a shortest path problem and use Dijkstra’s algorithm.]
Our first thought might be to weight the edges of the graph by how much petrol they use and then run Dijkstra’s algorithm, but this will miss quite a few things. Remember that we need to take into account:
• Thecostofpetrolatvarioustowns
• Wecanfueluppartiallyatanytown,andleavethetownwithanyamountofpetrol • Wemightnotbeabletomakeitacrossaroadwithoutrunningout
In order to account for these things, we create a new graph that encapsulates more information than just
our location on the vertices. Suppose that there are n towns Let’s make a graph that contains (C + 1)n vertices, one for each town for each possible amount of petrol that we could possible have. That is, each town has (C + 1) different vertices, one for when we are in that town with no petrol, one for when we are there with 1 litre, 2 litres and so on. Let’s the use the notation 〈u , c 〉 to denote the vertex corresponding to town u where we have c litres of petrol currently in the tank.
If a road from town u to town v takes x litres of petrol to travel, then for each of the vertices 〈u , c 〉 corre- sponding to town u with c ≥ x, we create an edge to the corresponding vertex 〈v,c − x〉 of town v. For example, if x = 5, then we create an edge from 〈u,10〉 to 〈v,5〉, and from 〈u,9〉 to 〈v,4〉, from 〈u,8〉 to 〈v,3〉, and so on. Importantly, these edges have weight zero, since we are going to use edge weights to model the cost of purchasing fuel.
To account for buying new fuel, suppose we are currently in the town u whose petrol price is p . Then we should add an edge from every vertex 〈u,c〉 with c < C to the vertex 〈u,c +1〉 with weight p. Note that we could have added edges from 〈u,c〉 to 〈u,c +2〉 with weight 2p and so on, but this would just make the graph unnecessarily denser and hence make the algorithm slower for no reason, so it is best to simply add edges that add 1 litre of petrol at a time.
We can then run Dijkstra from the vertex 〈s , 0〉 to find the shortest path to 〈t , 0〉, which will be the cheapest waytomakeitfroms tot.
Supplementary Problems
Problem9. ImplementDijkstra’salgorithmandtestyourcode’scorrectnessbysolvingthefollowingCodeforces
problem: http://codeforces.com/problemset/problem/20/C.
Problem10. ImplementBellman-Fordandtestyourcode’scorrectnessbysolvingthefollowingproblemonUVA Online Judge: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem& problem=499.
Problem11. ConsiderabuggyimplementationofDijkstra’salgorithminwhichthedistanceestimatetoavertex is only updated the first time the vertex is discovered, and not in any subsequent relaxations. Give a graph on which this bug will cause the algorithm to not produce the correct answer.
To break such a bug, we need a vertex whose initial distance estimate is very high, but should be subse- quently lowered by a better path found later. The following graph will cause this problem.
a 1000 c 1 d s11
The distance estimate to c will get locked at 1001, even though it should be updated to 3, and hence the
distances to c and d will be wrong.
Problem12. Givenagraphthatcontainsanegativeweightcycle,giveanalgorithmtodeterminetheverticesof
one such cycle. Your algorithm should run in O (V E ) time.
Recall from Problem 6 that we can use Bellman-Ford to detect the presence of a negative cycle by adding a new source vertex that connects to all others. Let’s start by doing this. Remember that when Bellman- Ford terminates, the predecessors will all form a shortest path tree, except for the vertices reachable from a negative cycle. These predecessors may not form a tree, but may actually form cycles since they will point to the vertices that caused them to relax most recently. To guarantee that the predecessors form a cycle, we will run Bellman-Ford for |V | iterations (instead of |V | − 1) since the extra relaxation will cause the infinite cycle to propagate all the way around.
To produce a negative cycle, we therefore begin at an arbitrary vertex that is reachable from a negative cycle. Such a vertex will be any one that was relaxed during iteration |V | of Bellman-Ford. This vertex may not necessarily be in a negative cycle, as it could be on a path that simply travels through one and then leaves it. In order to get to the negative cycle that caused this, we should travel backwards along the predecessors. Since there are at most |V | vertices in any path, we can just travel back |V | times. This will guarantee that we enter whatever cycle caused this vertex to have an undefined shortest path.
Once we are inside the cycle, we can then simply backtrack around it until we find the first vertex again, at which point we stop and return the sequence that we found. Some pseudocode is shown below.
1: functionFIND_NEGATIVE_CYCLE(G=(V,E))
2: s = G.add_vertex() // Add a new vertex to G
3: foreachvertexv=1ton do
4: G.add_edge(s, v, w = 0)
5: end for
6: dist[1..n], pred[1..n] = BELLMAN_FORD(G, s)
7: Let v = any vertex that was relaxed during iteration |V |
8: fori=1ton do
9: v = pred[v]
10: end for
11: cycle = [v]
12: u = pred[v]
13: whileu̸=vdo
14: cycle.append(u)
15: u = pred[u]
16: end while
17: return reverse(cycle)
18: endfunction
// We built the cycle backwards so reverse it
// Backtrack into the cycle
Problem 13. Add a post-processing step to Floyd-Warshall that sets dist[u][v] = −∞ if there is an arbitrarily short path between vertex u and vertex v , i.e. if u can travel to v via a negative weight cycle. Your post processing should run in O(V 3) time or better, i.e. it should not worsen the complexity of the overall algorithm.
// Run for |V | iterations to guarantee cycle
Recall that the Floyd-Warshall algorithm can detect the presence of negative cycles by looking at the dis- tances of vertices to themselves. If a vertex can reach itself with a negative distance, then it must be contained in a negative cycle. We can therefore post process the graph by checking each intermediate vertex k that is part of a negative cycle, and then setting the lengths of all paths u v such that u can reach k and k can reach v to −∞. This process takes O (V 3 ). See the pseudocode below.
1: functionFLOYD_WARSHALL_POSTPROCESS(G=(V,E),dist[1..n])
foreachvertexk=1ton do if dist[k][k] < 0 then
foreachvertexu=1ton do
5: 6: 7: 8: 9:
10: 11: 12: 13:
foreachvertexv=1ton do
if dist[u][k] + dist[k][v] < ∞ then
dist[u][v] = −∞ end if
end for end for
end if end for
endfunction
Problem 14. Arbitrage is the process of exploiting conversion rates between commodities to make a profit. Arbitrage may occur over many steps. For example, one could purchase US dollars, convert it into Great British Pounds, and then back into Australian dollars. If the prices were right, this could result in a profit. Given a list of currencies and the best conversion rate between each pair, devise an algorithm that determines whether arbitrage is possible, i.e. whether or not you could make a profit. Your algorithm should run in O(n3) where n is the number of currencies.
Let’s imagine this as a shortest path problem. We wish to begin at one currency and walk through a path containing some other currencies before arriving back at our initial currency with a net profit. Making a profit means that the net conversion rate between a currency and itself should be less than 1. Note that if we convert between currencies whose exchange rates are r1 , r2 , ..., rk , then the final conversion rate is r1 × r2 × ... × rk . One way to model this problem is to therefore create a graph on n vertices where each vertex represents a currency. We add a directed edge between a pair of vertices with the exchange rate as the weight. We could then modify the Floyd-Warshall algorithm to compute the product of the weights rather than the sum, and it would then find for us the best conversion rate between any pair of currencies. Arbitrage is possible if a currency can be converted into itself at a rate of less than 1, i.e. if we find an entry on the diagonal of the distance matrix that is less than 1.
An alternate solution that does not require us to modify Floyd-Warshall is to create the same graph but the use the logarithms of the exchange rates as the edge weights. We can then run the ordinary Floyd- Warshall algorithm. This works because log(r1) + log(r2) = log(r1 × r2). Since log(r ) < 0 if and only if r < 1, we know that arbitrage is possible if and only if the graph contained a negative cycle, i.e. if a vertex has a negative distance to itself.
Problem 15. In a directed graph with positive weights, a vital arc for a pair of vertices s and t is an edge whose removal from the graph would cause the shortest distance between s and t to increase. A most vital arc for the pair s,t is a vita