# -*- coding: utf-8 -*- """ @author: JMG """ import numpy as np #import sys def Dijkstra(G,sdebut): x,y = np.shape(G) assert x==y n=x assert sdebut < n-1 dinfini = 1000 #Création de la liste des couples [d,sp] ( [distance,sommet précédent]) des sommets provisoirement pondérés SProv = [] #Création de la liste des sommets marqués S = [] #Création du tableau d'analyse tableauAnalyse = [] #Initialisation de la liste des sommets provisoirement pondérés T = list(range(0,n)) #Création de la première liste des couples [d,sp] for i in T: SProv.extend([[dinfini,0]]) #La distance du sommet de début est fixée à 0 et son prédecesseur est lui-même SProv[sdebut][0] = 0 SProv[sdebut][1] = sdebut #Le sommet de début est marqué définitivement et donc enlevé de la liste des sommets provisoires T.remove(sdebut) #Il est ajouté à l'ensemble des sommets marqués S.append(sdebut) #Chaque sommet adjacent est marqué du poids de l'arête la reliant à sdebut for i in T: print(i,G[sdebut][i]) if G[sdebut][i] != 0: print ("Detection pour " ,i) SProv[i][0] = G[sdebut][i] SProv[i][1] = sdebut print ("Initialisation", T,SProv) #On termine en créant la première ligne du tableau d'analyse tableauAnalyse.append(SProv) #([SProv.copy()]) ligne = 0 #ligne courante du tableau d'analyse while len(T)>0: return tableauAnalyse,S ### Test ma=ma3() ta,chemin = Dijkstra(ma,4) print(np.shape(ta)) for i in range(0,np.shape(ta)[0]): for j in range(0,np.shape(ta)[1]): print(ta[i][j]) #,end='') #print() print(chemin)