Floyd多源最短路算法

2021-05-02 07:28

阅读：650

标签：顶点 init rsh 初始化 clu sha war c++ 赋值

其实没什么好说的，从点 i 到点 j ，除了直接一条边连接直通还可以通过别的边中转得到，这样就得到了一个类似dp的一个状态转移方程。但是注意：1.Floyd必须用邻接矩阵存图。2.不能解决负环问题。

#include using namespace std;
int main()  
{  
    int e[10][10],k,i,j,n,m,t1,t2,t3;  
    int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
    //读入n和m，n表示顶点个数，m表示边的条数
    scanf("%d %d",&n,&m);  
    //初始化
    for(i=1;i)  
        for(j=1;j)  
            if(i==j) e[i][j]=0;//自己到自己当然不需要任何代价    
            else e[i][j]=inf;//其它没有直通边的都赋值为正无穷  
    //读入边
    for(i=1;i)  
        {  
            scanf("%d %d %d",&t1,&t2,&t3);  
            e[t1][t2]=t3;//邻接矩阵存图  
        }  
    //Floyd-Warshall算法核心语句
    for(k=1;k)  
        for(i=1;i)  
            for(j=1;j)  
                if(e[i][j]>e[i][k]+e[k][j] )   
                    e[i][j]=e[i][k]+e[k][j];  
     //输出最终的结果
    for(i=1;i)  
    {  
        for(j=1;j) 
            printf("%10d",e[i][j]);  
        printf("\n");  
    }  
    return 0;  
}

Floyd多源最短路算法

标签：顶点 init rsh 初始化 clu sha war c++ 赋值

原文地址：https://www.cnblogs.com/57xmz/p/13204110.html

上一篇：数据结构与算法(二) 线性表一

下一篇：解决java.lang.SecurityException: Invalid signature file digest for Manifest main attributes

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Floyd多源最短路算法
文章链接：http://soscw.com/index.php/essay/81230.html

亲，登录后才可以留言！

Floyd多源最短路算法

评论

热门文章

推荐文章

最新文章

置顶文章