Bellman Ford

bmf.cpp

// Author: Harsh Gupta
// Date: 11 November 2013
// Implementation of Bellman Ford Algorithm
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define V 6 // Max Size of The Matrix
const float inf = 99999;

typedef struct edge{
    int to;
    int from;
    float weight;
}edge;

typedef struct graph{
    float adjmat[V][V];
    edge edges[V*V];
    int no_edges;
}graph;

float dist[V];

int is_empty(int A[], int size){
    int i;
    for(i=0;i<size;i++){
        if(A[i] != 0)
            return 0;
    }
    return 1;
}

graph add_edge(graph g, int i, int j, int cost){
    g.adjmat[i][j] = cost;
    g.edges[g.no_edges].to= i;
    g.edges[g.no_edges].from= j;
    g.edges[g.no_edges].weight= cost;
    g.no_edges++;
    return g;
}

/* graph input_graph(graph g){ */
/*     int i,j; */
/*     float val; */
/*     for(i=0; i<V;i++){ */
/*         for(j=0; j<V; j++){ */
/*             scanf("%f", &val); */
/*             if(val <= 0) g.adjmat[i][j] = inf; */
/*             else g.adjmat[i][j] = val; */
/*         } */
/*         g.adjmat[i][i] = inf; */
/*     } */
/*     return g; */
/* } */


int min_dist_in_Q(int A[], int size){
    int i;
    float min=inf;
    int min_pos;
    for(i=0;i<size;i++){
        if(dist[i] < min && A[i] == 1){
            min = dist[i];
            min_pos = i;
        }
    }
    return min_pos;
}

void bellman_ford(const graph g, int source){
    /* int i; */
    int predecessor[V];
    for(int i=0;i<V;i++){
        dist[i] = inf;
        predecessor[i] = -1;
    }
    dist[source] = 0;

    for(int i=0;i<V-1;i++){
        for(int j=0;j<g.no_edges;j++){
            int u, v;
            float w;
            u = g.edges[j].to;
            v = g.edges[j].from;
            w = g.edges[j].weight;
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                predecessor[v] = u;
            }
        }
    }

    for(int j=0;j<g.no_edges;j++){
            int u, v;
            float w;
            u = g.edges[j].to;
            v = g.edges[j].from;
            w = g.edges[j].weight;
            if(dist[u] + w < dist[v]){
                printf("The Graph contains at least one ");
                printf("negative-weight cycle \n");
            }

    }
}
/* void dijkstra(graph g, int x){ */
/*     int i; */
/*     int visited[V]; */
/*     int Q[V]; */
/*     int previous[V]; */
/*     for(i=0;i<V;i++){ */
/*         visited[i] = 0; */
/*         dist[i] = inf; */
/*         Q[i] = 0; */
/*         previous[i] = -1; */
/*     } */
/*  */
/*     dist[x] = 0; */
/*     Q[x] = 1; */
/*     previous[x] = x; */
/*  */
/*     while(is_empty(Q, V) != 1){ */
/*         int u = min_dist_in_Q(Q,V); */
/*         printf("in while loop, u is %d \n",u); */
/*         Q[u] = 0; */
/*         visited[u] = 1; */
/*  */
/*         int v=0; */
/*         for(v=0;v<V;v++){ // for v in ias the vertex of u */
/*             if(g.adjmat[v][u] != inf){ */
/*                 float alt = dist[u] + g.adjmat[u][v]; */
/*                 if(alt < dist[v] && visited[v] != 1){ */
/*                     dist[v] = alt; */
/*                     printf("Distance Updated %d %d %f\n",u,v, alt); */
/*                     previous[v] = u; */
/*                     #<{(| printf("Previous[%d] = %d\n", i, previous[i]); |)}># */
/*                     Q[v] = 1; */
/*                 } */
/*             } */
/*         } */
/*     } */
/*  */
/*     printf("Previous\n"); */
/*     for(i=0;i<V;i++) printf("%d ", previous[i]); */
/*     printf(" Printing Paths\n"); */
/*     for(i=0;i<V;i++){ */
/*         printf("%d to %d:",x, i); */
/*         int j; */
/*         j = previous[i]; */
/*         while(j != x && j != -1){ */
/*             printf("%d ", j); */
/*             j = previous[j]; */
/*         } */
/*         printf("\n"); */
/*     } */
/* } */

graph init_graph(graph g){
    g.no_edges = 0;
    for(int i=0;i<V*V;i++){
        g.edges[i].to = 0;
        g.edges[i].from = 0;
        g.edges[i].weight = inf;
    }
    printf("\n");
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            g.adjmat[i][j] = inf;
        }
    }
    return g;
}

void print_graph(graph g){
    for(int i=0;i<g.no_edges;i++){
        printf("(%d,%d,%.0f) ",g.edges[i].to,g.edges[i].from, g.edges[i].weight);
    }
    printf("\n");
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            printf("%.0f ",g.adjmat[i][j]);
        }
        printf("\n");
    }
}

int main(){
    graph g;
    g = init_graph(g);
    printf("Enter a connected tree of size %d\n", V);
    int u, v;
    float w;
    printf("Enter the edges in from 'to from weight' ");
    printf("Enter 0 0 0 to terminate input \n");
    /* scanf("%d %d %f", &u, &v, &w); */
    scanf("%d",&u);
    scanf("%d",&v);
    scanf("%f",&w);
    while(u !=0 && v != 0){
        g = add_edge(g, u, v, w);
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%f",&w);
    }
    print_graph(g);
    /* g = input_graph(g); */
    /* dijkstra(g, 0); */
    /* bellman_ford(g, 0); */
    /* int i; */
    /* for(i=0;i<V;i++){ */
    /*     printf("%f ", dist[i]); */
    /* } */

    printf("\n");
    return 0;
}