| When you multiply matrices A x B = C, you usually determine an
element of the product matrix C as follows
[ ... ] [ b(1,j) ]
[ a(i,1) a(i,2) ... a(i,m) ] * [ . b(2,j) . ] = C
[ ... ] [ . . . ]
[ . . . ]
[ . ]
[ b(m,j) ]
(n by m) (m by k) (n by k)
c(i,j) = a(i,1)b(1,j) + a(i,2)b(2,j) + ... + a(i,m)b(m,j)
Call this (+,*) matrix multiplication...you use the * operation
between elements and then use the + operation to combine the
results.
You can generalize this to any pair of binary operators (it helps
a lot if at least the first one is associative!).
If you do a (min,+) matrix multiplication on a square matrix A
where a(i,j) is the (nonnegative) distance from i to j, then
the (min,+) product A^2 has (i,j) entry equal to
min( a(i,1)+a(1,j), a(i,2)+a(2,j), ..., a(i,n)+a(n,j) )
= min( distance from i to j thru 1, ..., distance from i to j thru n )
= the shortest two step distance from i to j
Assuming a(i,i) = 0 for all i, this includes the minimum one step
distance from i to j as well, for example, i to j thru i. If you
can't get to j from i in one step, set that distance to the identity
element of the min operator, oo (or use a very large number).
If you compute A^n using (min,+) matrix multiplication, you get the
matrix of shortest distances from i to j along any path. I believe
this can be done faster than the obvious way.
Note the assumption of nonnegative distances. If a loop exists
with negative total distance then you go to the loop, go around it
many times, then go to your destination, and in so doing you can
get total distances that are more and more negative as you take more
trips around the loop.
If the entries were all 0 and 1, then (or,and) multiplication to
get A^n tells you whether you can get there from here (assuming 0
for false, 1 for true, and a(i,i) = 1).
There are books on algorithms that cover these graph/network/matrix
problems.
Dan
|
| The earlier note, what you called Floyd's algorithm,
describes computing the minimum distance (not the actual
path that accomplishes it, though) matrix for all pairs
of vertices. Dijkstra's algorithm computes the minimum
distance from one specific vertex to every vertex.
Checking a book on algorithms that someone down the hall
had...
inputs:
the number of vertices: n
the cost matrix: C(i,j) for 1 <= i,j <= n,
the starting vertex v: 1 <= v <= n
note: C(i,j) is set to some large number, + oo,
in the case edge (i,j) is not in the graph.
Each C(i,i) can be any nonnegative number.
output:
the distance array: d(i) 1 <= i <= n of distances
from vertex v to each of the n vertices
local variables:
Boolean array: S(i) 1 <= i <= n
integers: u, num, i, w
the steps of the algorithm:
for i in 1 to n do { s(i) <- 0 ; d(i) <- C(v,i) ; }
S(v) <- 1 ; d(v) <- 0 ;
for num in 2 to n-1 do {
choose u such that d(u) is the minimum of
the d(w) over all w with S(w) == 0 ;
S(u) <- 1 ;
for all w with S(w) == 0 do {
d(w) <- min(d(w), d(u)+C(u,w)) ;
}
}
Dan
|
|
Here is sample program that uses as input a 8x8 adjacency matrix.
The data file is included at the bottom.
PROGRAM SHORTEST_PATH (INPUT,OUTPUT,SHORTESTPATH);
CONST MAXNODES = 8;
TYPE NODEPTR = 1..MAXNODES;
WEIGHTMATRIX = ARRAY[NODEPTR,NODEPTR] OF INTEGER;
NODESET = SET OF NODEPTR;
NODEARRAY = ARRAY[NODEPTR] OF NODEPTR;
VAR
ROW,COL,LOOP_CNTR,COUNT : INTEGER;
WEIGHT,THEARRAY : WEIGHTMATRIX;
SHORTESTPATH : TEXT;
PROCEDURE LOAD_ARRAYS( VAR WEIGHT:WEIGHTMATRIX);
BEGIN
RESET (SHORTESTPATH);
READLN (SHORTESTPATH,COUNT);
FOR LOOP_CNTR := 1 TO COUNT DO
BEGIN
WRITELN;
FOR ROW := 1 TO MAXNODES DO
BEGIN
FOR COL := 1 TO MAXNODES DO
READ (SHORTESTPATH,WEIGHT[ROW,COL]);
END;
END;
END; (* End procedure Load_Arrays *)
PROCEDURE SHORTPATH( VAR WEIGHT:WEIGHTMATRIX);
VAR DISTANCE,travel: ARRAY[NODEPTR] OF INTEGER;
S,T,CURRENT,I,K:NODEPTR;
PERM:NODESET;
D,DC,SMALLDIST,NEWDIST:INTEGER;
PRECEDE:NODEARRAY;
j:INTEGER;
BEGIN
WRITE ('Enter your starting point :');
READLN (S);
WRITE ('Enter your ending point :');
READLN (T);
WRITELN;
WRITELN;
PERM:=[S];
FOR I:= 1 TO MAXNODES DO
DISTANCE[I]:= MAXINT;
DISTANCE[S]:=0;
CURRENT :=S;
WHILE(CURRENT<> T) DO
BEGIN
SMALLDIST:=MAXINT;
DC:= DISTANCE[CURRENT];
FOR I:= 1 TO MAXNODES DO
IF NOT (I IN PERM) THEN
BEGIN
NEWDIST := DC+WEIGHT[CURRENT,I];
IF NEWDIST < DISTANCE[I] THEN
BEGIN
DISTANCE[I] := NEWDIST;
PRECEDE[I] := CURRENT;
END;
IF DISTANCE[I] < SMALLDIST THEN
BEGIN
SMALLDIST := DISTANCE[I];
K:= I;
END;
END;
CURRENT := K;
PERM := PERM + [CURRENT];
END;
D := DISTANCE[T];
WRITELN('Shortest distance total weight :', D:3);
I := 1;
TRAVEL[I] := T;
J := T;
WHILE (S <> J) DO
BEGIN
I := I + 1;
TRAVEL[I] := PRECEDE[J];
J := TRAVEL[I];
END;
WRITE('Path traveled = ');
FOR J := I DOWNTO 1 DO
WRITE(TRAVEL[J]:3);
WRITELN;
END;
BEGIN (* MAIN *)
LOAD_ARRAYS (WEIGHT);
SHORTPATH (WEIGHT);
END.
------------- CUT HERE FOR DATA FILE ------------
1
99 3 5 99 8 1 99 99
3 99 2 99 99 99 1 99
5 2 99 1 99 99 99 2
99 99 1 99 4 99 99 99
8 99 99 4 99 6 99 1
1 99 99 99 6 99 5 99
99 1 99 99 99 5 99 1
99 99 2 99 1 99 1 99
|