aboutsummaryrefslogtreecommitdiff
path: root/q2
diff options
context:
space:
mode:
Diffstat (limited to 'q2')
-rw-r--r--q2/ford.c78
1 files changed, 78 insertions, 0 deletions
diff --git a/q2/ford.c b/q2/ford.c
new file mode 100644
index 0000000..993a0c3
--- /dev/null
+++ b/q2/ford.c
@@ -0,0 +1,78 @@
1#include <stdio.h>
2
3int A[10][10], n, d[10], p[10];
4
5int bellman_ford() {
6 int i, u, v;
7 for (int i = 0; i < n; i++) {
8 for (u = 0; u < n; u++) {
9 for (v = 0; v < n; v++) {
10 if (d[v] > d[u] + A[u][v]) {
11 d[v] = d[u] + A[u][v];
12 p[v] = u;
13 }
14 }
15 }
16 }
17 for (u = 0; u < n; u++) {
18 for (v = 0; v < n; v++) {
19 if (d[v] > d[u] + A[u][v]) {
20 printf("Detected negative edge\n");
21 return -1;
22 }
23 }
24 }
25 return 0;
26}
27
28int main() {
29 scanf("%d", &n);
30 int source = 0, destination = 0;
31 for (int i = 0; i < n; i++) {
32 for (int j = 0; j < n; j++) {
33 scanf("%d", &A[i][j]);
34 }
35 }
36 scanf("%d", &source);
37 scanf("%d", &destination);
38
39 printf("Input graph:\n");
40 for (int i = 0; i < n; i++) {
41 for (int j = 0; j < n; j++) {
42 printf("%3d ", A[i][j]);
43 }
44 printf("\n");
45 }
46
47 for (int i = 0; i < n; i++) {
48 d[i] = 999;
49 p[i] = -1;
50 }
51 d[source] = 0;
52 int valid = bellman_ford();
53 if (valid == -1) {
54 printf("Graph contains negative edge\n");
55 return 0;
56 }
57 printf("\nFrom Router %d to Router %d\n", source, destination);
58 // for(int i=0; i<n; i++){
59 // printf("Cost: %2d | Path: ", d[i]);
60 // if(i != source){
61 // int j = i;
62 // while(p[j] != -1){
63 // printf("%d <- ",j);
64 // j = p[j];
65 // }
66 // }
67 // printf("%d\n",source);
68 // }
69 printf("Cost: %2d | Path: ", d[destination]);
70 if(destination != source){
71 int j = destination;
72 while(p[j] != -1){
73 printf("%d <- ",j);
74 j = p[j];
75 }
76 }
77 printf("%d\n",source);
78}