#include <iostream>
    #include <fstream>
     
    using namespace std;
     
    typedef struct arc
    {
        int depart;
        int arrive;
        int valeur;
    } arc;
    typedef struct chemin
    {
        int pi;
        int pred;
    } chemin;
     
    chemin* dijkstra (int nbSommets, int nbArcs, arc* graphe_arcs, int depart)
    {
            bool* CC = new bool[nbSommets];
            chemin *longueur = new chemin[nbSommets];
            longueur[depart].pi = 0;
            longueur[depart].pred = 0;
            int actuel = 0;
     
            // Initialisation des structures de données
            for (int i = 0; i < nbSommets; ++i)
            {
                    if(i != depart)
                    {
                            longueur[i].pi = -1;
                            longueur[i].pred = -1;
                            CC[i] = false;
                    }
                    else CC[i] = true;
            }
     
            // Algorithme de Dijkstra
            for (int j = 0; j < nbSommets; ++j)
            {
                    // Rafraichissement des chemins les plus courts
                    for (int i = 0; i < nbArcs; ++i)
                    {
                            if (graphe_arcs[i].depart == actuel)
                            {
                                    int tmp = longueur[actuel].pi + graphe_arcs[i].valeur;
                                    if (tmp < longueur[graphe_arcs[i].arrive].pi || longueur[graphe_arcs[i].arrive].pi == -1)
                                    {
                                            longueur[graphe_arcs[i].arrive].pi = tmp;
                                            longueur[graphe_arcs[i].arrive].pred = actuel;
                                    }
                            }
                    }
     
                    // On choisit le prochain sommet à tester
                    int min = -1;
                    for (int i = 0; i < nbSommets; ++i)
                    {
                            if (longueur[i].pi != -1 && CC[i] == false)
                            {
                                    if(min == -1)
                                    {
                                            min = longueur[i].pi;
                                            actuel = i;
                                    }
                                    else
                                    {
                                            if(min > longueur[i].pi)
                                            {
                                                    min = longueur[i].pi;
                                                    actuel = i;
                                            }
                                    }
                            }
                    }
     
                    CC[actuel] = true;
                    min = -1;
            }
     
            for (int i = 0; i < nbSommets; ++i)
                    cout << "Chemin plus court : " << i << " = " << longueur[i].pi << endl;
     
            return longueur;
    }
     
    int main (int argc, char *argv[])
    {
        bool** matAdj;
        int** valAdj;
        arc* graphe_arcs;
        chemin* path;
        int nbSommets;
        int nbArcs;
        int sommetDepart;
        int extremiteInitiale;
        int extremiteTerminale;
        int valeurArc;
        ifstream sourceGraphe(argv[1]);
     
        // Le nom du fichier doit être passé comme premier argument
        if (!argv[1])
        {
            cout << "Usage: " << argv[0] << " FILE" << endl;
            return 0;
        }
       
        // ==== Initialisations ===================================================
     
        // Lecture nombre de sommets et nombre d’arcs
        sourceGraphe >> nbSommets;
        cout << "Nombre de sommets : " << nbSommets << "\n";
        sourceGraphe >> nbArcs;
        cout << "Nombre d'arcs : " << nbArcs << "\n";
        sourceGraphe >> sommetDepart;
        cout << "Sommet de depart : " << sommetDepart << "\n";
     
        // Définition des matrices d'adjacence et de valeur
        matAdj = new bool*[nbSommets];
        valAdj = new int*[nbSommets];
        graphe_arcs = new arc[nbArcs];
        for(int i = 0; i < nbSommets; ++i)
        {
            matAdj[i] = new bool[nbSommets];
            valAdj[i] = new int[nbSommets];
     
            for (int j = 0; j < nbSommets; ++j)
            {
                matAdj[i][j] = false;
                valAdj[i][j] = 0;
            }
        }
     
        // Lecture des arcs du graphe
        cout << "Arcs du graphe:\n";
        sourceGraphe >> extremiteInitiale;
        int k = 0;
        while (extremiteInitiale != -1)
        {
            sourceGraphe >> extremiteTerminale;
            sourceGraphe >> valeurArc;
            cout << extremiteInitiale << " -> " << extremiteTerminale << " = " << valeurArc << "\n";
            graphe_arcs[k].depart = extremiteInitiale;
            graphe_arcs[k].arrive = extremiteTerminale;
            graphe_arcs[k].valeur = valeurArc;
            matAdj[extremiteInitiale][extremiteTerminale] = true;
            valAdj[extremiteInitiale][extremiteTerminale] = valeurArc;
            sourceGraphe >> extremiteInitiale;
            ++k;
        }
     
        // Affichage de la matrice d'adjacence
        cout << "\nMatrice d'adjacence\n";
        for (int i = 0; i < nbSommets; ++i)
        {
            for (int j = 0; j < nbSommets; ++j)
                cout << matAdj[i][j] << " ";
            cout << "\n";
        }
     
        // Affichage de la matrice de valeurs
        cout << "\nMatrice de valeurs\n";
        for (int i = 0; i < nbSommets; ++i)
        {
            for (int j = 0; j < nbSommets; ++j)
                cout << valAdj[i][j] << " ";
            cout << "\n";
        }
     
        // ==== Calcul ============================================================
     
        cout << "\nAlgorithme de Dijkstra\n";
        path = dijkstra(nbSommets, nbArcs, graphe_arcs, sommetDepart);
     
        return 0;
    }