All Coursera Quiz Answers

Problem Set #2 Quiz Answer

by Niyander

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.