| Computation of Minimum-Cost Paths |
About This Exercise
The objectives of this exercise are
- to ensure that you understand the problem of computing minimum-cost paths in graphs
- to ensure that you understand Dijkstra’s algorithm for this problem well enough to describe it, trace its execution by hand on small examples, and discuss its correctness and efficiency.
Students should read through and try to solve the problems on this exercise before attending the tutorial.
Expected Background
This is based on the lecture on the computation of minimum-cost paths that was presented in class. Chapter 24 of Cormen, Leiserson, Rivest and Stein’s text, Introduction to Algorithms, include more information about these algorithms and was the primary reference for an earlier version of the the course notes on this topic. University of Calgary students can read this book online. The Wikpedia pages on problem of computing minimum-cost paths in graphs and on Dijkstra’s algorithm for this problem are also recommended.
Warmup Problems — To Check That You Understand the Basics
It is expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course and attended the lecture on the computation of minimum-cost paths was introduced (reviewing the online notes, as needed).
These warmup problems will not be discussed in the tutorial; students who do have difficulty with them should contact the course instructor to get extra help.
-
Give definitions of each of the following.
- the cost of a path in a weighted path G
- a minimum-cost path between a vertex s and another vertex t in a weighted graph G
-
Consider the following Min-Heap. The values that are stored are shown inside nodes; priorities are shown, in brackets, beside them.
Trace the execution of the Decrease-Priority algorithm if the array A represents the above heap, i=8, and the new priority p is 2.
-
Briefly say what the MCP algorithm does.
Then trace the execution of MCP(G, 0) on each of the following weighted graphs.
-
-
Give an asymptotic upper bound on the number of steps used by the MCP algorithm in the worst case, when it is run on inputs G and s, for a graph G = (V, E), and explain how that bound can be proved to be correct.
To Be Discussed in The Tutorial
-
Consider the Decrease-Priority algorithm that is used to update information about costs of paths during the MCP algorithm.
-
Review the information about operations on binary heaps that has previously been studied, and find an algorithm that uses essentially the same technique update a binary heap. Which algorithm does this, and what problem does it solve?
-
Referring to the information about this other algorithm as needed, identify a loop invariant and a loop variant for the while loop that does most of the work in the Decrease-Priority algorithm.
-
Use this to sketch a proof of the correctness of this algorithm and to show that it uses Θ(log n) steps, in the worst case, when applied to a priority queue with n elements.
-
-
Consider the problem of finding minimim costs paths from a given start vertex to other vertices in a directed weighted graph.
-
Modify the MCP algorithm so that it can be used to solve this version of the problem.
-
Describe any and all modifications that must be made to the analysis of the algorithm, in order to prove that your algorithm for directed graphs is correct and efficient.
-
Then, if time permits, trace the execution of your program on the following weighted directed graph, using 0 as the start vertex.
-
|
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial22.html |