from graphviz import Graph , Digraph
from math import inf
import os
os.environ["PATH"] +=os.pathsep+'C:/Program Files (x86)/Graphviz/bin/'
graphe = Graph()

class G :
    def __init__(self) :
        self.dic = {}
        self.dij = {}


    def ajout_arete(self,s1,s2,d) :
        if s1 not in self.dic :
            self.dic[s1] = {}
        self.dic[s1][s2] = d
        if s2 not in self.dic :
            self.dic[s2] = {}
        self.dic[s2][s1] = d

    def trace(self) :
        graphe.clear()
        deja_trace = []
        for s in self.dic :
            for nd in self.dic[s] :
                if {s,nd} not in deja_trace :
                    graphe.edge(str(s),str(nd),str(self.dic[s][nd]))
                    deja_trace.append({s,nd})
        graphe.view()

    def traitement_sommet(self,s,distance) :
            drapeau = False
            min = inf
            nd_min = s
            # on parcourt les voisins de s
            for nd in self.dic :
                if self.dij[nd][2] == 0 :
                    drapeau = True
                    if nd in self.dic[s] :
                        new_distance = distance + self.dic[nd][s]
                        if new_distance < self.dij[nd][0] :self.dij[nd] = [new_distance , s , 0]

                    if self.dij[nd][0] < min :
                        min = self.dij[nd][0]
                        nd_min = nd
            s = nd_min
            self.dij[s][2] = 1
            distance = self.dij[s][0]
            return s,distance,drapeau

    def affichage(self,sommet,fin) :
        nd = fin
        l = []
        while nd != sommet :
            l.append(nd)
            nd = self.dij[nd][1]
        l.append(sommet)
        print('Longueur = ',self.dij[fin][0])
        for i in range(len(l)-1 , -1 , -1) :
            print(l[i] , end = " ")

    def dijkstra(self,sommet,fin) :
        for nd in self.dic :
            self.dij[nd] = [inf , None , 0]
        self.dij[sommet] = [0 , sommet , 1]
        s = sommet
        distance = 0
        drapeau = True
        while drapeau :
            s,distance,drapeau = self.traitement_sommet(s,distance)
        self.affichage(sommet,fin)


# Main
g1 = G()
g1.ajout_arete('A','B',2)
g1.ajout_arete('A','C',1)
g1.ajout_arete('B','C',2)
g1.ajout_arete('B','D',1)
g1.ajout_arete('B','E',3)
g1.ajout_arete('C','D',4)
g1.ajout_arete('C','F',5)
g1.ajout_arete('C','E',3)
g1.ajout_arete('E','F',1)
g1.ajout_arete('F','D',6)
g1.ajout_arete('F','G',2)
g1.ajout_arete('G','D',5)


#g1.trace()

g1.dijkstra('A','G')