bellmanford.c

 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 
 /* Let INFINITY be an integer value not likely to be
    confused with a real weight, even a negative one. */
 #define INFINITY ((1 << 14)-1)
 
 typedef struct {
     int source;
     int dest;
     int weight;
 } Edge;
 
 void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
 {
     int *distance = malloc(nodecount * sizeof *distance);
     int i, j;
     if (distance == NULL) {
       fprintf(stderr, "malloc() failed\n");
       exit(EXIT_FAILURE);
     }
     for (i=0; i < nodecount; ++i)
       distance[i] = INFINITY;
     distance[source] = 0;
 
     for (i=0; i < nodecount; ++i) {
         for (j=0; j < edgecount; ++j) {
             if (distance[edges[j].source] != INFINITY) {
                 int new_distance = distance[edges[j].source] + edges[j].weight;
                 if (new_distance < distance[edges[j].dest])
                   distance[edges[j].dest] = new_distance;
             }
         }
     }
 
     for (i=0; i < edgecount; ++i) {
         if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
             puts("Negative edge weight cycles detected!");
             free(distance);
             return;
         }
     }
 
     for (i=0; i < nodecount; ++i) {
         printf("The shortest distance between nodes %d and %d is %d\n",
             source, i, distance[i]);
     }
     free(distance);
     return;
 }
 
 int main(void)
 {
     /* This test case should produce the distances 2, 4, 7, -2, and 0. */
     Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
                       {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
                       {4,0, 6}, {4,2, 7}};
     BellmanFord(edges, 10, 5, 4);
     return 0;
 }