1.10. Warshall's Algorithm and Transitive Closure

The original algorithm which was proposed by Warshall is for what is called transitive closure. So, transitive closure is exactly the same as computing the path from edge relation. So supposing you have a relationship like friend, so you know among a group of people, who is a direct friend of whom, then you might want to ask, who knows indirectly. So, I know somebody indirectly, if I have a friend, who knows that person or if I have a friend who has the friend knows that person and so on. So, knowing somebody indirectly is that transitive closure of the friend relation. In the same way in a general, I mean, so in every graph, if you put the friend, whatever relation, we want as the edge relation, the transitive closure is the path relation.

Transitive closure allows us to see the direct and indirect relationships between elements in a set. In our analogy, if person A is friends with person B and person B is friends with person C, then through transitive closure, we can conclude that person A indirectly knows person C. In the context of graphs, if we have a set of edges that represent connections between nodes, the transitive closure will tell us which nodes are reachable from one another, even if there isn't a direct edge connecting them.

Imagine a family tree. If you know that Alice is Bob's parent and Bob is Carol's parent, then through their transitive relationships, Alice is also a grandparent of Carol. This is the same concept: knowing indirect relationships helps to understand the entire connection between individuals.

So, we have an adjacency matrix which represents the edges, you want to compute a path matrix which represents the paths, which are the pairs of vertices computed by which are connected by paths. And so, Warshall described the similar algorithm, what we wrote now and we will just do it in a little detail in the next couple of slides to do this compute P from A and what Floyd is observed was you can adapt it as same algorithm.

Warshall's Algorithm uses an adjacency matrix to denote whether a direct edge exists between pairs of vertices. The goal is to construct a path matrix indicating the transitive closure, or reachability, between all pairs of vertices. The algorithm iterates through nodes and updates the path matrix based on already discovered paths, thus allowing it to build connections between non-direct neighbors through intermediate vertices.

Think of a road map where some roads are direct and some are only reachable via other roads. If you can travel from city A to city B, and from city B to city C, Warshall's algorithm helps us figure out that we can also travel from city A to city C, even if there’s no direct road linking them.

So, if there is a path already without using k, then I can just keep that path. So, we could either have that P k, I should remember now this is there a path is not the path. So, this is like an adjacency matrix, there is no weight, it was the 0, 1 matrix or a true false matrix. So, initially the adjacency matrix as 1 or true, whenever there is an edge, false whenever there is no edge. So, if I already got an entry true with k minus 1, then I can keep it. The other hand, maybe I do not have an entry true, after go back k, but one second that needs there is a path from i to k and there is a path from k to j and here I use only k minus 1 and here I use only k minus 1, because k needs to appear only once.

In Warshall's Algorithm, we maintain a path matrix P that tracks whether a path exists between every pair of vertices. If a path already exists without the current vertex k, we maintain that as it is. If it does not exist, we check if we can form a path from i to j through k, thus incorporating the new vertex into our pathfinding process. This systematic updating ensures all possible paths are considered.

Consider a group of friends looking to meet up. If person A knows person B directly, and person B knows person C directly, then A can still reach C through B, even if they have not met directly. Warshall's algorithm highlights these indirect connections, similar to how friends could introduce each other.

So, you initialize everything to false and then, again you should P for i is equal to 1 to n for j is equal to 1 to n. So, you initialize all the paths to false, when you set explicitly that is the zeroth level path at true, if there is an edge. And then, you keep updating the kth level path the either saying that there was already k minus 1 level path or I can find 2 k minus 1 level paths were intermediate level k in intermediate vertex k.

Before executing Warshall's algorithm, we start by initializing the path matrix P. Initially, we set all pairs to false, indicating no known paths. For the direct edges present in the graph, we set the corresponding entries in the matrix P to true. From there, we iteratively check for new paths using intermediate vertices and update the matrix based on found paths until all possibilities are accounted for.

Think of setting up a communication system in a new company. At first, you identify direct lines of communication (like emails) between employees. If you’re aware that some employees have mutual connections through others, like a friend who can connect two employees, you update the communication map to reflect these relationships over time.

--