Tag Archives: Shortest Paths

Bellman-Ford algorithm in C

Weighted graph showing all distances from vertex 0

The Bellman-Ford algorithm finds the shortest path between a single vertex and all other vertices in a graph. This is the same problem that Dijkstra’s algorithm solves, but unlike Dijkstra, the Bellman-Ford algorithm can handle graphs with negative edge weights.

One consequence of negative weights is that a graph can contain a negative cycle, and if this is the case, the shortest path to all vertices reachable from the cycle is negative infinity, because one could traverse the cycle any number of times and keep reducing the path length indefinitely. The Bellman Ford algorithm detects this by performing an extra iteration over the graph, and if this would result in a distance decreasing, it knows that there is a negative cycle.

Below is an implementation in C. It takes a set of weighted arcs, the number of arcs (size), the number of vertices (order), and a starting vertex number. It returns an array of integers containing the distance to every vertex. If the graph contains a negative cycle, it returns NULL.

#include <stdlib.h>
#include <limits.h>

typedef struct {
    unsigned int first;
    unsigned int second;
    int weight;
} weighted_arc;

int *bellman_ford(const weighted_arc *arcs, unsigned int size, unsigned int order, 
        unsigned int vertex)
{
    unsigned int i;
    int *distances = malloc(order * sizeof(unsigned int));
    unsigned int a, v, negative_cycle = 0;
    if (distances == NULL) {
        return NULL;
    }
    /* All distances start infinite */
    for (i = 0; i < order; i++) {
        distances[i] = INT_MAX;
    }
    /* Distance to starting vertex is 0 */
    distances[vertex] = 0;
    /* Relax edges repeatedly */
    for (v = 0; v < order; v++) {
        for (a = 0; a < size; a++) {
            const unsigned int first = arcs[a].first;
            const unsigned int second = arcs[a].second;
            const int weight = arcs[a].weight;
            if (distances[first] != INT_MAX
                && distances[first] + weight < distances[second])
            {
                distances[second] = distances[first] + weight;
            } 
        }
    }
    /* Check for negative weight cycle */
    for (a = 0; a < size && !negative_cycle; a++) {
        const unsigned int first = arcs[a].first;
        const unsigned int second = arcs[a].second;
        const int weight = arcs[a].weight;
        negative_cycle = distances[first] + weight < distances[second];
    }
    if (negative_cycle) {
        free(distances);
        distances = NULL;
    }

    return distances;
}

Here is an example program that computes the distances for the graph shown at the top:

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

/* Connect two arcs */
void weighted_arc_connect(weighted_arc *arcs, unsigned int first, unsigned int second, 
        int weight, unsigned int *pos)
{
    arcs[*pos].first = first;
    arcs[*pos].second = second;
    arcs[*pos].weight = weight;
    (*pos)++;
}

int main(void)
{
    unsigned int size = 9; /* Arcs */
    unsigned int order = 6; /* Vertices */
    unsigned int i = 0;
    int *distances;

    weighted_arc *arcs = malloc(size * sizeof(weighted_arc));
    weighted_arc_connect(arcs, 0, 1, 5, &i);
    weighted_arc_connect(arcs, 0, 3, -2, &i);
    weighted_arc_connect(arcs, 1, 2, 1, &i);
    weighted_arc_connect(arcs, 2, 3, 2, &i);
    weighted_arc_connect(arcs, 2, 4, 7, &i);
    weighted_arc_connect(arcs, 2, 5, 3, &i);
    weighted_arc_connect(arcs, 3, 1, 2, &i);
    weighted_arc_connect(arcs, 4, 3, 3, &i);
    weighted_arc_connect(arcs, 4, 5, 10, &i);

    distances = bellman_ford(arcs, size, order, 0);
    if (distances == NULL) {
        printf("Graph contains a negative cycle or ran out of memory.\n");
        return 1;
    }

    for (i = 0; i < order; i++) {
        printf("%u: %d\n", i, distances[i]);
    }

    free(arcs);
    free(distances);
    return 0;
}

The output:

0: 0
1: 0
2: 1
3: -2
4: 8
5: 4

Related

Floyd-Warshall algorithm in C

A weighted directed graph

The Floyd-Warshall algorithm calculates the distances between all pairs of vertices in a weighted graph. It is a dynamic programming algorithm very similar to Gauss-Jordan elimination.

Below is an implementation in C. The function takes an array of directed arcs, the size of the graph (number of arcs), and its order (number of vertices). It returns a dynamically allocated 2-dimensional array that is the distance table for all pairs of vertices.

One thing to notice about the implementation is that when you use INT_MAX to represent infinity, you need to be very careful not to do arithmetic on it that will cause it to roll over and become a small number. This is the reason for the checks for INT_MAX in the main calculation.

#include <stdlib.h>
#include <limits.h>

typedef struct {
    unsigned int first;
    unsigned int second;
    int weight;
} weighted_arc;

int **floyd_warshall(const weighted_arc *arcs, unsigned int size, unsigned int order)
{
    unsigned int i, j, k;
    int **distances = malloc(order * sizeof(int *));
    /* Initialise the distance table */
    for (i = 0; i < order; i++) {
        distances[i] = malloc(order * sizeof(int));
        for (j = 0; j < order; j++) {
            if (i == j) {
                distances[i][j] = 0;
            }
            else {
                distances[i][j] = INT_MAX;
            }
        }
    }
    /* Add the distance for each arc */
    for (i = 0; i < size; i++) {
        distances[arcs[i].first][arcs[i].second] = arcs[i].weight;
    }
    /* Calculate the rest of the distances */
    for (i = 0; i < order; i++) {
        for (j = 0; j < order; j++) {
            for (k = 0; k < order; k++) {
                const int djk = distances[j][k];
                const int dji = distances[j][i];
                const int dik = distances[i][k];
                if (dji != INT_MAX && dik != INT_MAX 
                        && djk > dji + dik)
                {
                    distances[j][k] = dji + dik;
                }
            }
        }
    }
    return distances;
}

Here is an example program that calculates the distance table for the graph shown at the top of the page:

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

/* Connect two arcs */
void weighted_arc_connect(weighted_arc *arcs, unsigned int first, unsigned int second, 
        int weight, unsigned int *pos)
{
    arcs[*pos].first = first;
    arcs[*pos].second = second;
    arcs[*pos].weight = weight;
    (*pos)++;
}

/* Print a distance table */
void print_distances(int **distances, unsigned int order)
{
    unsigned int i, j;
    for (i = 0; i < order; i++) {
        for (j = 0; j < order; j++) {
            printf("%d ", distances[i][j]);
        }
        putchar('\n');
    }
}

int main(void)
{
    unsigned int size = 5; /* Arcs */
    unsigned int order = 4; /* Vertices */
    unsigned int i = 0;
    int **distances;
    weighted_arc *arcs = malloc(size * sizeof(weighted_arc));
    weighted_arc_connect(arcs, 0, 2, -2, &i);
    weighted_arc_connect(arcs, 1, 0, 4, &i);
    weighted_arc_connect(arcs, 1, 2, 3, &i);
    weighted_arc_connect(arcs, 2, 3, 2, &i);
    weighted_arc_connect(arcs, 3, 1, -1, &i);
    distances = floyd_warshall(arcs, size, order);
    print_distances(distances, order);
    free(arcs);
    for (i = 0; i < order; i++) {
        free(distances[i]);
    }
    free(distances);
    return 0;
}

The output:

0 -1 -2 0
4 0 2 4
5 1 0 2
3 -1 1 0

Related