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") |
