 |
 |
 |
In this problem we want the minimum routes (m.r.) between all the pairs of the peaks of G. The Floyd algorithm solves this problem.This algorithm is an expansion of another algorithm,the Warshall algorithm,who was first defined for the solution of another problem:
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 WARSHALL for
the Warshall Algorithm.
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 FLOYD for the
Floyd Algorithm.
The complexity of the Floyd Algorithm is (in the worst case):O(n3).
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(n2),the algorithm will solve the problem in time : O(n3).By use of other data structures the Dijkstra Algorithm will require O(mnlogn) 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