1.3. Induction Setup for Shortest Paths

Try these first

1. 1.

   Define what is meant by All-pairs Shortest Paths.

   Hint

   Consider the necessity of comparing distances for multiple vertex pairs.

2. 2.

   What is a weighted graph?

   Hint

   Think about how distances are represented in a graph.

3. 3.

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

   • To find minimum spanning trees
   • To find shortest paths between all pairs of vertices
   • To find the largest cycle

   Hint

   Consider what the algorithm is focused on.

4. 4.

   True or False: The Floyd-Warshall algorithm can handle graphs with negative cycles.

   • True
   • False

   Hint

   Think about the impact of cycles on path definitions.

5. 5.

   Design a graph with vertices A, B, C, D, and edges with various weights including negative ones. Apply the Floyd-Warshall algorithm and determine all-pairs shortest paths.

   Hint

   Start initializing your weights based on direct edges then iterate through the vertex combinations.

6. 6.

   Discuss the implications of allowing negative weights in graphs. What types of real-world scenarios can affect the shortest path calculations?

   Hint

   Think about situations like city planning where costs might fluctuate or topographical changes could affect distances.