1.6. Example to Illustrate 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. 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.

This section introduces the All-pairs Shortest Paths problem, which seeks to find the shortest paths between every pair of vertices in a graph. Here, graphs have weighted edges, meaning each connection has a cost associated with it. The mention of negative edge weights indicates that it's possible for the cost of a path to decrease as you traverse it, yet negative cycles must be avoided as they make the shortest path definition ambiguous.

Imagine you are planning a road trip where the cost of fuel varies. Some routes (edges) are cheaper than others (negative weights). If there’s a loop (negative cycle) that lets you continuously reduce your costs, it becomes unclear how much the trip would actually cost because you could drive around indefinitely.

So, you 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.

This chunk explains an important property of the shortest path: loops are not included in the optimal path. If a path goes back to a previous vertex (loop), it can be simplified by removing that segment without increasing the overall cost, meaning the shortest path does not revisit any vertex.

Consider navigating through a city. If you take a wrong turn that leads you back to where you started, you'd retrace your steps to avoid unnecessary travel. The same principle applies here: loops do not contribute positively to the optimal route.

We will come up with an inductive solution of how to build up the shortest paths. So, we are basically going to build up shortest path in terms of vaguely by length, but most specifically what vertices we allowed in between.

This part introduces the concept of building shortest paths inductively. The algorithm determines how to construct the shortest path by progressively allowing more vertices to be included in the path while still ensuring optimality is preserved.

Think of a teacher creating a group project. At first, only a few students (vertices) are allowed in the group (path). As more students are added, the teacher can reassess the best combination of group members to achieve the best project outcome (shortest path).

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 this segment, the section discusses how to define a distance matrix W_k that captures the shortest path between vertex i and vertex j using only the first k vertices. This structured approach aids in systematically determining shortest paths by gradually expanding the set of allowable vertices.

Imagine a school field trip where initially, students can only visit nearby attractions (1 to k). As the list of attractions expands (from 1 to n), the teacher can find better routes or activities involving more destinations.

So, in particular if k is 0, because our numbering is 1 to n, it says that the vertices that can appear cannot be include 1. So, 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 such a shortest paths is to the direct edge.

When k is set to 0, the only paths that are considered are direct edges between vertices with no use of intermediary vertices. This serves as the base case for the inductive approach, showing that without any intermediary vertices, the shortest path must simply be the direct edge if it exists.

Picture two towns connected solely by a single highway. If you can't take any detours (k=0), the only way to travel is directly via that highway, emphasizing the concept of the most basic route configuration.

So, now since this is an inductive definition, what we have to say is, supposing we know the shortest paths which use 1 to k minus 1, then how do I compute the shortest paths reduce 1 to k.

The section explains how, based on the knowledge of previously computed shortest paths (for 1 to k-1), it is possible to compute the shortest paths considering an additional vertex (k). This iterative inclusion process helps progressively build the solution.

This can be likened to assembling a jigsaw puzzle. As you complete sections of the puzzle (1 to k-1), including new pieces (k) allows you to see more of the big picture and refine the details.

So, combing the cases, we say that either we do not use k in which case, we take the value of the old matrix or you do use k and which case we combine two entries going i or k in the old matrix, we will take the smaller of these two.

This part explains the decision-making process for determining the shortest path. If including vertex k does not improve the path from i to j, the previous shortest path value is retained. Alternatively, if including k offers a better path, this new combined path weight is used. This ensures the optimal solution is upheld.

Imagine a map with detours. If a new road (vertex k) opens up but doesn't shorten your travel time compared to staying on the main road, you'd choose the main road. However, if the new road provides a faster route, you’d opt for that.

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

The Floyd-Warshall algorithm is presented as a solution to compute the shortest paths in a graph using previously defined methods. The algorithm begins with a matrix that encapsulates the initial shortest paths and then iteratively improves upon it by considering additional vertices.

Think about a delivery service optimizing its routes over time. It starts with a basic map of current routes (W_0), and as it learns new paths (through analysis), it gradually adjusts its operations to ensure the fastest deliveries.

So, the actual code is again like Bellman-Ford extremely straightforward. You just have first initialization which sets every way to infinity and then updates the non trivial weights for those edges which had the graphs.

The complexity of the Floyd-Warshall algorithm is discussed. It emphasizes that the process involves setting up the shortest path matrix and performing updates iteratively, resulting in a time complexity of O(n^3), where n represents the number of vertices. This is because for each vertex, the algorithm checks all combinations of paths.

Consider preparing for a family reunion with numerous attendees (vertices). You might examine each person's travel options (paths) to determine the quickest routes, but since there are many attendees, this can become time-consuming (O(n^3)).

--