#include <iostream.h>
        #include "matrix.h"

/* START: Fig10_53.txt */
        const int NOT_A_VERTEX = -1;

        /**
         * Compute all-shortest paths.
         * a[ ][ ]contains the adjacency matrix with
         * a[ i ][ i ] presumed to be zero.
         * d[ ] contains the values of the shortest path.
         * Vertices are numbered starting at 0; all arrays
         * have equal dimension. A negative cycle exists if
         * d[ i ][ i ] is set to a negative value.
         * Actual path can be computed using path[ ][ ].
         * NOT_A_VERTEX is -1
         */
        void allPairs( const matrix<int> & a,
                       matrix<int> & d, matrix<int> & path ) 
        {
            int n = a.numrows( );

            // Initialize d and path
/* 1*/      for( int i = 0; i < n; i++ )
/* 2*/          for( int j = 0; j < n; j++ )
                {
/* 3*/              d[ i ][ j ] = a[ i ][ j ];
/* 4*/              path[ i ][ j ] = NOT_A_VERTEX;
                }

/* 5*/      for( int k = 0; k < n; k++ )
                // Consider each vertex as an intermediate
/* 6*/          for( int i = 0; i < n; i++ )
/* 7*/              for( int j = 0; j < n; j++ )
/* 8*/                  if( d[ i ][ k ] + d[ k ][ j ] < d[ i ][ j ] )
                        {
                            // Update shortest path
/* 9*/                      d[ i ][ j ] = d[ i ][ k ] + d[ k ][ j ];
/*10*/                      path[ i ][ j ] = k;
                        }
        }
/* END */

        int main( )
        {
            matrix<int> a( 4, 4 );
            a[ 0 ][0 ] = 0; a[ 0 ][ 1 ] = 2; a[ 0 ][ 2 ] = -2; a[ 0 ][ 3 ] = 2;
            a[ 1 ][ 0 ] = 1000; a[ 1 ][ 1 ] = 0; a[ 1 ][ 2 ] = -3; a[ 1 ][ 3 ] = 1000;
            a[ 2 ][ 0 ] = 4; a[ 2 ][ 1 ] = 1000; a[ 2 ][ 2 ] = 0; a[ 2 ][ 3 ] = 1000;
            a[ 3 ][ 0 ] = 1000; a[ 3 ][ 1 ] = -2; a[ 3 ][ 2 ] = 3; a[ 3 ][ 3 ] = 0;

            matrix<int> d( 4, 4 );
            matrix<int> path( 4, 4 );

            allPairs( a, d, path );
            int i;
            for( i = 0; i < d.numrows( ); i++ )
            {
                for( int j = 0; j < d.numcols( ); j++ )
                    cout << d[ i ][ j ] << "    " ;
                cout << endl;
            }
            for( i = 0; i < path.numrows( ); i++ )
            {
                for( int j = 0; j < path.numcols( ); j++ )
                    cout << path[ i ][ j ] << "    " ;
                cout << endl;
            }

            return 0;
        }