当前位置: 代码迷 >> 综合 >> BELLMAN-FORD算法 求有边数限制的最短路
  详细解决方案

BELLMAN-FORD算法 求有边数限制的最短路

热度:40   发布时间:2023-12-05 17:15:45.0

这个算法也是紧承我们之前讲过的关于图论的内容,我们在前面分析图的时候说过了对于不同的图论问题,我们会有不同的求解方法,那么这里我们讲到Bellman-Ford算法是用于解决有边数限制的求解最短路问题。

  

   我们先介绍一下我们之前讲过的Dijkstra算法为什么在这里失灵了,因为我们之前讲的Dijkstra算法是不适合求解含有负权边的最短路问题,原因如下图:

换言之,Dijkstra算法是找距离源点最近的点取更新别的点,这是一种贪心的思想,但是在具有负权边的问题时,局部最优解不一定是全局最优解,因为存在负权边,导致一开始大的边也有可能小下去。

Bellman—Ford算法的核心:对每一条边都进行松弛操作   

每次松弛操作实际上是对相邻节点的访问(相当于广度优先搜索),第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过|m| - 1条边,所以可知Bellman—Ford算法所得为最短路径,也可知时间复杂度为O(mn)。

代码:

#include<bits/stdc++.h>
#define maxn 510
#define maxm 10010

using namespace std;
int dist[maxn],backup[maxn],n,m,k;

struct EDGE{
int x,y,z;
}edge[maxm];

void bellman_ford(){
memset(dist , 0x3f , sizeof(dist));
dist[1] = 0;
for(int i = 1; i<=k; i++){
memcpy(backup,dist,sizeof(dist));
for(int j = 1; j<=m; j++){
int a = edge[j].x , b = edge[j].y , w = edge[j].z ;
dist[b] = min(dist[b],backup[a] + w);
}
}
}

int main()
{
cin >> n >> m >> k;
for(int i = 1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
edge[i].x = a; edge[i].y = b; edge[i].z = c;
}

bellman_ford();
if(dist[n] > 0x3f3f3f3f/2) cout << "impossible" << '\n';
else cout << dist[n] << '\n';
return 0;
}

 分析:

·我们对dist数组还是初始化为0x3f3f3f3f,但是最后在判断的时候去要求  >=0x3f3f3f3f/2:

  这是因为我们在进行松弛操作的时候是对每一条边都进行的, 所以本来时0x3f3f3f3f的地方可能被有负权边的路径给更新,所以我们只要保证他在一个量级就行了!

· 我们在每一次更新数值的时候,我们发现用到了一个backup数组,这个是用来干什么的呢:

  我们在按顺序更新数值的时候,我们如果直接用dist数组直接更新,有可能会导致前一个刚被更新的紧接着去更新下一个,这样就不能保证边数的限制了!

所以我们就要把上一次的值copy到backup数组中!

 

  相关解决方案