Bellman-Ford algorithm is used for which type of problem?

Bellman-Ford algorithm is used for which type of problem?

• A. Shortest paths with negative weights but no negative cycles
• B. Spanning trees
• C. Sorting
• D. Graph coloring

Answer: (A)

Finding single-source shortest paths in graphs that may have negative edge weights is what Bellman-Ford is designed to do. It works by repeatedly relaxing every edge to propagate distance improvements, performing V−1 passes where V is the number of vertices. This guarantees correct shortest-path distances as long as there isn’t a negative-weight cycle reachable from the source, because such a cycle would let you keep decreasing the path length without bound. After those passes, a final check looks for any edge that can still relax a distance; if found, it indicates a reachable negative-weight cycle, meaning finite shortest paths don’t exist in that case. This capability to handle negative weights (unlike algorithms that require all weights to be non-negative) while also detecting problematic cycles is why Bellman-Ford is used for this type of problem. It isn’t used for spanning trees, sorting, or graph coloring, which are different tasks.

Finding single-source shortest paths in graphs that may have negative edge weights is what Bellman-Ford is designed to do. It works by repeatedly relaxing every edge to propagate distance improvements, performing V−1 passes where V is the number of vertices. This guarantees correct shortest-path distances as long as there isn’t a negative-weight cycle reachable from the source, because such a cycle would let you keep decreasing the path length without bound. After those passes, a final check looks for any edge that can still relax a distance; if found, it indicates a reachable negative-weight cycle, meaning finite shortest paths don’t exist in that case. This capability to handle negative weights (unlike algorithms that require all weights to be non-negative) while also detecting problematic cycles is why Bellman-Ford is used for this type of problem. It isn’t used for spanning trees, sorting, or graph coloring, which are different tasks.