//--------------------------------------------------

//CPPfile: Dijkstra.cpp

//Beschreibung: Dijkstra Algorithmus

//Autor: Tobias Schwalb & Michael Tansella, ITIV

//Erstellt: 13.07.2011

//Version: 1.0

//--------------------------------------------------



#include <iostream>

#include <iomanip>

#include <stdlib.h>



using namespace std;



// Unendlich "definieren"

// größt möglicher Wert von int

const int INF = 2147483647;



// Anzahl an Knoten muss "hart" festgelegt werden

const unsigned short NODENUM = 9;



class Dijkstra {



public:

    void setMatrix( unsigned int matrix[NODENUM][NODENUM] );

    void setSource( unsigned int source );

    void calculate( bool step );

    void trace();



private:

    unsigned int matrix[NODENUM][NODENUM];

    unsigned int source;

    unsigned int distance[NODENUM];           // Array für Entfernungen/Kosten

    unsigned int predecessor[NODENUM];        // Array für Vorgängerknoten



};





void Dijkstra::setSource( unsigned int source ) {

    this->source = source;

}





void Dijkstra::setMatrix( unsigned int matrix[NODENUM][NODENUM] ) {

    for( int i = 0; i < NODENUM; i++ ) {

        for( int j = 0; j < NODENUM; j++ ) {

            this->matrix[i][j] = matrix[i][j];

        }

    }

}





void Dijkstra::calculate( bool step = false ) {



    // Array für markierte Knoten

    bool marked[NODENUM];



    // Initialisierung

    for( int x = 0; x < NODENUM; ++x ) {



        // Kein Knoten ist markiert

        marked[x] = false;



        // Kosten sind zunächst unendlich

        this->distance[x] = INF;



        // Vorgänger sind nicht vorhanden

        this->predecessor[x] = 0;

    }



    // Startknoten besitzt Kosten 0

    this->distance[this->source] = 0;



    bool flag = true;



    while( flag ) {



        // minimale Kosten initialisieren

        unsigned int minimum = INF;



        // zugehöriger (minimaler) Knoten

        int node = 0;



        // Minimale Distanz ermitteln

        for( int j = 0; j < NODENUM; ++j ) {

            // Knoten schon markiert -> überspringen (Zyklen vermeiden!)

            if( marked[j] ) continue;



            // Distance kleiner als Minimum -> neues Minimum gefunden

            if( this->distance[j] < minimum ) {

                minimum = this->distance[j];

                node = j;

            }

        }



        // Distanz aktualisieren, wenn Zielknoten über den gefundenen Minimumknoten billiger erreichbar

        for( int j = 0; j < NODENUM; ++j ) {



            if( !marked[j] && this->matrix[node][j] != 0 && this->distance[node] + this->matrix[node][j] < this->distance[j] ) {

                this->distance[j] = this->distance[node] + this->matrix[node][j];

                this->predecessor[j] = node;

            }



            // jeden einzelnen Verbesserungsschritt ausgeben

            if( step == true ) {

                if( this->distance[j] == INF ) {

                    cout << "INF\t";

                }

                else {

                    cout << setw(3) << this->distance[j] << "\t";

                }

            }

        }



        if( step == true ) {

            cout << "\n\n";

        }



        // gerade bestimmten Minimumknoten markieren

        marked[node] = true;



        // sind noch Knoten unmarkiert?

        flag = false;

        for( int j = 0; j < NODENUM && !flag; ++j ) {

            flag = !marked[j];

        }

    }

}





// Methode, die den günstigsten Weg vom angegebenen Startknoten zu den anderen Knoten aufzeigt

void Dijkstra::trace() {



    for( int x = 0; x < NODENUM; ++x ) {

        // Wenn kein Vorgänger vorhanden und Knoten != Startknoten existiert keine Verbindung

        if( this->predecessor[x] == 0 && x != this->source ) {

            cout <<"Keine Verbindung zwischen " << this->source << " und " << x << " gefunden\n\n";

            continue;

        }



        cout << "G\x81nstigste Verbindung von " << source << " nach " << x << endl;



        int j = x;



        // Vorgänger verfolgen bis zum Ziel ("Rückwärtssuche")

        while( this->predecessor[j] != 0 ) {

            cout << j << " <- ";

            j = this->predecessor[j];

        }



        cout << j << "\n\nKosten:" << setw(3) << this->distance[x] << "\n\n";

 }

}



// Beispielaufruf

int main() {



    unsigned int test[NODENUM][NODENUM] = {

        {   0,  15, INF, INF, INF, INF, INF, INF, INF },

        {  15,   0, INF,  30,  10, INF,  25,  10,  30 },

        { INF, INF,   0,  20, INF, INF,  15, INF, INF },

        { INF,  30,  20,   0, INF, INF, INF, INF, INF },

        { INF,  10, INF, INF,   0,  40,  10, INF, INF },

        { INF, INF, INF, INF,  40,   0,  20, INF, INF },

        { INF,  25,  15, INF,  10,  20,   0, INF, INF },

        { INF,  10, INF, INF, INF, INF, INF,   0,  10 },

        { INF,  30, INF, INF, INF, INF, INF,  10,   0 }

    };



    Dijkstra *myDijkstra = new Dijkstra();



    // Matrix setzen

    myDijkstra->setMatrix( test );



    // Startknoten setzen

    myDijkstra->setSource( 8 );



    // Algorithmus ausführen

    myDijkstra->calculate( true );



    // Günstigste Wege aufzeigen

    myDijkstra->trace();



    system( "Pause" );



    return 0;

}