from math import inf

Graphe = {
	'A':{'B':2, 'C':1},
	'B':{'A':2, 'C':2, 'D':1, 'E':3},
	'C':{'A':1, 'B':2, 'D':4, 'E':3, 'F':5},
	'D':{'B':1, 'C':4, 'E':3, 'F':6, 'G':5},
	'E':{'B':3, 'C':3, 'D':3, 'F':1},
	'F':{'C':5, 'D':6, 'E':1, 'G':2},
	'G':{'D':5, 'F':2}
	}



def mini(listeSommets, marque):
	"""
	Renvoie le sommet de listeSommets
	ayant la plus petite marque.
	"""
	marquePlusPetite = inf
	for s in listeSommets:
		if marque[s] < marquePlusPetite:
			marquePlusPetite = marque[s]
			sommetPlusPetit = s
	return sommetPlusPetit
	
	
def dijkstra(graphe, depart, arrivee):
	
	# initialisation
	marque = {}
	for sommet in graphe: marque[sommet] = inf
	marque[depart] = 0
	
	non_selectionnes = [sommet for sommet in graphe]
	 
	pere = {}
	pere[depart] = None
	
	# boucle principale:
	while non_selectionnes:
		# sélection:
		s = mini(non_selectionnes, marque)
		if s == arrivee: break
		non_selectionnes.remove(s)
		
		# mise à jour des voisins du sommet sélectionne:
		VoisinsAVisiter = [sommet for sommet in graphe[s] if sommet in non_selectionnes]
		for sommet in VoisinsAVisiter:
			p = marque[s] + graphe[s][sommet] 
			if p < marque[sommet]:
				marque[sommet] = p
				pere[sommet] = s
	
	return marque, pere
	 
	
def affichageCheminMin(graphe, depart, arrivee):
	distance, pere = dijkstra(Graphe, depart, arrivee)
	print("La distance de {} à {} est de longueur {}.".format(depart, arrivee, distance[arrivee]))
	chemin = arrivee
	sommet = arrivee
	while pere[sommet] != None:
		chemin = pere[sommet] + chemin
		sommet = pere[sommet]
	print()
	print("Le chemin de {} à {}: {}.".format(depart, arrivee,chemin))
 

affichageCheminMin(Graphe, 'A', 'G')