# 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

**Also Visit This Link:** Problem Set #1 Quiz Answer

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