11.2.1. Finding the Minimum Distance

Try these first

1. 1.

   What is the primary purpose of Dijkstra’s algorithm?

   Hint

   Recall what type of problems requires the shortest distance.

2. 2.

   What is a min-heap?

   Hint

   Think about how parent and child relationships work in trees.

3. 3.

   What data structure does Dijkstra's Algorithm use for selecting the next vertex?

   • Array
   • Min-Heap
   • Stack

   Hint

   Consider which data structure allows for quick access to the smallest value.

4. 4.

   Heap violations are fixed upwards when:

   • True
   • False

   Hint

   Think about the implications of increasing a node's value relative to it parent.

5. 5.

   Using the graph defined by vertices 1-4 and edges (1-2, cost 4), (1-3, cost 1), (2-4, cost 1), (3-4, cost 5). Demonstrate the application of Dijkstra’s Algorithm starting from vertex 1.

   Hint

   Trace the path carefully, recording minimum distances achieved.

6. 6.

   Describe the implications of using an array versus a heap for implementing Dijkstra’s algorithm in terms of time complexity and performance.

   Hint

   Compare the efficiency by considering retrieval of the minimum element.