28.1. Design and Analysis of Algorithms, Chennai Mathematical Institute

Try these first

1. 1.

   What does the Bellman-Ford algorithm specifically handle that Dijkstra's does not?

   Hint

   Think about edge weights in graphs.

2. 2.

   True or False: A shortest path can have loops.

   Hint

   Recall the properties of shortest paths and loops.

3. 3.

   What does the Bellman-Ford algorithm do?

   • Finds paths with positive weights only
   • Finds shortest paths with negative weights
   • Finds all longest paths

   Hint

   Consider the capabilities of both the Bellman-Ford and Dijkstra’s algorithms.

4. 4.

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

   • True
   • False

   Hint

   Think about the implications of negative cycles.

5. 5.

   In a graph with vertices A, B, C, and D, where edges are weighted A->B(2), B->C(-3), A->C(4), and C->D(1). Determine the shortest path from A to D using the Bellman-Ford algorithm.

   Hint

   Implement the updates as per Bellman-Ford, observing each iteration's effect.

6. 6.

   Create your own graph with at least one negative cycle and explain in detail how it affects the path calculations when running Bellman-Ford.

   Hint

   Draw the graph out and calculate distances after each iteration to see the cycle's effect.