# Graph Search, Shortest Paths, and Data Structures Week 2 | Problem Set #2 Quiz Answer

## Graph Search, Shortest Paths, and Data Structures Week 2 | Problem Set #2 Quiz Answer

#### Problem Set #2

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.