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

*/