Problem Set 5
Consider a directed graph with distinct and nonnegative edge lengths and a source vertex . Fix a destination vertex , and assume that the graph contains at least one - path.
Which of the following statements are true? Check all that apply.
- The shortest (i.e., minimum-length)
path might have as many as edges, where is the number of vertices. - There is a shortest
path with no repeated vertices (i.e., a “simple” or “loopless” such path). - The shortest
path must include the minimum-length edge of . - The shortest
path must exclude the maximum-length edge of .
ANSWER: Consider a directed path with no cycles, and
Consider a directed graph
and a source vertex with the following properties: edges that leave the source vertex have arbitrary (possibly negative) lengths; all other edge lengths are nonnegative; and there are no edges from any other vertex to the source . Does Dijkstra’s shortest-path algorithm correctly compute shortest-path distances (from
) in this graph?
- Only if we add the assumption that
contains no directed cycles with negative total weight. - Never
- Maybe, maybe not (depends on the graph)
- Always
ANSWER: Dijkstra’s algorithm will work just fine. One approach is to see that the proof of correctness from the videos still works. A slicker solution is to notice that adding a positive constant
Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest).
What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)
and and and and
ANSWER: In the worst case, Insert may need to move all elements of the array to the right (if we get an element bigger than the first one). Extract-Min is simply a constant-time lookup of the last index of the array. Thus, option 4 is correct.
Suppose you implement the functionality of a priority queue using a unsorted array.
What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)
and and and and
ANSWER: The worst case running time for insertion is easy, we can simply append it in the end of the unsorted array in constant time. For extracting the minimum element, we may need to look at all the elements. Thus, option 4 is correct.
You are given a heap with
elements that supports Insert and Extract-Min. Which of the following tasks can you achieve in
time?
- None of these
- Find the largest element stored in the heap
- Find the median of the elements stored in the heap
- Find the fifth-smallest element stored in the heap
ANSWER: Finding the fifth-smallest element from a min-heap takes five calls, each
Consider a directed graph
with a source vertex , a destination , and nonnegative edge lengths. Under what conditions is the shortest path guaranteed to be unique?
- When all edge lengths are distinct positive integers.
- None of the other options are correct.
- When all edges lengths are distinct positive integers and the graph
contains no directed cycles. - When all edge lengths are distinct powers of 2.
ANSWER: Consider a graph
Consider a directed graph
and a source vertex . Suppose has some negative edge lengths but no negative cycles, meaning does not have a directed cycle in which the sum of the edge lengths is negative. Suppose you run Dijkstra’s algorithm on (with source ). Which of the following statements are true? [Check all that apply.]
- It’s impossible to run Dijkstra’s algorithm on a graph with negative edge lengths.
- Dijkstra’s algorithm always terminates, but in some cases the paths it computes will not be the shortest paths from
to all other vertices. - Dijkstra’s algorithm might loop forever.
- Dijkstra’s algorithm always terminates, and in some cases the paths it computes will be the correct shortest paths from
to all other vertices.
ANSWER: Nothing about the description of the algorithm itself relies on there being no negative cycle. Thus, option 1 is incorrect.
Nonnegativity of the edge lengths was used in the correctness proof for Dijkstra’s algorithm; with negative edge lengths, the algorithm is no longer correct in general. Thus, option 2 is correct.
The algorithm always halts after
Option 4 is correct; imagine adding a large postive constant
Consider a directed graph
and a source vertex . Suppose contains a negative cycle (a directed cycle in which the sum of the edge lengths is negative) and also a path from to this cycle. Suppose you run Dijkstra’s algorithm on (with source ). Which of the following statements are true? [Check all that apply.]
- It’s impossible to run Dijkstra’s algorithm on a graph with negative edge lengths.
- Dijkstra’s algorithm might loop forever.
- Dijkstra’s algorithm always terminates, but in some cases the paths it computes will not be the shortest paths from
to all other vertices. - Dijkstra’s algorithm always terminates, and in some cases the paths it computes will be the correct shortest paths from
to all other vertices.
ANSWER: Nothing about the description of the algorithm itself relies on there being no negative cycle. Thus, option 1 is incorrect.
When there is negative cycle reachable from
Options 3 and 4 are incorrect because they are contracdictory to option 2.
Leave a comment