1. All-pairs Shortest Paths

Let us now turn our attention to the All-pairs Shortest Paths problems, where we try to find the paths, shortest paths between every pair of vertices in a graph.

The All-pairs Shortest Paths problem is a fundamental question in graph theory where we seek to determine the shortest path between all possible pairs of vertices in a graph. This means for a graph with 'n' vertices, we should be able to know the shortest distance from vertex 1 to vertex 2, vertex 1 to vertex 3, and so on up to vertex n.

Imagine a navigation app that needs to inform you of the shortest travel time between various locations in a city. If the city is represented as a graph where intersections are vertices and the roads connecting them are edges with weights (representing distance or travel time), the All-pairs Shortest Paths problem is akin to finding the quickest routes between every pair of intersections.

We made the following observation on shortest paths that the shortest path even in the presence of negative weights will never loop, because we can always remove the loop without increasing the length of the path.

One key characteristic of shortest paths is that they do not contain any cycles (loops). If a path revisits a vertex, we can eliminate the cycle without making the path any longer. Therefore, in finding the shortest paths, we ensure that every vertex on the path is unique and that no vertex is repeated.

Think of a hiker on a trail. If the hiker walks in a circular path (loop) and returns to the same point, they don't gain any new ground. To get to their destination faster, they should avoid walking in circles and follow a direct route instead.

We will come up with an inductive solution of how to build up the shortest paths in terms of length and the vertices allowed in between.

The inductive approach to solving the All-pairs Shortest Paths involves building upon previously computed shortest paths. Initially, we can consider the paths between vertices using no intermediate vertices (direct edges). Then, we progressively allow more vertices to serve as intermediates, thereby expanding our path options and seeking potentially shorter routes.

Consider planning a journey from city A to city B. At first, you might only look for direct flights (no stops). Next, you might consider flights with one layover, then two layovers, and so forth, constantly searching for the quickest route as you add more potential connections.

We compute a quantity W k of ij to be the weight of the shortest path from i to j, where we restrict the vertices to be between 1 and k.

Here, W k(i, j) represents the minimum distance between vertex i and vertex j using only the first k vertices as intermediates. The base case, W 0(i, j), allows only the direct edge from i to j, if it exists. As we move up to W 1, W 2, etc., we include more vertices as possible intermediates to explore shorter paths.

If you want to travel between two countries, initially you might only consider direct flights. With each additional country you can connect through, such as adding a layover in a friendly airport, you might discover new, cheaper connecting flights that take you to your destination quicker.

This gives us an immediate algorithm which is called the Floyd-Warshall algorithm.

The Floyd-Warshall algorithm is a systematic method to compute the shortest paths between all pairs of vertices. It iteratively updates the shortest path table by considering each vertex as an intermediate vertex one by one. The algorithm maintains a matrix representation of paths that gets updated through each iteration, ultimately yielding the shortest paths for every pair of vertices.

Think of organizing a series of meetings in various city offices. Each time you add a new office as a consideration for meeting locations (intermediate vertex), you reassess all previous meeting plans to see if including this new location creates a quicker route between your starting and ending offices.

It is very easy to see that the complexity is order n cube, because you have n iterations and in each iteration, we are updating the entire matrix which has n square entries.

The time complexity of the Floyd-Warshall algorithm is O(n³), where 'n' is the number of vertices in the graph. This is because the algorithm involves three nested loops: the outer loop for the number of vertices (n), and the two inner loops scanning through all pairs of vertices to update their shortest path values.

Imagine preparing the fastest route for a delivery company that serves 'n' locations. Each time a new route is proposed, the delivery planner must check the potential path connections to every other location. As the delivery count increases (n), the time taken increases dramatically due to the multiple route checks at each stage (n³).

--