算法導論-C++實作-all pairs shortest paths-matrix multiplication算法

#include <iostream>

using namespace std;

#define matricsRow 100

int infinite=1000;

int nullValue=-1;

int **pi;

int **d;

int **W;

int ***L;

void extendShortestPaths(int ii,int n){

    int **C=new int*[matricsRow];

    for(int i=0;i<matricsRow;i++)

        C[i]=new int[matricsRow];

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++){

            C[i][j]=infinite;

            for(int k=0;k<n;k++){

                if(C[i][j]>L[ii][i][k]+W[k][j])

                    C[i][j]=L[ii][i][k]+W[k][j];

            }

        }

    }

    L[ii]=C;

}

void slowAllPairsShortestPaths(int n){

    L[0]=W;

    for(int i=1;i<n-1;i++){

        extendShortestPaths(i-1,n);

    }

}

void printAllPairsShortestPath(int i,int j){

    if(i==j){

        cout<<i;

    }

    else if (pi[i][j]==nullValue){

        cout<<endl;

        cout<<"no path from "<<i<<" to "<<j<<" exists"<<endl;

    }

    else{

        printAllPairsShortestPath(pi,i,pi[i][j]);

        cout<<j;

    }

}

void initialize(){

    pi=new int*[matricsRow];

    d=new int*[matricsRow];

    W=new int*[matricsRow];

    L=new int**[matricsRow];

    for(int i=0;i<matricsRow;i++){

        pi[i]=new int[matricsRow];

        d[i]=new int[matricsRow];

        W[i]=new int[matricsRow];

        L[i]=new int*[matricsRow];

        for(int j=0;j<matricsRow;j++){

            L[i][j]=new int[matricsRow];

        }

    }

    for(int i=0;i<matricsRow;i++){

        for(int j=0;j<matricsRow;j++){

//            cout<<i<<":"<<j<<endl;

            pi[i][j]=nullValue;

            W[i][j]=infinite;

        }

    }

    cout<<"initialization of W values finished"<<endl;

    W[0][0]=0;

    W[1][1]=0;

    W[2][2]=0;

    W[3][3]=0;

    W[4][4]=0;

    W[0][1]=3;

    W[0][2]=8;

    W[0][4]=-4;

    W[1][3]=1;

    W[1][4]=7;

    W[2][1]=4;

    W[3][0]=2;

    W[3][2]=-5;

    W[4][3]=6;

    cout<<"initialize finished"<<endl;

}

int main(){

    cout<<"program begins"<<endl;

    initialize();

    slowAllPairsShortestPaths(5);

    printAllPairsShortestPath(0,1);

    return 0;

}