/******************************************************************************\
*                                                                              *
*   Assignment 2 - Implementation of Bellman-Ford Algorithm                    *
*                                                                              *
*   flamingspinach                                                             *
*                                                                              *
*   Started:  2006-10-22                                                       *
*   Finished: 2006-10-22                                                       *
*                                                                              *
\******************************************************************************/

#include <iostream>
#include <string>
#include <list>
#include <iterator>
#include <vector>
#include "Network.h"
using namespace std;

list<int> getPath (Network& N, int start, int end) {
    int v, w, newDistance, n = N.NumberVertices();
    bool improvement = true;
    list<int> path;
    for (v = 1; v <= n; ++v) N.SetDistance(v, INT_MAX);
    N.SetDistance(start,0);
    N.SetPredecessor(start,0);
    
    while(improvement) {
        improvement = false;
        for (v = 1; v <= n; ++v) {
            if (N.Distance(v) == INT_MAX) continue;
            for (int c = 0; c < N.Degree(v); ++c) {
                w = N.Neighbor(v, c);
                newDistance = N.Distance(v) + N.Length(v, c);
                if (newDistance < N.Distance(w)) {
                    N.SetDistance(w, newDistance);
                    N.SetPredecessor(w, v);
                    improvement = true;
                }
            }
        }
    }
    
    v = end;
    while (v != 0) {
        path.push_front(v);
        v = N.Predecessor(v);
    }
    
    return path;
}

int main()
{
    vector<string> files(6);
    files[0]="test1.edge";
    files[1]="test2.edge";
    files[2]="test3.edge";
    files[3]="test4.edge";
    files[4]="test5.edge";
    files[5]="test6.edge";
    
    for(int i = 0; i < 6; ++i) {
        Network N (files[i].c_str());
        list<int> path;
        int n = N.NumberVertices();
       
        cout << "The shortest path for " << files[i] << " from the first to the "
             << "last vertex is:" << endl << "     ";       
        path = getPath(N, 1, n);
        for (list<int>::iterator I = path.begin(); I != path.end(); ++I)
            cout << *I << " ";
        cout << endl << "     Minimum distance required: " << N.Distance(n) << endl << endl;
    }
    
    system("pause");
    return 0;
}