Register

GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 8

• edited by
243 views
0 0 votes

 

Consider the following directed, weighted graph:

Even though the graph has negative weight edges, we use Dijkstra’s algorithm to calculate supposedly shortest paths from A to every other vertex.
Which of the following is/are correct?

  1. The order in which vertices are added to the shortest path tree using Dijkstra's algorithm is $: \text{A B D F G C E}.$
  2. The order in which vertices are added to the shortest path tree using Dijkstra's algorithm is $: \text{A B D F C G E}.$
  3. Dijkstra’s algorithm finds the wrong path to some of the vertices.
  4. Dijkstra’s algorithm finds the right path to all of the vertices.

1 Answer

2 2 votes
Known vertices (in order marked known)$: \text{A B D F C G E}$
$$
\begin{array}{|c|c|c|c|}
\hline \text{Vertex} & \text{Known} & \text{Distance} & \text{Path} \\
\hline \text{A} & \text{Y} & 0 & \\
\hline \text{B} & \text{Y} & 2 & \text{A} \\
\hline \text{C} & \text{Y} & 7 & \text{A} \\
\hline \text{D} & \text{Y} & 4 & \text{B} \\
\hline \text{E} & \text{Y} & 12\;9 & \text{A C} \\
\hline \text{F} & \text{Y} & 6 & \text{D} \\
\hline \text{G} & \text{Y} & 8 & \text{F} \\
\hline
\end{array}
$$
Dijkstra's algorithm found the wrong path to some of the vertices. Computed path to $\mathrm{G}$ is $\mathrm{A}, \mathrm{B}, \mathrm{D}, \mathrm{F}, \mathrm{G}$ but shortest path is $\mathrm{A}, \mathrm{C}, \mathrm{E}, \mathrm{G}$. Computed path to $\mathrm{D}$ is $\mathrm{A}, \mathrm{B}, \mathrm{D}$ but shortest path is $\mathrm{A}, \mathrm{C}, \mathrm{E}, \mathrm{G}, \mathrm{D}$. Computed path to $\mathrm{F}$ is $\mathrm{A}, \mathrm{B}, \mathrm{D}, \mathrm{F}$ but shortest path is $\mathrm{A}, \mathrm{C}, \mathrm{E}, \mathrm{G}, \mathrm{D}, \mathrm{F}$.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes Test Seri...Next → · GO Classes Test Seri...
← Previous in category · GO Classes Test Seri...Next in category → · GO Classes Test Seri...
Position:
Show:

Related questions

0 0 votes
2 2 answers
186
186 views
GO Classes asked Oct 16, 2024
186 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 4
Consider the below weighted graph where weight of the edge $e$ is written as $w(e).$If we run Dijkstra's algorithm with $s=0$, in which order will the vertices be deleted...
0 0 votes
2 2 answers
261
261 views
GO Classes asked Oct 16, 2024
261 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 6
Which of the following is/are TRUE ?If we perform DFS on an undirected graph, there are no cross edges.If the DFS tree has no back edges, then there are no cycles in the ...
2 2 votes
1 1 answer
378
378 views
GO Classes asked Oct 16, 2024
378 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 9
Which of the following is/are TRUE?Dijkstra's algorithm may not terminate if the graph contains negative-weight edges.Given a graph $\text{G = (V, E)}$ with positive edge...
1 1 vote
1 1 answer
245
245 views
GO Classes asked Oct 16, 2024
245 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 12
Let $\text{G = (V, E)}$ be a weighted directed graph. The shortest path from a node $s \in \text{V}$ to a node $t \in \text{V}$ will remain unchanged if: (Multiple option...