**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*/ }