Routing algorithmimplementation.

/* Link State Routing - Dijkstra's shortest path algorithm.
 *
 * Every router floods its own link costs, so every router ends up holding
 * the same Link State Database. This program is what ONE router then runs
 * over that database to build its own shortest-path tree and routing table.
 *
 * Build: gcc dijkstra.c -o dijkstra && ./dijkstra
 */
#include <stdio.h>

#define N   6      /* routers A..F                              */
#define INF 9999   /* "no direct link" / "not reachable yet"     */

/* cost[i][j] = cost of the direct link i-j, INF when there is none.
 * Default lab network:
 *   A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6, E-F 3 */
int cost[N][N] = {
/*          A     B     C     D     E     F   */
/* A */ {   0,    4,    2,  INF,  INF,  INF },
/* B */ {   4,    0,    1,    5,  INF,  INF },
/* C */ {   2,    1,    0,    8,   10,  INF },
/* D */ { INF,    5,    8,    0,    2,    6 },
/* E */ { INF,  INF,   10,    2,    0,    3 },
/* F */ { INF,  INF,  INF,    6,    3,    0 }
};

int dist[N];     /* dist[v]    = cheapest known cost source -> v   */
int parent[N];   /* parent[v]  = predecessor of v on that path      */
int done[N];     /* done[v]    = 1 once dist[v] can never improve   */

void dijkstra(int src)
{
    int i, round, u, v;

    /* 1. Initialise: source at 0, everything else at infinity. */
    for (i = 0; i < N; i++) {
        dist[i]   = INF;
        parent[i] = -1;
        done[i]   = 0;
    }
    dist[src] = 0;

    /* 2. Finalise one router per round, always the cheapest one left. */
    for (round = 0; round < N; round++) {
        int best = INF;
        u = -1;
        for (i = 0; i < N; i++)
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }

        if (u == -1) break;      /* whatever is left is unreachable */
        done[u] = 1;

        /* 3. Relax every link out of u that leads somewhere unfinished. */
        for (v = 0; v < N; v++) {
            if (done[v] || cost[u][v] >= INF) continue;
            if (dist[u] + cost[u][v] < dist[v]) {
                dist[v]   = dist[u] + cost[u][v];
                parent[v] = u;
            }
        }
    }
}

/* A router stores only ONE hop, not the whole path. The next hop is the
 * first router after the source, so walk parent[] back towards src. */
int next_hop(int src, int dest)
{
    int hop = dest;
    if (dest == src || parent[dest] == -1) return -1;
    while (parent[hop] != src) hop = parent[hop];
    return hop;
}

int main(void)
{
    int src = 0;    /* 0 = router A */
    int v;

    dijkstra(src);

    printf("Routing table for router %c (Link State / Dijkstra)\n", 'A' + src);
    printf("%-12s %-10s %s\n", "Destination", "Next Hop", "Cost");
    for (v = 0; v < N; v++) {
        int hop;
        if (v == src) continue;
        hop = next_hop(src, v);
        if (hop == -1)
            printf("%-12c %-10s %s\n", 'A' + v, "-", "INF");
        else
            printf("%-12c %-10c %d\n", 'A' + v, 'A' + hop, dist[v]);
    }
    return 0;
}

/* Expected output:
 *   B  C  3      D  C  8
 *   C  C  2      E  C  10
 *                F  C  13                                        */

/* Distance Vector Routing - distributed Bellman-Ford.
 *
 * Each router keeps one distance vector and periodically hands it to its
 * DIRECT NEIGHBOURS ONLY. On receiving a neighbour's vector it applies
 *
 *     D(x, y) = min over neighbours v of { c(x, v) + D(v, y) }
 *
 * Build: gcc distance_vector.c -o dv && ./dv
 */
#include <stdio.h>

#define N   6    /* routers A..F                                      */
#define INF 16   /* RIP-style infinity: 16 hops means "unreachable"    */

/* Direct link costs. INF means the two routers are not neighbours.
 * Default lab network:
 *   A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6, E-F 3 */
int cost[N][N] = {
/*          A     B     C     D     E     F   */
/* A */ {   0,    4,    2,  INF,  INF,  INF },
/* B */ {   4,    0,    1,    5,  INF,  INF },
/* C */ {   2,    1,    0,    8,   10,  INF },
/* D */ { INF,    5,    8,    0,    2,    6 },
/* E */ { INF,  INF,   10,    2,    0,    3 },
/* F */ { INF,  INF,  INF,    6,    3,    0 }
};

int dv[N][N];       /* dv[x][y]      = D(x, y), x's cost to reach y   */
int nexthop[N][N];  /* nexthop[x][y] = neighbour x forwards y through */

/* Every router starts knowing only itself and its direct neighbours. */
void initialise(void)
{
    int x, y;
    for (x = 0; x < N; x++) {
        for (y = 0; y < N; y++) {
            if (x == y) {
                dv[x][y] = 0;    nexthop[x][y] = x;
            } else if (cost[x][y] < INF) {
                dv[x][y] = cost[x][y];  nexthop[x][y] = y;
            } else {
                dv[x][y] = INF;  nexthop[x][y] = -1;
            }
        }
    }
}

/* One synchronous exchange round. Returns 1 if any entry changed.
 * Every router advertises first, so all of them recompute from the same
 * snapshot - that is what "one round" means. */
int exchange_round(void)
{
    int advertised[N][N];
    int x, y, v, changed = 0;

    for (x = 0; x < N; x++)
        for (y = 0; y < N; y++)
            advertised[x][y] = dv[x][y];

    for (x = 0; x < N; x++) {
        for (y = 0; y < N; y++) {
            int best, best_hop;
            if (x == y) continue;

            best = INF;
            best_hop = -1;
            for (v = 0; v < N; v++) {                 /* v = each neighbour */
                int alt;
                if (v == x || cost[x][v] >= INF) continue;
                alt = cost[x][v] + advertised[v][y];  /* Bellman-Ford       */
                if (alt > INF) alt = INF;             /* clamp at infinity  */
                if (alt < best) { best = alt; best_hop = v; }
            }

            if (best != dv[x][y] || best_hop != nexthop[x][y]) changed = 1;
            dv[x][y]      = best;
            nexthop[x][y] = (best >= INF) ? -1 : best_hop;
        }
    }
    return changed;
}

void print_table(int x)
{
    int y;
    printf("\nRouting table for router %c (Distance Vector)\n", 'A' + x);
    printf("%-12s %-10s %s\n", "Destination", "Next Hop", "Cost");
    for (y = 0; y < N; y++) {
        if (y == x) continue;
        if (dv[x][y] >= INF) printf("%-12c %-10s %s\n", 'A' + y, "-", "INF");
        else printf("%-12c %-10c %d\n", 'A' + y, 'A' + nexthop[x][y], dv[x][y]);
    }
}

int main(void)
{
    int round = 0;

    initialise();
    while (exchange_round()) {         /* repeat until nothing changes */
        round++;
        printf("Round %d: vectors exchanged, tables updated.\n", round);
        if (round > 100) break;        /* safety net */
    }
    printf("Converged after %d round(s).\n", round);

    print_table(0);                    /* router A */
    return 0;
}

/* Expected table for A:  B C 3 | C C 2 | D C 8 | E C 10 | F C 13 */