首页 > 代码库 > 只有五行的算法》》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算法(多元最短路径问题)