Register

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

• edited by
338 views
1 1 vote

Which of the following is correct option about $\mathrm{S} 1$ and $\mathrm{S} 2?$

  • $\mathrm{S} 1:$ If $\text{G}$ is a weighted graph with $n$ vertices and $m$ edges that does not contain negative weight cycle, then the iteration of the Bellman-Ford algorithm will reach a fixed point in at most $n-1$ rounds.
  • $\mathrm{S} 2:$ If $\text{G}$ is a weighted graph with $n$ vertices and $m$ edges that does contain negative-weight cycle, then for every vertex $v$ in $\text{G}$ the shortest path from $v$ to $t$ in $\text{G}$ containing $n$ edges is strictly shorter than the shortest path from $v$ to $t$ in $\text{G}$ containing $n-1$ edges.
  1. $\mathrm{S} 1$ is TRUE but $\mathrm{S} 2$ is False
  2. $\mathrm{S} 2$ is TRUE but $\mathrm{S} 1$ is False
  3. Both are True
  4. Both are False

1 Answer

5 5 votes
Bellman Ford Algorithm finds the shortest path in V-1 iterations, if the negative cycle is either not present or it is not reachable.

S2 is False, because if the negative cycle is not reachable from any vertex, and if n-1 edge is giving the shortest path between any pair of vertices, then considering n edges may not change the shortest path.
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
260
260 views
GO Classes asked Oct 16, 2024
260 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 ...
1 1 vote
1 1 answer
279
279 views
GO Classes asked Oct 16, 2024
279 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 10
Each of the figures below represents a partial spanning tree with bold edges. Determine whether it could possibly be obtained from (a prematurely stopped) Prim’s algorith...
1 1 vote
1 1 answer
243
243 views
GO Classes asked Oct 16, 2024
243 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...
2 2 votes
1 1 answer
390
390 views
GO Classes asked Oct 16, 2024
390 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 15
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...