1.1. Introduction to 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.

So, recall that we are working with weighted graphs, we allow negative edge weights, but not negative cycles, because with negative cycles our shortest path is not well defined, with negative weights, it is well defined.

The All-pairs Shortest Paths problem is about finding the shortest paths between every pair of vertices in a graph. This graph can have weights on its edges, which means that some paths may be longer or shorter depending on the weight, or cost, of traveling along them. Negative edge weights are allowed, meaning that some paths can cost less than nothing, but we have to avoid negative cycles. A negative cycle is when you can go around a set of vertices and end up with a lower total weight than you started, making the shortest path undefined.

Imagine you're using a navigation app to find the best route between multiple locations. The app must calculate the shortest way to travel between every pair of locations, considering aspects like traffic (edge weights). If a road usually charges a toll (negative weight), it might provide a quicker route that overall saves time compared to longer routes, but if there are loops that keep bringing you back to the same place, it could confuse the calculations just like negative cycles do.

So, we want to further generalize this and compute not just the shortest paths from a single source, but the shortest path between every pair of vertices. We made the following observation of 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.

To compute more broadly, we observe that the shortest path will never revisit a vertex—if it did, we could simply skip that vertex and find a shorter path instead. This means that each path from vertex i to vertex j will consist of unique vertices, and its length will be a maximum of n-1, where n is the total number of vertices in the graph. This observation allows us to create an inductive algorithm that builds the shortest paths step-by-step by recalling which vertices we are allowed to include along the way.

Think of it like sending out invitations for a party while trying to limit the number of people you reach out to. If you keep inviting the same group of friends (looping back), you can't get invitations to new friends in time, and hence, you won't increase your party size effectively. Each step forward means considering only unique individuals until you've maximized your connections without redundancy.

So, recall that vertices are numbered 1 to n, so we will compute a quantity W k of i j to be the weight of the shortest path from i to j, where we restrict the vertices that can be used go from i to j to be between 1 and k.

In our calculation to find the shortest path, we will use a method called induction. We define a weight matrix W where each entry W_k(i, j) represents the weight of the shortest path between vertices i and j, limiting the intermediate vertices we can use to those numbered 1 through k. This means as we increase k, we are gradually introducing more vertices into our paths and seeing how it affects the weight, or cost, of getting between i and j.

Imagine you're trying to create a journey plan between cities where you can only stop at certain cities. First, you might only allow stops at cities numbered 1 and 2, then later you allow city 3. As you allow more cities, you'll see if these new stops make your journey shorter or longer. The inductive process helps analyze paths gradually.

if k is 0, because our numbering is 1 to n, it says that the vertices that can appear cannot be include 1. In other words, if I have W 0, then it says all of the vertices 1 to n cannot appear on the paths, so the only way that we can 3 such a shortest paths is to the direct edge.

In the base case where k equals 0, we can only consider direct edges between vertices because no intermediate vertices are allowed. This means that W_0(i, j) can only be the direct edge weight between i and j or infinity if no such edge exists. This serves as our starting point before we begin allowing other vertices into our paths.

Think of trying to send a package directly from one city (vertex) to another. If you can't go through any other city, the only option is to take the shortest available road between them. If that road isn't available, the delivery can't happen—just like the infinity scenario for nonexistent edges.

Now, how do I compute the shortest paths reduce 1 to k. We know among all the paths which use at most 1 to k minus 1, what is the shortest path from i to j, how do we now compute, if we allow vertex k also to be used?

To compute the shortest path when we introduce the k-th vertex, we consider two scenarios. First, if including vertex k does not help us find a shorter path, then the shortest distance remains the same as before (W_k(i, j) = W_{k-1}(i, j)). But if including vertex k leads to a shorter path, we can express that path as passing through k: going from i to k and then from k to j, with each segment only using vertices allowed in the earlier stage (1 to k-1). Therefore, our new weight considers both the previously computed weights plus this new path.

Imagine a delivery route where now you can make a stop at a new warehouse (vertex k). You check if the route with this warehouse reduces overall travel time compared to just heading straight without it. Sometimes, stopping to refuel or sort packages at the new point makes the journey faster, while other times, the old route may still be quicker.

This gives us an immediate algorithm which is called the Floyd-Warshall algorithm. So, we start off with matrix representing the function W 0. So, W 0 has entries which are exactly the edge weight...

The Floyd-Warshall algorithm implements the inductive process we discussed to compute shortest paths for all pairs of vertices. It initializes a matrix W_0 with entry values as the edge weights. The algorithm then iteratively updates the matrix to consider each vertex as an intermediate point, ultimately capturing the shortest paths when all vertices can be used. This method is efficient and systematic, capturing results in a structured, layered way.

If we think of the algorithm as a city planner mapping out routes, it starts with direct streets. Then, in subsequent rounds, it revisits and updates routes while considering various shortcuts and stops until it has the best route for every connection in the city. This careful, step-wise process yields an efficient city map that all travelers can use.

--