Question-51

Algorithms
Shortest Path

Consider a weighted, directed acyclic graph \(G = (V, E, w)\) in which edges that leave the source vertex \(s\) may have negative weights and all other edges weights are non-negative.

Which of the following statement(s) is/are correct?

  1. Dijkstra’s algorithm correctly computes the shortest-path weight \(δ(s, t)\) from \(s\) to every vertex \(t\) in this graph G.

  2. Dijkstra’s algorithm may compute an incorrect shortest-path weight \(δ(s, t)\) from \(s\) to at least one vertex \(t\) in this graph G.

  3. Bellman’s Ford algorithm correctly computes the shortest-path weight \(δ(s, t)\) from \(s\) to every vertex \(t\) in this graph G.