""" 
	Implémentation de l'Algorithme de Dijkstra
	https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

	directement tirée de: 
	https://algodaily.com/lessons/an-illustrated-guide-to-dijkstras-algorithm/python 
"""

import math

"""
	Le graphe est celui de l'exercice 2 p.3 du document: "Internet et 
	localisation, cartographie  et mobilité, routage et calculs 
	d'itinéraires" sur educsol.education.fr.
	
	Le graphe est représenté sous forme de liste d'adjacence: on donne 
	une liste des sommets, et pour chaque sommet, un dictionnaire donne 
	la liste des sommets voisins avec le poids de chaque arrête.
"""

graph ={
	'a' :{'c':3,'g':6},
	'b':{'c':14, 'd':20, 'h':7, 'g':4 }, 
	'c':{'a':3,'b':14,'d':6 },
    'd':{'c':6,'b':20,'e':4} ,
    'e':{'d':4,'h':3,'f':22},
    'f':{'e':22,'h':4,'m':5,'n':6},
    'h':{'f':4,'e':3,'b':7,'g':19,'i':1,'l':1,'m':12},
    'g':{'a':6,'b':4,'h':19,'i':21},
    'i':{'g':21,'h':1,'l':9,'j':5},
    'j':{'i':5,'k':2},
    'k':{'j':2,'l':1},
    'l':{'k':1,'i':9,'h':1,'m':5,'n':9},
    'm':{'n':3,'f':5,'h':12,'l':5},
    'n':{'f':6,'m':3,'l':9},    
	}

# on indique le sommets de départ
source = 'a'
# on indique le sommets de destination
destination = 'n'

# liste des sommets non visités
unvisited = graph

# liste des distances à partir du sommets d'origine
shortest_distances = {}

# chemin le plus court
route = []

# liste des chemins entre deux sommets
path_nodes = {}

# initialisation à +infini des distances de chaque sommet du graphe 
# au sommet de départ 
for nodes in unvisited:
    shortest_distances[nodes] = math.inf
    
# la distance du sommet de départ à lui même est nulle    
shortest_distances[source] = 0

# pour tous les sommets non visités ...
while unvisited:
    min_node = None
    # on cherche le sommet non visité qui est le plus proche 
    # du sommet de départ
    for current_node in unvisited:
        if min_node is None:
            min_node = current_node
        elif shortest_distances[min_node]> shortest_distances[current_node]:
            min_node = current_node
    # à partir de ce sommet, on met à jour les distances des sommets 
    # voisins qui n'ont pas été visités        
    for (node, value) in unvisited[min_node].items():
        if value + shortest_distances[min_node]< shortest_distances[node]:
            shortest_distances[node] = value + shortest_distances[min_node]
            # on garde le sommet dans le chemin, car il permet d'avoir un 
            # un parcourt le plus court
            path_nodes[node] = min_node
    # le sommet est visité, on le retire de la liste des sommets
    # à traiter        
    unvisited.pop(min_node)
    
# on calcule le chemin le plus court en partant de la destination    
# on remonte à la source, en empruntant les chemins les plus courts
node = destination
while node != source:
	#la liste est construite en ajoutant en début de liste le sommet 
    try:
        route.insert(0, node)
        node = path_nodes[node]
    except Exception:
        print('Path not reachable')
        break
# on ajoute le point de départ au début de la liste        
route.insert(0, source)

# présentation du résultat
if shortest_distances[destination] != math.inf:
    print('La distance la plus courte est ' + str(shortest_distances[destination]) +' km')
    print('Elle correspond au chemin ' + str(route))