# Problem Set #2 Quiz Answer

In this article i am gone to share Coursera Course Graph Search, Shortest Paths, and Data Structures Week 2 | Problem Set #2 Quiz Answer with you..

## Graph Search, Shortest Paths, and Data Structures

### Problem Set #2 Quiz Answer

Question 1)
Consider a directed graph with distinct and nonnegative edge lengths and a source vertex s. Fix a destination vertex s,and assume that the graph contains at least one s-t path. Which of the following statements are true? (Check all that apply.]

• The shortest s-t path must exclude the maximum-length edge of G.
• There is a shortest s-t path with no repeated vertices (i.e., a “simple” or “loopless” such path).
• The shortest (i.e., minimum-length) s-t path might have as many as n – 1 edges, where n is the number of vertices.
• The shortest s-t path must include the minimum-length edge of G.

Question 2)
Consider a directed graph G with a source vertex s, a destination t, and nonnegative edge lengths. Under what conditions is the shortest s-t path guaranteed to be unique?

• When all edge lengths are distinct powers of 2.
• None of the other options are correct.
• When all edge lengths are distinct positive integers.
• When all edges lengths are distinct positive integers and the graph G contains no directed cycles.

Question 3)
Consider a directed graph G = (V, E) and a source vertex s with the following properties: edges that leave the source vertex s have arbitrary (possibly negative) lengths; all other edge lengths are nonnegative; and there are no edges from any other vertex to the source s. Does Dijkstra’s shortest-path algorithm correctly compute shortest-path distances (from s) in this graph?

• Maybe, maybe not (depends on the graph)
• Only if we add the assumption that G contains no directed cycles with negative total weight.
• Always
• Never

Question 4)
Consider a directed graph G and a source vertex s. Suppose G has some negative edge lengths but no negative cycles, meaning G does not have a directed cycle in which the sum of the edge lengths is negative. Suppose you run Dijkstra’s algorithm on G (with source s). Which of the following statements are true? [Check all that apply.]

• Dijkstra’s algorithm might loop forever.
• 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 s to all other vertices.
• Dijkstra’s algorithm always terminates, and in some cases the paths it computes will be the correct shortest paths from s to all other vertices.

Question 5)
Consider a directed graph G and a source vertex s. Suppose G contains a negative cycle (a directed cycle in which the sum of the edge lengths is negative) and also a path from s to this cycle. Suppose you run Dijkstra’s algorithm on G (with source s). Which of the following statements are true? [Check all that apply.]

• 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 s to all other vertices.
• Dijkstra’s algorithm always terminates, but in some cases the paths it computes will not be the shortest paths from s to all other vertices.
• It’s impossible to run Dijkstra’s algorithm on a graph with a negative cycle.