bellman-ford 有边数限制的最短路只能用bellman_ford

⬅ 返回

1、思路

解决图中可能存在重边和自环， 边权可能为负数。并且有边数限制的最短路只能用bellman_ford

📌

0.初始化dist数组为正无穷，dist[1]=0; 1.（外重循环）循环i从1到n，遍历n次指的：是不经过i条边到达终点的最短距离

经过n次操作n个点的最短距离也就确定了；

2.（内重循环）循环j从1到m，遍历m条边，把所有边都进行松弛操作；

每次取出两点以及他们连接的边的权重（a,b,w表示a—>b的一条边）；

用从起点到a的当前最短距离+权重来更新从起点到b的当前最短距离； dist[b]=min(dist[b],dist[a]+w);

3.返回答案；

2、所用的数据结构和方法

📌

dist[N]表示从起点到当前点的当前最短距离 backup[j]表示每次进入第2重循环的dist数组的备份

//用结构体来储存所有边

//备份 防止dist修改影响遍历

memcpy(backup, dist, sizeof dist);

3、代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define PI 3.14159
using namespace std;
 
typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e5+15;
const int mod = 1e9+7;
//用结构体来储存所有边
int n,m,k;
struct Edge{
	int a;
	int b;//表示a-b 之间有一条边 权值为c
	int c;
};
Edge e[N];
int dist[N],backup[N];
 
 
void solve()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].a>>e[i].b>>e[i].c;
	}
	memset(dist,0x3f,sizeof dist);
	
	dist[1]=0;//不要忘了让第一个点的距离为0
	for(int i=1;i<=k;i++)//遍历k次 k为边数限制 遍历k次不要求i从1开始
	{
		memcpy(backup,dist,sizeof dist);//备份 防止dist修改影响遍历
		for(int j=1;j<=m;j++)
		{
			int a = e[j].a;
			int b = e[j].b;
			int c = e[j].c;
			dist[b] = min(dist[b],backup[a]+c);//用备份的路径修改dist 或者说用上一次遍历的结果增加一条边
		}
	}
	if(dist[n]>=MAX_INT/2)
		cout<<"impossible"<<endl;// >的原因是因为存在负值 可能存在比无穷大 小1的情况 不能用等号
	else
		cout<<dist[n]<<endl;
	
	
 
}
 
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
    int T = 1;
    while(T--)
    {
        solve();
    }
}

4、例题

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。