[C++]Floyd最短路径算法

Floyd最短路径的算法实现C++

#include <stdio.h>
#define INF 10000
int e[5][5]={
0,45,30,INF,50,
            45,0,INF,60,INF,
            30,INF,0,INF,45,
            INF,60,INF,0,55,
            50,INF,45,55,0
};

int path[5][5] = {0};

void floyd(){
    int i,j,k;
    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
            for(k=0;k<5;k++)
                if(e[i][k]<INF&&e[k][j]<INF&&e[i][j]>e[i][k]+e[k][j]){
                    e[i][j] = e[i][k] + e[k][j];
                    path[i][j] = k;
                }
}

void getPath(int i ,int j){
    if(i==j) return;
    if(path[i][j]==0) printf("%c ",j+'a');
    else{
        getPath(i,path[i][j]);
        getPath(path[i][j],j);
    }

}

int main(){
    char start,end;
    printf("输入起点编号和终点编号：");
    scanf("%c %c",&start,&end);
    floyd();
    int m,n;
    for(m=0;m<4;m++){
        for(n=0;n<4;n++){
            printf("%d",path[m][n]);
        }
    }

    printf("最短路径为：%d，具体如下：\n%c ",e[start-'a'][end-'a'],start);
    getPath(start-'a',end-'a');
    return 0;
}