Bellman Ford Algorithm

bellmanford.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES   8
#define INFINITE    0xffff

// structure for a node
typedef struct _node {
    int node;
    int cost;
    int updateFrom;
} node;


// structure for a grpah defined by an adjacency matrix
typedef struct _graph {
    int numNodes;
    node nodes[MAX_NODES];
    int adjMatrix[MAX_NODES][MAX_NODES];
} graph;


// function prototypes
void initGraph(graph *g);
void resetGraph(graph *g);
int addNode(graph *g, char *name);
void BellmanFord(graph *g, int s, int t);


// initialize graph
void initGraph(graph *g) {
    int i, j;
    g->numNodes = 0;
    for (i = 0; i < MAX_NODES; i++) {
        g->nodes[i].node = 0;
        g->nodes[i].cost = INFINITE;
        g->nodes[i].updateFrom = 0;

        for (j = 0; j < MAX_NODES; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// reset the colors to white and clear all times
void resetGraph(graph *g) {
    int i;
    for (i = 0; i < g->numNodes; i++) {
        g->nodes[i].node = 0;
        g->nodes[i].cost = INFINITE;
        g->nodes[i].updateFrom = 0;
    }
}


void printPath(graph *g, int s, int t) {
    if (g->nodes[t].updateFrom)
        printPath(g, s, g->nodes[t].updateFrom);

    printf(" %i ", g->nodes[t].node);
}


// add a node to the graph if it does not exist yet and return the index of the node
int addNode(graph *g, char * node) {
    int i;

    for (i = 0; i < g->numNodes; i++) {
        // if we find a node with the name return the index
        if (g->nodes[i].node == atoi(node)) {
            return i;
        }
    }

    g->nodes[atoi(node)-1].node = atoi(node);
    // increase the number of nodes since we added a new node
    g->numNodes++;

    return atoi(node)-1;
}


void BellmanFord(graph *g, int s, int t) {
    int nodeIndex, edgeIndex, addCost;

    g->nodes[s].cost = 0;

    for (int nodeIndex2 = 0; nodeIndex2 < g->numNodes; nodeIndex2++) {
        for (nodeIndex = 0; nodeIndex < g->numNodes; nodeIndex++) {
            for (edgeIndex = 0; edgeIndex < MAX_NODES; edgeIndex++) {
                if ((addCost = g->adjMatrix[nodeIndex][edgeIndex])) {

                    if (g->nodes[nodeIndex].cost + addCost < g->nodes[edgeIndex].cost) {
                        g->nodes[edgeIndex].cost = g->nodes[nodeIndex].cost + addCost;
                        g->nodes[edgeIndex].updateFrom = nodeIndex;
                    }

                }

            }
        }
    }
}


int main() {
    FILE *fp;
    char line[1000];
    char *pos;
    int i ,j= 0;

    // our graph g
    graph g;
    int source;
    int target;

    // initialize the new graph
    initGraph(&g);

    // open the file
    fp = fopen("graph", "r");
    if (fp == NULL) {
        printf("Cannot open Graphfile!!!\n");
        return -1;
    }

    // loop through all lines of the file
    while (!feof(fp)) {
        fgets(line, 1000, fp);

        // extract the first node name
        pos = strtok(line, " \n\r");
        // ignore any empty line
        if (pos == NULL) continue;

        // add the node to the graph
        source = addNode(&g, pos);

        // ignore the colon
        pos = strtok(NULL, " \n\r");

        // read all neighbor nodes including their edge weights on the same line
        while ((pos = strtok(NULL, " \n\r")) != NULL) {
            target = addNode(&g, pos);

            // get the weight of the node
            pos = strtok(NULL, " \n\r");

            // add an edge to the adjacency matrix
            g.adjMatrix[source][target] = atoi(pos);
            printf("[%d] -> [%d] with weight %d\n", g.nodes[source].node, g.nodes[target].node, atoi(pos));
        }
    }

    fclose(fp);

    // print adjacency matrix with weights
    printf("\n");

    for (i = 0; i < MAX_NODES; i++) {
        for (j = 0; j < MAX_NODES; j++) {
            printf("%d",g.adjMatrix[i][j]);
        }
        printf("\n");
    }

    // Find the shortest path between node 1 and 8
    // One-Indexed (!)
    int s = 6;
    int t = 5;

    // Make zero-indexed
    s = s-1;
    t = t-1;

    BellmanFord(&g, s, t);

    for(int x=0; x<=MAX_NODES; x++) {
        printf("Node %i has cost %i\n", g.nodes[x].node, g.nodes[x].cost);
    }

    printPath(&g, s, t);
    printf("\n");
    return 0;
}