28.2.1. Introduction to Negative Edges

Try these first

1. 1.

   What is a shortest path in graph theory?

   Hint

   Think of it as the quickest route.

2. 2.

   What happens if a graph contains negative cycles?

   Hint

   Consider how looping through a negative edge affects path weight.

3. 3.

   What is the main issue with Dijkstra's algorithm when dealing with negative edge weights?

   • It cannot handle negative weights
   • It assumes vertices have fixed shortest paths
   • It is inefficient

   Hint

   Think about the assumptions made when paths are completed.

4. 4.

   True or False: All prefixes of a shortest path must also be the shortest path.

   • True
   • False

   Hint

   Reflect on the characteristics of minimizing distance.

5. 5.

   Create a graph demonstrating the calculations of distances using the Bellman-Ford algorithm, detailing each iteration and resulting distances.

   Hint

   Focus on changes after each complete pass through the edges.

6. 6.

   Design a scenario where a negative cycle forces a path to have undefined shortest lengths, and explain the implications.

   Hint

   Consider how completing a circle with negative weights behaves over time.