jtahstu的博客

1373758426   Git仓库   GitBook  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> Bellman_Ford算法 - 解决负权边

Bellman_Ford算法 - 解决负权边

1 介绍

  1. 这是一个单源最短路径算法,一般计算第1个点到后面的点的最短路径
  2. 相区别与Floyd_Warshall算法(参考 最简单的最短路径算法 - Floyd_Warshall算法)的是,前者使用n*n的矩阵存储,而这个算法使用三个长n的数组存储,所以前者容易开数组时就爆了
  3. 在本人看来,这个算法与Floyd_Warshall算法的本质是一样的,核心都是一个if判断大小后更新为较小值
  4. 算法时间复杂度是 : O(NM)

2 代码

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int dis[10],bak[10],n,m,u[10],v[10],w[10],check,flag;
    int inf=99999999;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>u[i]>>v[i]>>w[i];
    for(int i=1; i<=n; i++)
        dis[i]=inf;
    dis[1]=0;

    for(int k=1; k<=n-1; k++)   //算法核心
    {
        for(int i=1; i<=n; i++) //备份dis
            bak[i]=dis[i];

        for(int i=1; i<=m; i++) //进行一次松弛,主要就是这里
        {
            if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i];
        }

        //检测is数组是否有更新
        check=0;
        for(int i=1; i<=n; i++)
        {
            if(bak[i]!=dis[i])
            {
                check=1;
                break;
            }
        }
        if(check==0)
            break;
    }

    flag=0;
    for(int i=1; i<=m; i++)
        if(dis[v[i]]>dis[u[i]]+w[i])
            flag=1;
    if(flag==1)
        cout<<"此图有复权回路"<<endl;
    else
    {
        for(int i=1; i<=n; i++)
            cout<<dis[i]<<" ";
        cout<<endl;
    }
    return 0;
}
/*
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
*/

3 拓展链接

  1. Bellman-Ford算法详讲 - CSDN博客,该文章记录了路径
  2. 算法笔记_070-BellmanFord算法简单介绍(Java) - CSDN博客    

---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

50 + 90 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……