题目描述
首先为什么dijkstra算法不适用于存在负权边的问题?
因为在dijkstra算法中每次利用最小的一个未标记的点对其他距离的点进行更新,可能会导致存在某一点被多次更新,使答案最终距离更小,因为每一次更新距离不能确定更新的一定是最小值
而bellman_ford算法则是枚举每一条边,对每一条边的进行松弛操作,使得操作后,该点到原点距离一定最短
其中存在一些问题:
(1)为什么要memcpy()保存d上一次更新的值?
因为受到一定边数k的限制,每次更新都受到本次更新的点的影响,导致被更新的点影响其他的点,导致更多的点变化,因此用memcpy()保存上一次的点的距离
(2)为什么是d[n] > 0x3f3f3f3f / 2?
因为该图可能包含负权边,所以若没有更新到n点,但是可以通过与n联通的边更新d[n],而这些联通的点可能是负权边
样例
#include<iostream>
#include<cstring>
using namespace std;
const int N = 550, M = 10100;
struct Point
{
int x, y, t; //x到y的边权是t
}point[M];
int n, m, k;
int d[N];
int last[N];
void bellman_ford()
{
memset(d, 0x3f, sizeof(d));
d[1] = 0;
for(int i = 0; i < k; i++)
{
memcpy(last, d, sizeof(d)); //每一次只对一个节点的子边进行更新,保证这一次更新不会受到其他点更新的影响
for(int j = 0; j < m; j++) //对每个点到原点的距离进行松弛操作
{
auto tem = point[j];
d[tem.y] = min(d[tem.y], last[tem.x] + tem.t); //原点到tem.y点的距离和原点到上一次更新的tem.x再到tem.y的距离的最小值
}
}
}
int main()
{
cin >> n >> m >> k;
for(int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
point[i] = {a, b, c};
}
bellman_ford();
if(d[n] > 0x3f3f3f3f / 2) cout << "impossible";
else cout << d[n];
return 0 ;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla