只有五行的算法》》Foloyd-Warshall算法（多元最短路径问题）

浏览数：44 / 时间：2015年06月08日 
#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;
}

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢