[ Prev ] [ Index ] [ Next ]

Bellman-Ford

Created Donnerstag 28 April 2016

Solve the following problem with Bellman-Ford algorithm!
Find the shortest path from node-0 to node-6!

/*
 ============================================================================
 Name        : bellman-ford.c
 Author      : Auralius Manurung
 Version     :
 Copyright   : --
 Description : in C, Ansi-style
 ============================================================================
 */

#include 
#include 
#include 
#include 

#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))


int nNodes = 8;
int startNode = 0;
double **dist;

int dbl_array_eq(double const *x, double const *y, size_t n, double eps)
{
    int i = 0;
    for (i = 0; i < n; i++)
        if (fabs(x[i] - y[i]) > eps)
            return 0;
    return 1;
}

int main(void)
{
    int i = 0;
    int j = 0;
    int converged = 0;

    dist = calloc(nNodes, sizeof(double*));
    for (i = 0; i < nNodes; i++)
        dist[i] = calloc(nNodes, sizeof(double));

    /* Build the dist matrix*/
    for (i = 0; i < nNodes; i++)
    {
        for (j = 0; j < nNodes; j++)
        {
            if (i == j)
                dist[i][j] = 0.0;
            else
                dist[i][j] = INFINITY;
        }
    };

    /* Example */
    dist[0][1] = 5;
    dist[0][7] = 8;
    dist[0][4] = 9;

    dist[1][3] = 15;
    dist[1][2] = 12;
    dist[1][7] = 4;

    dist[4][7] = 5;
    dist[4][5] = 4;
    dist[4][6] = 20;

    dist[7][2] = 7;
    dist[7][5] = 6;

    dist[5][2] = 1;
    dist[5][6] = 13;

    dist[2][3] = 3;
    dist[2][6] = 11;

    dist[3][6] = 9;

    /* Memory allocation */
    double *distTo = calloc(nNodes, sizeof(double));
    double *distToOld = calloc(nNodes, sizeof(double));
    int *edgeTo = calloc(nNodes, sizeof(int));
    for (i = 0; i < nNodes; i++) {
        distTo[i] = dist[startNode][i];
        edgeTo[i] = startNode;
    }

    /* Bellman-Ford ierations */
    while (converged == 0)
    {
        memcpy(distToOld, distTo, sizeof(double)*nNodes);
        for (i = 0; i < nNodes; i++)
        {
            for (j = 0; j < nNodes; j++)
            {
                double tmp = dist[i][j] + distTo[i];
                if (tmp < distTo[j]) {
                    distTo[j] = tmp;
                    edgeTo[j] = i;
                }
            }
        }
        converged = dbl_array_eq(distToOld, distTo, nNodes, 1e-9);
    }

    /* Print out the results: */
    printf("v\tdistTo[]\tedgeTo[]:\n");
    printf("------------------------------\n");

    for (i = 0; i < nNodes; i++)
        printf("%i\t%.1f\t\t%i-->%i\n", i, distTo[i], i, edgeTo[i],i);

    /* Cleaning up */
    free(distTo);
    free(distToOld);
    free(edgeTo);
    for (i = 0; i < nNodes; i++)
        free(dist[i]);
    free(dist);

    return EXIT_SUCCESS;
}

References


http://algs4.cs.princeton.edu/lectures/44DemoBellmanFord.pdf
./44DemoBellmanFord.pdf