gistfile1.cpp

/**
 * bellman-ford.cpp
 *
 *  Created on: Nov 29, 2010
 *      Author: blabos
 */
#include <iostream>


using namespace std;


const int inf_dist      = 2147483647;
const int nil_parent    = -1;
const int ord           = 5;

typedef int adj_mat_t[ord][ord];


void print_vector(int* v, int len) {
    for (int i = 0; i < len; i++) {
        cout.flags(ios::right);
        cout.width(9);
        cout  << v[i];
    }
    cout << endl;
}


void print_matrix(adj_mat_t m) {
    cout << "matriz de adjacencia:" << endl;
    
    for (int i = 0; i < ord; i++) {
        for (int j = 0; j < ord; j++) {
            cout.flags(ios::right);
            cout.width(9);
            cout << m[i][j];
        }
        cout << endl;
    }
    cout << endl;
}


void init_graph(adj_mat_t graph) {
    for (int i = 0; i < ord; i++) {
        for (int j = 0; j < ord; j++) {
            graph[i][j] = 0;
        }
    }
    
    graph[0][1] = 10;
    graph[0][3] = 2;
    graph[0][4] = 9;
    
    graph[1][2] = 5;
    
    graph[2][4] = -4;
    
    graph[3][2] = -3;
    graph[3][4] = -8;
}


bool bellman_ford(adj_mat_t graph, int start, int* dist, int* path) {
    for (int i = 0; i < ord; i++) {
        dist[i] = inf_dist;
        path[i] = nil_parent;
    }
    
    dist[start] = 0;
    
    for (int u = 0; u < ord; u++) {
        for (int v = 0; v < ord; v++) {
            if (graph[u][v] == 0) continue;
            
            int step = dist[u] + graph[u][v];
            if (dist[v] > step) {
                dist[v] = step;
                path[v] = u;
            }
        }
    }
    
    for (int u = 0; u < ord; u++) {
        for (int v = 0; v < ord; v++) {
            if (graph[u][v] == 0) continue;
            
            int step = dist[u] + graph[u][v];
            if (dist[v] > step) {
                return false;
            }
        }
    }
    
    return true;
}


int main(int argc, char** argv) {
    adj_mat_t graph;
    int dist[ord];
    int path[ord];
    
    init_graph(graph);
    print_matrix(graph);
    
    cout << "bellman:   " << bellman_ford(graph, 0, dist, path) << endl;
    
    cout << "distances: ";
    print_vector(dist, ord);
    
    cout << "paths:     ";
    print_vector(path, ord);
    
    return 0;
}