1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
|
# algorithme de dijkstra appliqué au réseau de métro parisien
import time
import datetime
# matrice qui représente les liaisons entre les sommets (stations) du graphe
matrice=[
[0,10,7,0,0,0,0,0,0,0],
[10,0,0,0,0,6,0,0,0,0],
[7,0,0,9,0,12,0,0,0,0],
[0,0,9,0,2,0,0,0,0,6],
[0,0,0,2,0,4,0,3,0,0],
[0,6,12,0,4,0,8,0,0,0],
[0,0,0,0,0,8,0,4,11,0],
[0,0,0,0,3,0,4,0,0,9],
[0,0,0,0,0,0,11,0,0,14],
[0,0,0,6,0,0,0,9,14,0]
]
# nombre de stations( sommets) dans le graphe
taille=len(matrice)
# initialisation
temps=[1000]*taille # tous les sommets sont initialement à un temps infini (1000) du sommet de départ
pere=[-1]*taille # -1 signifie qu'un sommet ne possède pas encore de sommet père
traitement=["n"]*taille # aucun sommet n'est traité pour le moment
exploration=0 # pour detecter la première exploration
# représentation des lignes et des sommets qu'elles contiennent
lignes=[[0,1,5,4,3],[0,2,5,6,7,9],[2,3,9,8,6],[4,7]]
# liste pour la représentation des vitesses de chaque ligne
VitesseDesLignes=[1]*len(lignes)
# fonction qui permet de vérifier si on prend une correspondance (changement de ligne)
def correspondance (sommet1,sommet2):
for k in range(0,len(lignes)):
if sommet1 in lignes[k] and sommet2 in lignes[k]:
return False
else:
return True
# fonction qui permet d'associer le déplacement à une ligne, utile pour sélectionner la bonne vistesse
def appartenance (sommet1,sommet2):
for k in range(0,len(lignes)):
if sommet1 in lignes[k] and sommet2 in lignes[k]:
return k
SommetDepart=int(input("Indiquez le sommet de départ:"))
print()
SommetArrivee=int(input("Indiquez le sommet d'arrivée:"))
print()
TempsDeCorrespondance=int(input("Indiquez le temps de correspondance en secondes:"))
print()
reponse=input("Les lignes circulent-elles toutes à la même vitesse (o/n)?")
print()
if reponse=="o":
VitesseDesLignes[0]=int(input("indiquez la vitesse (en m/s) applicable à toutes les lignes:"))
for i in range(1,len(lignes)):
VitesseDesLignes[i]=VitesseDesLignes[0]
elif reponse=="n":
for i in range(0,len(lignes)):
print("Indiquez la vitesse de la ligne " + str(i) + ";",end="")
VitesseDesLignes[i]=int(input())
print()
print()
DebutTraitement = time.time()
print()
print("Merci de patienter...")
print()
#initialisation
temps[SommetDepart]=0 # le sommet de départ est à un temps 0 de lui même
pere[SommetDepart]=-2 # -2 caractérise le sommet d'origine
while traitement[SommetArrivee]!="o": # la boucle se termine lorsque le traitement du sommet d'arrivée est demandé
pas=0
resultat="n"
while resultat =="n": # recherche du premier sommet non traité (voisins non explorés)
if traitement[pas]=="n":
PremierTemps=temps[pas]
ProchainSommet=pas
resultat="o"
pas+=1
for i in range(0,taille): # recherche le sommet non traité avec la plus petite distance - au premier tout de boucle c'est forcément le sommet de départ dont la distance a été initialisée à 0
if traitement[i]=="n":
if temps[i]<PremierTemps:
PremierTemps=temps[i]
ProchainSommet=i # permet de déterminer le sommet dont les voisins doivent être explorés
# exploration des sommets voisins
for i in range(0,taille):
if matrice[ProchainSommet][i]!=0 and traitement[i]=="n": #lien avec le sommet voisin et non traité
TempsIntermediaire=temps[ProchainSommet]+(matrice[ProchainSommet][i])/VitesseDesLignes[appartenance(ProchainSommet,i)]
if exploration>1:
if correspondance(pere[ProchainSommet],i):
TempsIntermediaire+=TempsDeCorrespondance
if TempsIntermediaire<temps[i]:
temps[i]=TempsIntermediaire
pere[i]=ProchainSommet
exploration+=1
traitement[ProchainSommet]="o"
chemin=[]
LectureDuPere=pere[SommetArrivee]
while LectureDuPere!=SommetDepart:
chemin.append(LectureDuPere)
LectureDuPere=pere[LectureDuPere]
chemin.reverse()
chemin.insert(0,SommetDepart)
chemin.insert(len(chemin),SommetArrivee)
print("Le chemin est:",end="")
for sommet in chemin:
print (">"+str(sommet).zfill(3),end="")
print(" et le temps le plus court vaut:" + str(temps[SommetArrivee]))
"""for i in range(100000):
j=0
j+=1"""
print()
TempsEcoule=time.time()-DebutTraitement
print()
print ("Temps d'execution = %f" %TempsEcoule + " secondes") |
Partager