GATE 2009
October 15, 2023GATE 2009
October 15, 2023GATE 2009
|
Question 13
|
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?
-
P. Always finds a negative weighted cycle, if one
Q. Finds whether any negative weighted cycle is reachable from the source.
|
P Only
|
|
|
Q Only
|
|
|
Both P and Q
|
|
|
Neither P nor Q
|
Question 13 Explanation:
Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.
More Info: The Dijkstra’a algorithm:
–A greedy algorithm
–Works when weights are all non-negative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
—If there is no negative cycle, a shortest path has at most |V|-1 edges
—A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
More Info: The Dijkstra’a algorithm:
–A greedy algorithm
–Works when weights are all non-negative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
—If there is no negative cycle, a shortest path has at most |V|-1 edges
—A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
Correct Answer: B
Question 13 Explanation:
Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.
More Info: The Dijkstra’a algorithm:
–A greedy algorithm
–Works when weights are all non-negative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
—If there is no negative cycle, a shortest path has at most |V|-1 edges
—A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
More Info: The Dijkstra’a algorithm:
–A greedy algorithm
–Works when weights are all non-negative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
—If there is no negative cycle, a shortest path has at most |V|-1 edges
—A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
Subscribe
Login
0 Comments