4.1. Dijkstra's Algorithm and Prim's Algorithm

Try these first

1. 1.

   What does Dijkstra's algorithm compute?

   Hint

   Think about graph paths and distances.

2. 2.

   What is a minimum spanning tree?

   Hint

   Remember the concept of connecting without cycles.

3. 3.

   What is the purpose of Dijkstra's algorithm?

   • To find minimum spanning trees
   • To find the shortest paths from a source vertex
   • To sort a list of numbers

   Hint

   Think about its application in pathfinding.

4. 4.

   True or False: Prim's algorithm can guarantee a unique minimum spanning tree for any graph.

   • True
   • False

   Hint

   Consider scenarios with equal edge weights.

5. 5.

   Create a graph with 5 vertices and 7 edges. Apply Dijkstra's algorithm starting from vertex 1. Show the steps and calculate the shortest path to each vertex.

   Hint

   Remember to keep track of your cumulative distances and to update them as you encounter each edge.

6. 6.

   Design a weighted graph where Prim's algorithm needs to handle equal weights. Explain the outcome and potential edges selected at each step.

   Hint

   Consider how many valid edges can exist when weights are the same, and how to break ties effectively.