11.2. Dijkstra's Algorithm

Try these first

1. 1.

   Define a graph.

   Hint

   Think about nodes and their connections.

2. 2.

   What is a min-heap?

   Hint

   Consider how numbers are arranged.

3. 3.

   What data structure does Dijkstra's algorithm primarily use for finding the minimum distance?

   • Array
   • List
   • Heap

   Hint

   Recall the structure discussed that has a special property.

4. 4.

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

   • True
   • False

   Hint

   Think about the implications of changing a weight.

5. 5.

   Given a directed graph with weighted edges, apply Dijkstra's algorithm to find the shortest path from vertex X to vertex Y. Provide detailed steps.

   Hint

   Draw the graph to visualize paths.

6. 6.

   Discuss the potential time complexity optimizations for Dijkstra's algorithm using different data structures aside from heaps.

   Hint

   Explore computational theory on data structures.