from graphviz import Graph , Digraph
from math import inf
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 dijkstra(self,debut,fin) :
        # initialisation du dictionnaire self.dij
        for nd in self.dic :
            self.dij[nd] = [inf , None , True]
        self.dij[debut] = [0 , debut , False]
        # traitement
        ndVisite = debut
        distance = 0
        while ndVisite != fin :
            for nd in self.dic[ndVisite] :
                if self.dij[nd][2] == True :
                    new_distance = distance + self.dic[ndVisite][nd]
                    if new_distance < self.dij[nd][0] :
                        self.dij[nd][0] = new_distance
                        self.dij[nd][1] = ndVisite
            dMin = inf
            ndMin = None
            for nd in self.dic :
                if self.dij[nd][2] == True :
                    if self.dij[nd][0] < dMin :
                        dMin = self.dij[nd][0]
                        ndMin = nd
                    ndVisite = ndMin
                    distance = dMin
            self.dij[ndVisite][2] = False

        # reconstitution
        nd = fin
        chemin = " "+fin
        while nd != debut :
            nd = self.dij[nd][1]
            chemin = " " + nd + " " + chemin
        return chemin


# Main
g1 = G()
g1.ajout_arete('A','B',90)
g1.ajout_arete('A','C',290)
g1.ajout_arete('A','D',175)
g1.ajout_arete('A','E',150)
g1.ajout_arete('B','E',180)
g1.ajout_arete('B','D',155)
g1.ajout_arete('B','C',185)
g1.ajout_arete('C','D',120)
g1.ajout_arete('D','F',105)
g1.ajout_arete('C','G',260)
g1.ajout_arete('E','F',135)
g1.ajout_arete('F','G',230)
g1.ajout_arete('E','D',110)
#g1.trace()

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