26.1.5. Types of Shortest Path Problems

Try these first

1. 1.

   What is a weighted graph?

   Hint

   Think about how real-world costs can be represented on a graph.

2. 2.

   Describe a real-world example of a single-source shortest path problem.

   Hint

   Consider transportation logistics.

3. 3.

   What constitutes a weighted graph?

   • A graph with vertices only
   • A graph with edges having costs
   • A graph with no edges

   Hint

   Consider how graph structures represent different factors.

4. 4.

   True or False: The all-pairs shortest path problem finds paths only from one vertex.

   • True
   • False

   Hint

   Recall the definitions we discussed.

5. 5.

   Design a logistical problem using a weighted graph and apply Dijkstra's algorithm to determine the most efficient route from a factory to multiple delivery points.

   Hint

   Map out your graph clearly! Focus on the starting point.

6. 6.

   Critically evaluate how variations in edge weights (for example, introducing negative weights) could affect Dijkstra's algorithm's performance.

   Hint

   Reflect on what happens with negative costs.