Description: Implement the Bellman Ford Algorithm

Algorithm:

Relax step

Relax( u,v,w )

If v.d> u.d +w(u,v)

       v.d = u.d + w(u,v)

       v.p = u

 

Step 1: Initialize distances from source to all other vertices as INFINITE but source to source as 0

Step 2: Relax all edges |V| - 1 times. A simple shortest path from source to any other vertex can have at-most |V| - 1 edges

Step 3: Check for negative-weight cycles.  The above step guaranteesshortest distances if graph doesn't contain negative weight cycle.If we get a shorter path, then there is a cycle.

    

C Implementation:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
 
/* a structure to represent a weighted edge in graph */
struct Edge
{
    int src, dest, weight;
};
 
/* a structure to represent a connected, directed and weighted graph */
struct Gr
{
    /* V-> Number of vertices, E-> Number of edges */
    int V, E;
    /* graph is represented as an array of edges. */
    struct Edge* edge;
};
 
/* The following function implements Bellman Ford*/
void BFord(struct Gr* graph, intsrc)
{
    int V = graph->V;
    int E = graph->E;
    int d[V];
    /*Initialize distances from src to all other vertices as INFINITE */
    for(inti = 0; i < V; i++)
        d[i]   = INT_MAX;
    d[src] = 0;
 
    /*Step 2: Relax all edges |V| - 1 times */
    for(int i = 1; i <= V-1; i++)
    {
        for(int j = 0; j < E; j++)
        {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if(d[u] + weight < d[v])
                d[v] = d[u] + weight;
        }
    }
 
    /* check for negative-weight cycles */
    for(inti = 0; i < E; i++)
    {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if(d[u] + weight < d[v])
            printf("Negative weight cycle fund");
    }
return;
}
Go to top