Nvilles = 5
L0 = [0,1,1.4,2.8,3.6] # la matrice d'adjacence est mise en place de façon très simple ici
L1 = [1,0,1,2.2,3.2] 
L2 = [1.4,1,0,1.4,2.2]
L3 = [2.8,2.2,1.4,0,1]
L4 = [3.6,3.2,2.2,1,0]

m_adjac = [L0,L1,L2,L3,L4] # m_adjac[4][2] contient la valeur 5, etc. 

def Djikstra(Nvilles, m_adjac):
	DIJ=list() # la liste DIJ mémorise les données du tableau (cf. étape 1)
	for i in range (Nvilles):
		DIJ.append([1000000,"X","N"]) 
		
	ville_select=0 # numéro de la ville sélectionnée; 0 = ville de départ
	dist_interm=0 # distance pour arriver à la ville sélectionnée; 0 au départ
	while ville_select < Nvilles-1:
		minimum=1000000
		for n in range(1,Nvilles):
			if DIJ[n][2]=="N":
				dist=m_adjac[ville_select][n]
				dist_totale=dist_interm+dist
				if dist != 0 and dist_totale < DIJ[n][0]:
					DIJ[n][0]=dist_totale
					DIJ[n][1]=ville_select
				if DIJ[n][0]<minimum:
					minimum=DIJ[n][0]
					pville_select=n
		ville_select=pville_select # pville_select = numéro de la prochaine ville sélectionnée
		DIJ[ville_select][2]="O"
		dist_interm=DIJ[ville_select][0]
		
		for i in range(1,Nvilles):
			print (DIJ[i])
		print( "\n")
		
	chemin=list() # reconstitution du plus court chemin, en partant de la ville d'arrivée
	ville=Nvilles-1
	chemin.append(ville)
	while ville != 0:
		ville=DIJ[ville][1]
		chemin.append(ville)
	print ("plus court chemin, à lire à l'envers : ",chemin)
	print ("distance totale : ",DIJ[Nvilles-1][0])
	

Djikstra(Nvilles, m_adjac)