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 @@
+#include <stdio.h>
+
+int A[10][10], n, d[10], p[10];
+
+int bellman_ford() {
+    int i, u, v;
+    for (int i = 0; i < n; i++) {
+        for (u = 0; u < n; u++) {
+            for (v = 0; v < n; v++) {
+                if (d[v] > d[u] + A[u][v]) {
+                    d[v] = d[u] + A[u][v];
+                    p[v] = u;
+                }
+            }
+        }
+    }
+    for (u = 0; u < n; u++) {
+        for (v = 0; v < n; v++) {
+            if (d[v] > d[u] + A[u][v]) {
+                printf("Detected negative edge\n");
+                return -1;
+            }
+        }
+    }
+    return 0;
+}
+
+int main() {
+    scanf("%d", &n);
+    int source = 0, destination = 0;
+    for (int i = 0; i < n; i++) {
+        for (int j = 0; j < n; j++) {
+            scanf("%d", &A[i][j]);
+        }
+    }
+    scanf("%d", &source);
+    scanf("%d", &destination);
+
+    printf("Input graph:\n");
+    for (int i = 0; i < n; i++) {
+        for (int j = 0; j < n; j++) {
+            printf("%3d ", A[i][j]);
+        }
+        printf("\n");
+    }
+
+    for (int i = 0; i < n; i++) {
+        d[i] = 999;
+        p[i] = -1;
+    }
+    d[source] = 0;
+    int valid = bellman_ford();
+    if (valid == -1) {
+        printf("Graph contains negative edge\n");
+        return 0;
+    }
+    printf("\nFrom Router %d to Router %d\n", source, destination);
+    // for(int i=0; i<n; i++){
+    //     printf("Cost: %2d | Path: ", d[i]);
+    //     if(i != source){
+    //         int j = i;
+    //         while(p[j] != -1){
+    //             printf("%d <- ",j);
+    //             j = p[j];
+    //         }
+    //     }
+    //     printf("%d\n",source);
+    // }
+    printf("Cost: %2d | Path: ", d[destination]);
+    if(destination != source){
+        int j = destination;
+        while(p[j] != -1){
+            printf("%d <- ",j);
+            j = p[j];
+        }
+    }
+    printf("%d\n",source);
+}