第一领券网-每天9.9元疯抢-taobao.dyboy.cn!

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实现的最短路径算法

 小东
 简介:有丰富WEB开发经验,WEB安全相关经验,已承接各类外包项目20+,专业团队为您打造产品,有合作意向请联系QQ:1099718640

在淘宝购物这么久,你居然不知道这个内部福利?

↓↓↓小伙伴们有任何问题都可以评论反馈的哦↓↓↓

发表评论

游客
送你一朵小花花~

帅人已评(0)