# Bellman-Ford Algorithm

user_3763047219
c_cpp
2 years ago
1.6 kB
4
Indexable
Never
```#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]);
}
}```