Problem:
Which of the following statements about Dijkstra's shortest-path algorithm are true for input graphs that might have some negative edge lengths?
Solution:
(Option 1) It is guaranteed to terminate.
The algorithm, regardless of correctness, also make progress towards completion by removing a vertex from the unknown set, so it must terminate.
(Option 2) It may or may not correctly compute shortest-path distances (from a given source vertex to all other vertices), depending on the graph.
This is true because the graph may not have any negative edge at all.
(Option 3) It may or may not terminate (depending on the graph).
This is not true given option 1
(Option 4) It is guaranteed to correctly compute shortest-path distances (from a given source vertex to all other vertices).
This is not true, or else we don't really need the restriction.
Which of the following statements about Dijkstra's shortest-path algorithm are true for input graphs that might have some negative edge lengths?
(Option 1) It is guaranteed to terminate.
The algorithm, regardless of correctness, also make progress towards completion by removing a vertex from the unknown set, so it must terminate.
(Option 2) It may or may not correctly compute shortest-path distances (from a given source vertex to all other vertices), depending on the graph.
This is true because the graph may not have any negative edge at all.
(Option 3) It may or may not terminate (depending on the graph).
This is not true given option 1
(Option 4) It is guaranteed to correctly compute shortest-path distances (from a given source vertex to all other vertices).
This is not true, or else we don't really need the restriction.
No comments:
Post a Comment