11.3.1. Time Complexity of Dijkstra's Algorithm

Try these first

1. 1.

   What is the purpose of using a min-heap in Dijkstra's algorithm?

   Hint

   Think about the operations we need to perform frequently.

2. 2.

   How are initial distances set in Dijkstra's algorithm?

   Hint

   What initialization allows us to start our shortest path search?

3. 3.

   What is the time complexity of Dijkstra's Algorithm using heaps?

   • O(N)
   • O(N log N)
   • O((N + M) log N)

   Hint

   Consider both vertices and edges in your calculations.

4. 4.

   Dijkstra's algorithm guarantees the shortest path for which type of graph?

   • True
   • False

   Hint

   Think about how edge weights can influence the shortest paths.

5. 5.

   Design a graph with at least 5 vertices and weighted edges. Perform Dijkstra's algorithm and describe each step including the heap updates.

   Hint

   Begin with the starting vertex and iteratively find the next minimum distance.

6. 6.

   Explain how modifying edge weights can impact Dijkstra’s algorithm and provide an example.

   Hint

   Consider both increasing and decreasing an edge's weight.