27.2.1. Correctness of Dijkstra Algorithm

Try these first

1. 1.

   What is the primary purpose of Dijkstra's algorithm?

   Hint

   Think about pathfinding in graphs.

2. 2.

   Define an invariant in the context of algorithms.

   Hint

   What stays fixed in an algorithm during its run?

3. 3.

   What is the time complexity of Dijkstra's algorithm when using an adjacency matrix?

   • O(n)
   • O(n^2)
   • O(n log n)

   Hint

   Consider how many comparisons are needed with a matrix representation.

4. 4.

   True or False: Dijkstra's algorithm can handle graphs with negative edge weights.

   • True
   • False

   Hint

   Think about how negative weights impact distance calculations.

5. 5.

   If the graph contains both positive and negative edge weights but no negative cycles, describe how you might adapt Dijkstra's Algorithm to work correctly.

   Hint

   What alternative has been specifically designed for such cases?

6. 6.

   Given a graph structure with specific distances, compute the shortest path using Dijkstra's Algorithm. Provide a step-by-step explanation.

   Hint

   What systematic approach can you follow?