Question

The Bellman-Ford algorithm is preferred over Dijkstra's algorithm when the graph contains:

• A. Positive weight cycles
• B. Large number of nodes
• C. Negative weight edges
• D. Disconnected components

Hint:

While Bellman-Ford is more versatile, it is significantly slower than Dijkstra. Bellman-Ford has a time complexity of $O(VE)$, whereas Dijkstra with a Fibonacci heap is $O(E + V \log V)$.

Answer 1

The Correct Option is C

Concept: Both Dijkstra and Bellman-Ford are used to find the shortest path from a single source to all other vertices.
• Dijkstra's Algorithm: A greedy approach that is highly efficient but restricted to non-negative edge weights.
• Bellman-Ford Algorithm: A dynamic programming approach that handles a broader range of graphs.
• Negative Weights: These occur in real-world scenarios like financial modeling or chemical reactions where a path might represent "gain" instead of "cost."

Step 1: Understanding why Dijkstra's fails.
Dijkstra's algorithm assumes that once a vertex is added to the "visited" set, its shortest path is finalized. If there are negative weights, a later edge could potentially reduce the path cost to an already visited vertex. This greedy assumption makes Dijkstra's produce incorrect results for negative edge weights.

Step 2: How Bellman-Ford handles negative edges.
Bellman-Ford works by "relaxing" all edges in the graph $V-1$ times. This iterative approach ensures that even if a negative edge is found late, the path estimates can be updated correctly.

Step 3: Negative Cycle Detection.
Bellman-Ford can also detect negative weight cycles. If a path continues to decrease after $V-1$ iterations, a negative cycle exists.