bellman-ford
bellman-ford（贝尔曼—福德）算法介绍1. 对每条边进行|V|-1次Relax操作;
2. 如果存在(u,v)∈E使得dis[u]+w(u,v)<dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。
程序代码/*如何用bellman-ford判断存在负权回路《算法导论》P362(在此算法中未体现，时间复杂度O（VE）)*/
#include <iostream>
#include <climits>
using namespace std;
struct node { //记录每条边的三个属性
int a, b, c;
};
node brr[10];
int arr[10][10];
int main(void) {
int m, n, a, b, c;
cin >> m >> n;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
arr[j] = INT_MAX;
for (int i = 0; i < n; i++) {
cin >> a >> b >> c;
arr[a] = c;
brr.a = a;
brr.b = b;
brr.c = c;
}
for (int i = 0; i < m-1; i++) //点
for (int j = 0; j < n; j++) { //边
if (arr[1].a] != INT_MAX && arr[1].a]
+ brr[j].c < arr[1].b])
arr[1].b] = arr[1].a] + brr[j].c;
}
for (int i = 2; i <= m; i++) {
if (arr[1] == INT_MAX) {
cout << 1 << "-->" << i << ": " << "no exit" << endl;
} else
cout << 1 << "-->" << i << ": " << arr[1] << endl;
}
return 0;
}
/*
6 8
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
1-->2: no exit!
1-->3: 10
1-->4: 50
1-->5: 30
1-->6: 60
*/