27.1.5. Module - 02

Try these first

1. 1.

   What is the initial distance assigned to all vertices except the source in Dijkstra's algorithm?

   Hint

   All vertices start with a distance of what value except the source?

2. 2.

   True or False: Dijkstra's algorithm can handle negative weight edges.

   Hint

   What happens with negative weights in shortest path problems?

3. 3.

   What is the main objective of Dijkstra's algorithm?

   • Find the maximum path
   • Find the shortest path
   • Find all paths

   Hint

   What are we trying to minimize in this algorithm?

4. 4.

   Dijkstra's algorithm uses which type of approach?

   • True
   • False

   Hint

   Does it make local choices for global outcomes?

5. 5.

   Given a graph with vertices A, B, C, and D with weights: A to B (1), A to C (4), B to C (2), B to D (6), and C to D (1). Using Dijkstra's algorithm from A, calculate the shortest path to D.

   Hint

   Trace the paths starting from A and calculate the weights.

6. 6.

   Explain the shortcomings of Dijkstra's algorithm when applied to a graph with negative edges and provide an example of why it fails.

   Hint

   Consider paths and how weights impact total distance, especially when negative options are available.