1. All-pairs Shortest Paths

Try these first

1. 1.

   Define the All-pairs Shortest Paths problem.

   Hint

   What does 'all-pairs' refer to?

2. 2.

   What does the Floyd-Warshall algorithm compute?

   Hint

   Recall the algorithm's purpose.

3. 3.

   What does the All-pairs Shortest Paths problem focus on?

   • Finding distances from one vertex
   • Finding distances between all pairs of vertices
   • Finding cycles

   Hint

   Think about what 'all-pairs' signifies.

4. 4.

   Is it true that the Bellman-Ford algorithm is applicable for finding all pairs shortest paths?

   • True
   • False

   Hint

   Consider how Bellman-Ford works and its extensions.

5. 5.

   In a directed graph defined by the following edges with their weights: (1, 2) = 10, (1, 3) = 5, (2, 3) = 2, (3, 1) = 6, apply the Floyd-Warshall algorithm step-by-step to find the distance matrix for all pairs of vertices.

   Hint

   Start with the initial weights and iteratively consider each vertex as an intermediate step.

6. 6.

   Analyze the impact of introducing a negative cycle in a graph, such as adding an edge with a weight of -5 between two already connected vertices, in relation to calculating the shortest paths.

   Hint

   Reflect on paths you've calculated before and consider how negative totals would affect them.