登录注册

关于 合作 投稿 帮助 赞助 Sitemap RSS

免费网站源码∣网站模板∣微信小程序∣ppt模板∣织梦模板下载就选-叮当猫资源网logo

Floyd实现的最短路径算法

2018-09-20jonnck互联网挑错收藏打印

#include stdio.h#define INF 10000int 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;i5;i++) for(j=0;j5;j++) for(k=0;k5;k++) if(e[i][k]INFe[k]
#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;
}

免责声明:本站所有资源除标明原创外,均来自互联网,不对任何资源负法律责任。如有侵犯您的版权,请及时联系我们删除!
说点什么吧
  • 全部评论(0
    还没有评论,快来抢沙发吧!

返回顶部