In this problem we want the** minimum routes (m.r.)**
between all the pairs of the peaks of

*In a digraph G (whether there are costs or not,is
of no importance) find whether there is a route from V**(i)** to V**(j)**,for all
pairs of (i,j) , i<>j. *

To solve this problem we find an array A.The elements of this
array are A(i,j)=1 if there is a route from
i to j,otherwise A(i,j)=0.Because the cost
is not important we define the Adjoining Array as if all the
costs were 1 that means C(i,j)=1 if there
is eij belonging to E and otherwise C(i,j)=0.The requested array A is called **transitive
closure** of the Adjoining Array.

We notice that the elements of the A array are Boolean variables(0 or 1),which means that the operations AND and OR are valid.The Warshall algorithm initializes the A array at the value of C:

A(i,j)=C(i,j), i,j=1,...,n

At this point the A array shows only the direct connections as
existing routes.Then the algorithm goes through the A array n
times,one time for every node k=1,....,n.For every node V(k) the main thinking is : Is there a route from
V(i) to V(j) ,if it
has already been found {that is A(i,j)=1] **or**
if a route is found through V(k),that is if the routes from V(i) to V(k)** and** from
V(k) to V(j)[that is
if A(i,k)=1 **and **A(k,j)=1].

If the BOOLEAN characteristics of the elements of A are taken
under consideration,then the rule in the k pass is:

**A****(i,j)****=A****(i,j)**** OR {A****(i,k)**** AND A****(k,j)**** }.
**Click

We now come back to the * m.r.* problem
for all pairs.This time we are talking about a graph,and the
Adjoining Array is defined by the costs C(i,j)=c(eij).The
A array will finally consist of all the costs of the minimum
routes.

During the k pass the following formula is valid:

**A****(i,j)****=min{A****(i,j)****,A****(i,k)**** + A****(k,j)**** ****}
**which means that if the route through V(k) is
cheaper will be the winner.That gives us the Floyd algorithm.

Click

The complexity of the Floyd Algorithm is (in the worst
case):O(n^{3}).

For the same problem the Dijkstra Algorithm could be used n
times(every time another starting point).Because every use of the
Adjoining Array demands complexity time of O(n^{2}),the
algorithm will solve the problem in time : O(n^{3}).By
use of other data structures the Dijkstra Algorithm will require **O(****mn****log****n****)***
*and for great n with few sides,it is a much better
algorithm.

The replacement of "**A****(i,j)****:=s**",with
the:

**begin A****(i,j)****:=s;P****(i,j)****:=k end**

creates a new array with the values k(equivalent to n(i) in the Prim and Dijkstra Algorithm),which is the pointer of the peak through which the connection for the minimum route is made.The initialization is P(i,j)=0.

HTML PAGE DIRECTOR :Papaioannou Panagiotis