首页 > 代码库 > 只有五行的算法》》Foloyd-Warshall算法(多元最短路径问题)
只有五行的算法》》Foloyd-Warshall算法(多元最短路径问题)
#include<stdio.h>int main(){ int INF=9999999;//音节划分:无穷的 infinite int map[100][100]; int N,M; scanf("%d%d",&N,&M); int i,j; int k; for(i=1;i<=N;i++) for(j=1;j<=N;j++){ if(i==j) map[i][j]=0; else map[i][j]=INF; } int m; for(k=1;k<=M;k++){ scanf("%d%d%d",&i,&j,&m); map[i][j]=m; }//下面就是传说中的“只有五行的算法”——Floyd-Warshall//**************************************************** for(k=1;k<=N;k++) for(i=1;i<=N;i++) for(j=1;j<=N;j++) if(map[i][k]<INF&&map[k][j]<INF&&map[i][j]>map[i][k]+map[k][j]) //寻找i-->j最小距离 map[i][j]=map[i][k]+map[k][j];//****************************************************//下面就是传说中的“只有五行的算法”——Floyd-Warshall for(i=1;i<=N;i++) for(j=1;j<=N;j++) printf("%d-->%d: %d\n",i,j,map[i][j]); return 0;}
只有五行的算法》》Foloyd-Warshall算法(多元最短路径问题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。