//============================================================================
// Name        : Floyd_Warshallov_algoritem.cpp
// Author      : Jasmin Dervisevic
// Version     :
// Copyright   : Jasmin Dervisevic all rights reserved
// Description : Vaja 5, Floyd_Warhallov_algoritem
//============================================================================

#include <iostream>
#include <time.h>
#include <fstream>
#include <stdlib.h>
#include <chrono>
using namespace std;

int vel;


void BERI(int C[100][100], string f) {
    fstream dat(f.c_str(), fstream::in);
    if (dat.is_open()) {
        dat >> vel;
          int i=0;
          int p, q, cena;
          while(!dat.eof())
          {
            dat >> p >> q >> cena;
            C[p-1][q-1] = cena;
            i++;
          }

        dat.close();

    }else {
        cout<<"Napaka pri odpiranju datoteke!"<<endl;
    }
}
void Floyd(int C[100][100]) {
    int n;
    n = vel + 1;
    int P[vel][vel];
    int D[vel][vel];
    for(int i = 0; i < n-1; i++) {
        for(int j = 0; j < n - 1; j++) {
            D[i][j] = C[i][j];
            if (i != j && C[i][j] != 10000 /*INFINITY???*/) {
                P[i][j] = i;

            }else {
                P[i][j] = -10000; //NIL??;
            }
        }

    }
    for(int k = 0; k < n - 1; k++) {
        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j < n - 1; j++) {
                if(D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    P[i][j] = P[k][j];
                }
            }
        }
    }

    //return D, P;

}

void Izpis_Poti (int P[][vel], int s, int g) {
    if (s == g) {
        cout<<"Zacetno vozlisce: " << s << endl;

    }else {
        if(P[s][g] < 0 /*NIL*/) {
            cout<< "Med "<< s << " in " << g << " ni poti."<<endl;

        }else {
            Izpis_Poti(P, s, P[s][g]);
            cout<< "Koncno vozlisce: "<< g <<endl;
        }
    }
}
int main() {
    int p[vel][vel];
    int n;
    int koncno_vozlisce, ciljno_vozlisce;
    while (n!=4) {
        cout<<"Floyd - Warshallov algoritem - izbira: "<<endl;
        cout<< "1. Preberi graf iz datoteke"<<endl;
        cout<< "2. Zagon algoritma"<<endl;
        cout<< "3. Izpis najkrajse poti med vozliscema s in g"<<endl;
        cout<< "4. Konec"<<endl;
        cout<<"Prosim, vnesi stevilko pred menijem: ";
                cin>> n;

        switch(n) {
        case 1: {
            BERI(p, "Testni_graf.txt");
            cout<<"-------------------------------------"<<endl;
            break;
        }
        case 2: {
            Floyd(p);
            break;
        }
        case 3: {
            //nekaj pac;
            cout<<"Vnesi koncno vozlisce: ";
            cin>>koncno_vozlisce;
            cout<<"Vnesi ciljno vozlisce: ";
            cin>>ciljno_vozlisce;
            Izpis_Poti(p, koncno_vozlisce, ciljno_vozlisce);
            break;
        }
        case 4: {
            exit(0);
            break;
        }
            default:
                cout<<"Napacen vnos, poskusi znova!"<<endl;

            }

        }
    return 0;
}