20.6. Updating W Matrices

So, now Warshall’s algorithm boils down to the following that how exactly I am going to update my matrix W to the matrix W and as per my definition the i, jth entry in the matrix, W is 1 provided I have a valid path satisfying the restriction that the intermediate nodes are within the subset 1 to k – 1 and I want, assuming I have already computed matrix W , my goal is how to find out the matrix W , where, I am allowing you to include node number k as well, as a possible intermediate node.

In this setup of Warshall’s algorithm, we need to figure out how to change the matrix W (which represents a certain state of paths among nodes) into a new matrix W that accounts for an additional node (node k) as a potential intermediate node in the paths. The update is significant because it helps determine if there is a path from node i to node j that can factor in paths through node k, without having to recompute everything from scratch.

Imagine you are trying to find the best route between two cities, and you already have information on certain direct routes. Now, suppose a new road opens (like our new node k); the goal is to see whether this new road makes previously impossible routes workable without having to redraw your entire map. You can explore routes just using the new road and see how they connect to existing roads.

If your i, jth entry in the matrix W is 1 then I can simply say that i, jth entry in matrix W will also be 1 and this is because any valid path from node i to j where the intermediate nodes are within the subset 1 to k - 1 can also be considered as a valid path, where the intermediate nodes are restricted within the subset 1 to k.

This scenario outlines a straightforward condition. If we already know there is a path from node i to node j in the previous version (W), indicated by the entry being 1, we can immediately assume that the same path remains valid in the current version (W) as long as we are only extending the range of possible intermediate nodes to include k. Thus, there’s no need to change this entry in the new matrix – it stays as 1.

Think of a situation where you have access to a library that only includes books from authors A to C. If you already know that there’s a direct reference in a book by author A to a book by author C, and now you add books from author D into your library, you still have the original reference – it hasn’t changed just because you have more books available.

My claim here is that if in the (k – 1)th matrix the i, jth entry is 0. That means there was no valid path from the node i to node j where all intermediate nodes are restricted to the subset 1 to k - 1. No such path was there. Then what I will check is the following. I will check whether there exists a path from the node i to k where all the intermediate nodes are within the subset 1 to k - 1.

In this case, we start with the situation where no path exists from i to j in the prior matrix version. To potentially find a path in the new matrix (W), we check if there are paths from i to k and from k to j in the previous matrix (W(k-1)). If both these paths exist, we can conclude that a path from i to j can be established by going from i to k and then from k to j, utilizing the new intermediate node.

Consider that you are trying to reach a friend (node j) through another friend (node k). If until now you didn’t have a direct link to your friend, first you would check if you can reach the intermediary friend (node k) and if that friend can in turn reach your target friend (node j). If both routes are valid, then you can successfully reach your friend despite the gaps.

So, what I can say is that I can summarize the two cases for updating the i, jth entry from the previous matrix to the new matrix as follows. If in the previous matrix i, jth entry is already 1, I will say that even in the new matrix the i, jth entry will be 1. Else I will check whether the i, kth entry as well as the k, jth entry are simultaneously 1 in the previous matrix and if that is the case I can say that i, jth entry in the updated matrix is also 1.

This final summary encapsulates how we manage the updates for each entry going from W(k-1) to W(k). It delineates the two scenarios effectively: either you have an existing path (the entry remains 1), or no such path exists and you must check intermediary connections through the new node to see if a route can be established. This step-wise check ensures that the new matrix is comprehensive and reflects all possible paths using the newly included intermediates.

Imagine you have a task list. If you've already marked a task as done, it stays done irrespective of new tasks added. On the other hand, if the task was incomplete, you would verify with available resources to see if it could still be completed using newly available tools or connections. This approach allows you to keep your task list accurate and up-to-date.

--