1.2. Characteristics of Shortest Paths

Try these first

1. 1.

   What characterizes the paths in a weighted graph?

   Hint

   Think about how weights can change the journey.

2. 2.

   What happens to the shortest path if there is a negative cycle in the graph?

   Hint

   Consider how negative weights might play into the path calculation.

3. 3.

   What is the main goal of the Floyd-Warshall algorithm?

   • To find longest paths
   • To find shortest paths between all pairs of vertices
   • To detect cycles

   Hint

   Think about what the algorithm calculates across all vertices.

4. 4.

   True or False: The Bellman-Ford algorithm can handle negative weights.

   • True
   • False

   Hint

   Consider how each of these algorithms is affected by negative weights.

5. 5.

   Given a graph with vertices A, B, C, and D with edge weights defined as follows: A-B (4), A-C (1), B-D (1), C-D (2), calculate the shortest path length using the Floyd-Warshall algorithm.

   Hint

   Draw out the matrix and visualize the longest paths in each step for clarification.

6. 6.

   Explain in detail how the algorithm adapts when it finds a negative edge weight, specifically in implementation.

   Hint

   Reflect on how the algorithm’s rules enforce checks for conditions in path optimizations.