Implementation of Distance Vector Routing Algorithm

Algorithms

Step 1: Read the number of nodes n.

Step 2: Read the distance matrix dm[n][n] which represents the direct cost between each pair of nodes.

Step 3: Initialize routing table for each router:

• Set rt[i].dist[j] = dm[i][j] for all i,j
• Set rt[i].next[j] = j for all i,j
• Set dm[i][i] = 0 (distance to self is zero)

Step 4: Perform Bellman-Ford relaxation for n-1 iterations:

• For iter = 0 to n-2
• For each router i = 0 to n-1
• For each destination j = 0 to n-1
• For each intermediate node k = 0 to n-1
• If rt[i].dist[j] > rt[i].dist[k] + rt[k].dist[j] then
  • Update rt[i].dist[j] = rt[i].dist[k] + rt[k].dist[j]
  • Update rt[i].next[j] = rt[i].next[k]

Step 5: Display the final routing table for each router showing destination node, next hop, and distance.

---

Programs

#include <stdio.h>

#define MAX 20

struct Node {
    int dist[MAX];
    int next[MAX];
} rt[10];

int main() {
    int dm[MAX][MAX], n;
    
    printf("Enter number of nodes: ");
    scanf("%d", &n);
    
    printf("Enter distance matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &dm[i][j]);
            dm[i][i] = 0;
            rt[i].dist[j] = dm[i][j];
            rt[i].next[j] = j;
        }
    }

    // Run Bellman-Ford n-1 iterations
    for (int iter = 0; iter < n - 1; iter++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (rt[i].dist[j] > rt[i].dist[k] + rt[k].dist[j]) {
                        rt[i].dist[j] = rt[i].dist[k] + rt[k].dist[j];
                        rt[i].next[j] = rt[i].next[k];
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        printf("\nRouter %c:\nDest\tNext\tDist\n", 'A' + i);
        for (int j = 0; j < n; j++)
            printf("%c\t%c\t%d\n", 'A' + j, 'A' + rt[i].next[j], rt[i].dist[j]);
    }
    
    return 0;
}