Warshall's Algorithm

Warshall’s algorithm is a dynamic programming algorithm that uses a matrix to calculate the transitive closure of a graph. It works on by the principle of transitivity in binary relations, which states that if $(u,v)$ and $(u,w)$ exist on the graph $G$, then $(u,w)$ is an existing path.

Transitive closure is defined as:

Process §

Let $G$ be the graph which we are calculating the transitive closure of.

1. Initialise a square matrix, (using a 2-dimensional array) of size $|V|\times |V|$. Let $T$ be this matrix.
2. Convert $T$ to an adjacency matrix of $G$ by a nested for loop.
   1. For every node $u$ in $G$, loop through every node $v$ in $G$ and if an edge $(u,v)$ exists, set $T_{u,v}=1$. Else, set it to 0.
3. Use the transitive closure property:
   1. For every node $i$:
      1. For every node $j$
         1. For every node $k$, check if $T[i][k]\wedge T[k][j]$. i.e. there is a path from $i$ to $j$ via $k$
4. Return $T$. If $T[u][v]$ is 1, then there exists a path from $u$ to $v$.

Warshall’s Algorithm uses dynamic programming because it:

• Splits problem into sub-problems: The problem of finding all paths between any two nodes $i$ and $j$ in a graph has a trivial and non-trivial section. It can be easily checked if $(i,j)$ exists, than a path of length 1 exists between $i$ and $j$. The non-trivial section is seeing if there is a path with any intermediate nodes. If a path between $(i,k)$ and $(k,j)$ exists (with $k\ne i,j$), then a path exists from $i$ to $j$ via $k$. Hence, we need to check whether $(k,j)$ and $(i,k)$ have paths. This is splitting into sub-problems.
• Uses overlapping solutions to sub-problems: When checking for paths between $(i,k)$ and $(i,j)$ (our sub-problems), any paths that start with $i$ and make use of $k$ as an intermediate node will benefit from the solution to $(i,k)$. Hence, the solution of sub-problems can overlap.

As a recurrence relation, this can be expressed as:

$$T_{i,j}^k=\{\begin{array}{ll}{A}_{i,j},& k=0\\ T_{i,j}^{k-1}\vee (T_{i,k}^{k-1}\wedge T_{k,j}^{k-1}),& 0<k\le |V|\end{array}$$

Pseudocode §

Simple §

Algorithm Transitive_Closure(G):
	T ← |V| x |V| array
	
	//Initialise the T matrix
	For i from 1 to |V| do:
		For j from 1 to |V| do:
			If i=j or edge i-j exists in G then:
				T[i][j] ← 1
			Else:
				T[i][j] ← 0
			End if
		End do
	End do

	For k from 1 to |V| do:
		From i from 1 to |V| do:
			From j from 1 to |V| do:
				If T[i][k] = 1 AND T[k][j] = 1 then:
					T[i][j] ← 1
				End if
			End do
		End do
	End do
	Return T
End Algorithm

Slightly Improved §

Since the equality check $T[i][k]=1$ does not depend on $j$, it can be moved outside the j-loop, which does not change the time complexity, but does make it faster in real-time:

Algorithm Transitive_Closure(G):

	...
	
	For k from 1 to |V| do:
		From i from 1 to |V| do:
			If T[i][k] = 1 then:
				From j from 1 to |V| do:
					If T[k][j] = 1 then:
						T[i][j] ← 1
					End if
				End do
			End if
		End do
	End do
	Return T
End Algorithm

Time Complexity §

The time complexity of Warshall’s Algorithm is relatively straightforward. It consists of three nested for loops, each running for $\Theta (|V|)$ times, giving a time complexity of:

$$\Theta (|V|{)}^3=\Theta (|V{|}^3)$$

This time complexity applies for all cases:

Case Scenario	Input Description	Growth Function	Asymptotic	Notes
Worst			$\Theta (\Vert V{\Vert }^3)$	Time complexity is same for every case
Average			$\Theta (\Vert V{\Vert }^3)$
Best			$\Theta (\Vert V{\Vert }^3)$

Implementation §