gpt4 book ai didi

c++ Bellman-Ford算法的具体实现

转载 作者:qq735679552 更新时间:2022-09-27 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章c++ Bellman-Ford算法的具体实现由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

Bellman-Ford算法用于解决有边数限制的最短路问题,且可以应对有负边权的图 。

其时间复杂度为O(nm),效率较低 。

c++ Bellman-Ford算法的具体实现

代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e4+10;
const int M=510;
int m,n,k,dis[M],backup[M];
//m条边,n个点,在1号点到n号点之间找到一条经过小于等于k条边的通路
//dis:各点到源点的距离,backup:备份
struct Node
{
     int x,y,v;
}edge[N]; //可以直接用结构体存边
int Bellman_Ford()
{
     dis[1]=0;
     memset (dis,0x3f, sizeof dis);
     for ( int i=1;i<=k;i++)
     {
         memcpy (backup,dis, sizeof dis);
         for ( int j=1;j<=m;j++)
         {
             Node t=edge[j];
             dis[t.y]=min(dis[t.y],backup[t.x]+t.v);
         }
     }
     if (dis[n]>inf/2) return -1;
     return dis[n];
}
int main()
{
     cin>>n>>m>>k;
     for ( int i=1;i<=m;i++)
     {
         int a,b,c;
         cin>>a>>b>>c;
         edge[i]={a,b,c};
     }
     int ans=Bellman_Ford();
     if (ans==-1)     cout<< "impossible" ;
     else            cout<<ans;
     return 0;
  }

对代码中的重难点的解释:

1.backup备份数组存在的意义:每一次“迭代”后,实现对dis数组的当前状态进行保存 。

这里详细解释一下“迭代”的含义:此处的迭代即为从源点开始,对所到达的点的出边进行松弛 。

举个例子:有一个如下的图,1号点为源点 。

c++ Bellman-Ford算法的具体实现

第一次迭代 。

找到2,3号点到源点的最短距离 。

c++ Bellman-Ford算法的具体实现

第二次迭代 。

找到4,5号点到源点的最短距离 。

c++ Bellman-Ford算法的具体实现

第三次迭代 。

由于所有边都已被遍历,没有边能够被松弛,迭代结束 。

由刚才的过程可知,每一次迭代后要对dis数组进行备份,若一直使用dis数组进行运算,程序则会失去迭代的控制(在代码中迭代体现为Bellman-Ford函数中的外重循环,题目要求最多经过k条边,实际上就是最多有k次迭代) 。

2.代码的最后的判断 。

为什么是if(dis[n]>inf/2),而不是if(dis[n]==inf)呢?

原因是Bellman-Ford算法可能处理含负权边的图,dis[n]可能会出现+∞-2这样的数值,所以进行大小比较判断时条件只需要让dis[n]大于一个同数量级的数(此处为inf/2)即可 。

到此这篇关于c++ Bellman-Ford算法的具体实现的文章就介绍到这了,更多相关c++ Bellman-Ford内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我! 。

原文链接:https://blog.csdn.net/weixin_56057952/article/details/118278873 。

最后此篇关于c++ Bellman-Ford算法的具体实现的文章就讲到这里了,如果你想了解更多关于c++ Bellman-Ford算法的具体实现的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com