Floyd实现的最短路径算法

【摘要】#include<stdio.h>#defineINF10000inte[5][5]={0,45,30,INF,50,45,0,INF,60,INF,30,INF,0,INF,45,I...

#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;
}
未经允许不得转载:第一资源网 » Floyd实现的最短路径算法

 小东
 简介:专业团队网站开发、安全运维,合作意向请联系!

扫码关注微信公众号:ITDYBOY,学前端,学安全,从0到1,从1到精通!

扫码关注微信公众号:ITDYBOY

发表评论

游客
送你一朵小花花~

帅人已评(13)