Floyd算法

2008-11-13 17:43

#include<iostream>
using namespace std;

const int N = 10000000;

int matrix[10][10] = {{0,2,3,1,12,15},
                    {2,0,2,5,3,12},
                    {3,2,0,3,6,5},
                    {1,5,3,0,7,9},
                    {12,3,6,7,0,2},
                    {15,12,5,9,2,0}};
int vexnum = 6;
int D[10][10];

void Floyd();

int main(void){
    int i,j;
   
    Floyd();
   
    for(i=0;i<vexnum;i++){
        for(j=0;j<vexnum;j++)
            cout<<"D["<<i<<"]["<<j<<"]:"<<D[i][j]<<"\t";
        cout<<endl;
    }
   
    system("pause");
    return 0;
}

void Floyd(){
     int i,j,k;
    
     //init

     for(i=0;i<vexnum;i++)
         for(j=0;j<vexnum;j++)
             D[i][j] = matrix[i][j];
     for(i=0;i<vexnum;i++)
         D[i][i] = 0;
               
     //Floyd

     for(i=0;i<vexnum;i++)
         for(j=0;j<vexnum;j++)
             for(k=0;k<vexnum;k++){
                 if(matrix[i][k]==N||matrix[k][j]==N) continue;
                 if(D[i][k]+D[k][j]<D[i][j])
                    D[i][j] = D[i][k] + D[k][j];
             }
}