**fig10_53.txt**

/* 1*/	// Compute All-Shortest Paths.
/* 2*/	// A[ ] contains the adjacency matrix with.
/* 3*/	// A[ i ][ i ] presumed to be zero.
/* 4*/	// D[ ] contains the values of the shortest path.
/* 5*/	// N is the number of vertices.
/* 6*/	// A negative cycle exists iff.
/* 7*/	// D[ i ][ i ] is set to a negative value.
/* 8*/	// Actual path can be computed using Path[ ].
/* 9*/	// All arrays are indexed starting at 0.
/*10*/	// Not_A_Vertex is -1.

/*11*/	void
/*12*/	All_Pairs( const Two_D_Array A, Two_D_Array D,
/*13*/	                Two_D_Array Path, const int N )
/*14*/	{
/*15*/	    int i, j, k;

/*16*/	    for( i = 0; i < N; i++ )	// Initialize D and Path.
/*17*/	        for( j = 0; j < N; j++ )
/*18*/	        {
/*19*/	            D[ i ][ j ] = A[ i ][ j ];
/*20*/	            Path[ i ][ j ] = Not_A_Vertex;
/*21*/	        }

/*22*/	    for( k = 0; k < N; k++ )
/*23*/	        // Consider each vertex as an intermediate.
/*24*/	        for( i = 0; i < N; i++ )
/*25*/	            for( j = 0; j < N; j ++ )
/*26*/	                if( D[ i ][ k ] + D[ k ][ j ] < D[ i ][ j ] )
/*27*/	                {	// Update min.
/*28*/	                    D[ i ][ j ] = D[ i ][ k ] + D[ k ][ j ];
/*29*/	                    Path[ i ][ j ] = k;
/*30*/	                }
/*31*/	}