# 代写代考 FIT2004 Implementation checklist – cscodehelp代写

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
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