# 演算法 Bellman-Ford Algorithm

user_6817964
c_cpp
a year ago
1.8 kB
2
Indexable
Never
```int main()
{
int n, m, i[201], j[201], w[201], s;
scanf("%d%d", &n, &m);
for (int k = 1; k <= m; k++) {
scanf("%d%d%d", &i[k], &j[k], &w[k]);
}
scanf("%d", &s);

int key[51], parent[51], finish[51], ok = 0;
for (int k = 1; k <= n; k++) {
key[k] = 99999;
parent[k] = 0;
finish[k] = 0;
}
key[s] = 0;

int s_ori = s;

while (ok != n) {
int min = 99999;
for (int k = 1; k <= n; k++) {
if (key[k] < min && finish[k] == 0) {
min = key[k];
s = k;
}
}
finish[s] = 1;

for (int k = 1; k <= m; k++) {                       //比第二題多刪掉finish
if (s == i[k] && key[j[k]] > (w[k] + key[s])) {
key[j[k]] = w[k] + key[s];  // 比第一題多改這
parent[j[k]] = s;
}
}
ok++;
}

s = s_ori;
ok = 0;
int circle = 0;
while (ok != n) {
int min = 99999;
for (int k = 1; k <= n; k++) {
if (key[k] < min && finish[k] == 0) {
min = key[k];
s = k;
}
}
finish[s] = 1;

for (int k = 1; k <= m; k++) {
if (s == i[k] && key[j[k]] > (w[k] + key[s])) {
printf("There is a negative weight cycle in the graph");
circle = 1;
ok = n - 1;
}
}
ok++;
}

if (circle == 0) {
printf("%d", key[1]);
for (int k = 2; k <= n; k++) {
printf(" %d", key[k]);
}
printf("\n%d", parent[1]);
for (int k = 2; k <= n; k++) {
printf(" %d", parent[k]);
}
}
}```