28.1.1. Prof. Madhavan Mukund

Try these first

1. 1.

   What is the main purpose of the Bellman-Ford algorithm?

   Hint

   Think about what makes Dijkstra's algorithm limited.

2. 2.

   Does the Bellman-Ford algorithm work with negative cycles?

   Hint

   Consider what happens if a cycle continuously reduces a path's cost.

3. 3.

   What does the Bellman-Ford algorithm compute?

   • Longest paths
   • Shortest paths
   • Paths with infinite costs

   Hint

   Consider the goal of the algorithm.

4. 4.

   True or False: The Bellman-Ford algorithm can handle negative weights.

   • True
   • False

   Hint

   Remember how negative weights impact path costs.

5. 5.

   Create an example graph with at least five vertices and a few edges, some of which have negative weights. Use the Bellman-Ford algorithm to compute shortest paths.

   Hint

   Keep track of each vertex's distance as you update!

6. 6.

   Given a graph includes a negative cycle involving three vertices, explain how the Bellman-Ford algorithm handles this scenario.

   Hint

   No hint provided