1.7. Complexity Analysis of Floyd-Warshall Algorithm

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 Floyd-Warshall Algorithm is designed to find the shortest paths between every pair of vertices in a graph. This problem is known as the All-pairs Shortest Paths problem. The algorithm is particularly useful when you want to analyze the paths in weighted graphs, including those with negative edge weights, as long as there are no negative cycles.

Imagine planning a road trip across several cities. You want to know the shortest route between every possible pair of cities, considering the distance or time each road takes, even if some roads can decrease travel time (negetive weights) between certain points.

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.

A significant property of shortest paths in graphs is that they do not contain loops. This means if you could travel from vertex 'A' to vertex 'B', and you find a way that goes from 'A' to 'C', back to 'A', and then to 'B', you can ignore the part where you return to 'A' because it does not help in achieving a shorter overall path. This property is important for the efficiency and correctness of algorithms like Floyd-Warshall.

Think of a person trying to take a direct route to a destination. If they take a detour that brings them back to an earlier point and then continues onward, they can simply skip that detour to take the quicker direct route.

We are basically going to build up the shortest path in terms of vaguely by length, but most specifically what vertices we allowed in between

The Floyd-Warshall Algorithm builds the shortest paths incrementally. Initially, it considers paths that only contain direct edges. It then gradually allows more vertices to be used in forming paths. The main concept is to start from the simplest case and build up to allow more complexity, ensuring that all potential paths are evaluated for their costs.

Imagine building a multi-layered cake. You start with a plain base layer (direct routes) and then add more layers (intermediate vertices) one at a time, ensuring that each time you check that the cake remains stable and delicious (the shortest path).

Supposing we know the shortest paths that use 1 to k minus 1, how do I compute the shortest paths reduce 1 to k.

When the algorithm includes a new vertex 'k', it checks two scenarios to see if adding 'k' improves the shortest path from 'i' to 'j'. If the shortest path remains the same even when 'k' is included, it simply retains the previous value. If incorporating 'k' provides a shorter path, it recalculates the shortest path as the sum of the paths from 'i' to 'k' and from 'k' to 'j'. This method allows for efficient updating of the shortest paths.

Think of it like a navigation app adjusting your route. If a new road (vertex 'k') opens up and offers a shortcut from your current location (i) to your destination (j), the app checks if this new road provides a quicker route than the previously recommended path.

So, this gives us an immediate algorithm which is called the Floyd-Warshall algorithm. We start off with a matrix representing the function W 0.

The algorithm initializes a matrix that represents the weights of direct edges between all pairs of vertices. This is referred to as W0. It then iterates through all the vertices (from 1 to n), continuously updating the shortest path weights for each pair based on previously calculated values, expanding the set of considered vertices at each step.

Imagine someone managing a shipping company. They have a matrix that lists shipping times between all ports. Each round of updates represents checking with the latest shipping routes to see if adding a new port offers faster shipping routes between other ports.

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

The complexity of the Floyd-Warshall algorithm is O(n³). This is due to the fact that it performs n iterations on a matrix of n² entries to find the shortest paths. This cubic complexity means that as the number of vertices increases, the computational effort increases significantly.

Picture a school with n students, each needing to be matched with every other student for a project. If every student must meet with every other student before finishing their project (n³ efforts), the time taken grows very quickly as more students join the class.

So, we need to do these update exactly n times, so that after n times I capture the shortest way paths which include any arbitrary combination of vertices on the path.

While the algorithm appears to need O(n²) space due to the matrix representation of paths, it can be optimized to use just two copies of the matrix at any time. This reduces memory usage significantly while allowing the algorithm to function effectively.

Imagine a chef only needing two mixing bowls to prepare a complicated recipe. Instead of using a fresh bowl for every ingredient, the chef cleverly uses the same bowls, washing them between uses, thus saving on space and making cleanup easier.

--