Bellman-Ford Algorithm
user_3763047219
c_cpp
2 years ago
1.6 kB
7
Indexable
#include <iostream> int main() { int n = 0, m = 0, s = 0; scanf("%d %d", &n, &m); int weight[201][3] = {}; int key[201] = {}; for (int i = 1; i <= m; i++) { scanf("%d %d %d", &weight[i][0], &weight[i][1], &weight[i][2]); } for (int i = 1; i <= n; i++) { key[i] = 10001; } scanf("%d", &s); key[s] = 0; int count = 1; int v[201] = { 0 }; int parent[201] = { 0 }; v[s] = 1; while (count < n) { int eachkey = 10001; for (int i = 1; i <= m; i++) { if (key[weight[i][1]] > weight[i][2] + key[weight[i][0]]) { key[weight[i][1]] = weight[i][2] + key[weight[i][0]]; parent[weight[i][1]] = weight[i][0]; } } count = count + 1; } int sum1 = 0, sum2 = 0; for (int i = 1; i <= n; i++) { sum1 = sum1 + key[i]; } for (int i = 1; i <= m; i++) { if (key[weight[i][1]] > weight[i][2] + key[weight[i][0]]) { key[weight[i][1]] = weight[i][2] + key[weight[i][0]]; parent[weight[i][1]] = weight[i][0]; } } for (int i = 1; i <= n; i++) { sum2 = sum2 + key[i]; } if (sum1 != sum2) { printf("There is a negative weight cycle in the graph"); } else { for (int i = 1; i < n; i++) { printf("%d ", key[i]); } printf("%d\n", key[n]); for (int i = 1; i < n; i++) { printf("%d ", parent[i]); } printf("%d", parent[n]); } }
Editor is loading...