[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1527.0. ""Shortest Path" through a adjacency matrix" by WILLEE::ZELISKO () Wed Dec 04 1991 14:06

Would anyone have a Pascal example of determining the "shortest path"
through a adjacency matrix? I'm given a 2 dimensional array matrix 
which contains the individual distances between points of a connected 
graph. I need to determine given two points what is the shortest distance 
between those points within the matrix.

This is for a Discrete math course I am taking. Any help would
be greatly appreciated.

Thanks,
  Ed

T.RTitleUserPersonal
Name
DateLines
1527.1Here's a hintBUZON::BELDIN_RPull us together, not apartWed Dec 04 1991 15:165
Remember that the n'th power of an adjacency matrix gives the length of a
path using n legs.


Dick
1527.2another hintGUESS::DERAMODan D'Eramo, zfc::deramoWed Dec 04 1991 23:223
The n'th power under what operation?

Dan
1527.3A little more detailWILLEE::ZELISKOThu Dec 05 1991 09:5910
    I'm afraid I don't follow. I read through the ~~very~~ brief section
    I have for this in my text book and could not understand it. Looking
    at the actual graph with paper and pencil I can come up with the
    shortest path. But trying to develop some algorithm is something
    else.....
    
    Any other suggestions????
    
    > Ed <
    
1527.4This hint is too precise!PULPO::BELDIN_RPull us together, not apartThu Dec 05 1991 10:0512
Make a matrix like the adjacency matrix (called X) but with all the
distances replaced by one.  Call this matrix Y.

Y * Y tells you whether there is a path of two legs.

Y * Y * Y tells you about 3 legged paths.

X * Y * Y gives the length of two legged paths.

X * Y * Y * Y gives the length of three legged paths.

Dick
1527.5puzzledELIS::GARSONV+F = E+2Wed Dec 11 1991 05:179
re .4
    
>                         -< This hint is too precise! >-
    
    Not for me, it isn't.
    
    I'm probably being thick here but this isn't working for me.
    
    Can you provide a small example?
1527.6I almost came back and retracted .4, it's wrongPULPO::BELDIN_RPull us together, not apartWed Dec 11 1991 09:030
1527.7ZFC::deramoDan D'EramoWed Dec 11 1991 11:5852
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
1527.8ELIS::GARSONV+F = E+2Thu Dec 12 1991 04:453
    re .-1
    
    Ah, glimmers of understanding and a few lines of APL.
1527.9Floyd vs Dijkstra's algorithmWILLEE::ZELISKOFri Dec 13 1991 13:557
    RE: .7
    Great explanation Dan, from my reasearch in other texts what you
    described is "Floyds" algorithm. What I need an example of is
    "Dijkstra's" algorithm.
    
    Ed
    
1527.10GUESS::DERAMODan D'Eramo, zfc::deramoFri Dec 13 1991 15:1844
        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
1527.11A working sample & data fileWILLEE::ZELISKOTue Dec 17 1991 15:46121
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