edited by
279 views
6 votes
6 votes

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $c$ and $e$. Which one will be reported by Dijstra's shortest path algorithm run with $a$ as the source? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered.

  1. $c-d-f-e$
  2. $c-f-e$
  3. $c-i-g-f-e$
  4. $c-d-e$
edited by

1 Answer

Best answer
2 votes
2 votes
The nodes will be visited as

$\boxed{\underset{0}{a}}-\boxed{\underset{3}{b}} - \boxed{\underset{7}{c}} - \boxed{\underset{9}{i}} - \boxed{\underset{12}{h}} - \boxed{\underset{15}{g}} - \boxed{\underset{14}{d}} - \boxed{\underset{21}{f}} - \boxed{\underset{25}{e}}$

$e$ is first updated as $25$ while processing $d$ is first updated as $14$ while processing $c.$ So, the path output by Dijkstra's algorithm from $c - e$ will be $c – d –  e.$

Correct option: D
selected by
Answer:

Related questions

5 votes
5 votes
1 answer
3
gatecse asked Sep 7, 2020
283 views
Which of the following algorithm can be used to efficiently calculate single source shortest paths in a Directed Acyclic Graph where all edge weights are equal?Dijkstra's...
4 votes
4 votes
1 answer
4