26.1. Shortest Paths in Weighted Graphs

Try these first

1. 1.

   What is a weighted graph?

   Hint

   Think about how costs can affect paths.

2. 2.

   What does Dijkstra's Algorithm find?

   Hint

   It’s named after the person who proposed it.

3. 3.

   What is the purpose of a weight function in a weighted graph?

   • To connect vertices
   • To assign costs to edges
   • To perform graph traversal

   Hint

   Focus on what makes weighted graphs distinct from unweighted graphs.

4. 4.

   Dijkstra's Algorithm can only be used with which type of weights?

   • True
   • False

   Hint

   Consider what happens if a path can decrease in cost.

5. 5.

   Given a weighted graph with vertices A, B, C, and D, create an edge weight table and utilize Dijkstra's algorithm to find the shortest path from A to all other vertices. What paths will you end up with?

   Hint

   Start with distances set to infinity, except for the starting vertex.

6. 6.

   In a scenario where some edge weights can change dynamically, discuss how you might adapt Dijkstra's algorithm for efficient re-computation. What strategies would you use?

   Hint

   What would be the trade-off between recalculating paths versus maintaining existing paths?