Discussion :

[thierry1967]

Bonjour à tous,
J'ai programmé un algorithme du plus court chemin (Djikstra) et cela fonctionne très bien avec mon réseau de test dont je vous joint une image ci-dessous.



Le code en python est le suivant et fonctionne très bien.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

LE PROBLEME que je rencontre est le suivant.
lorsque je rentre un nouveau réseau, plus grand (matrice de 300*300 et 19 lignes) une erreur d'exécution apparaît :
in <module> appartenance(i, ProchainSommet)] TypeError: list indices must be integers or slices, not NoneType

je ne comprends pas cette erreur de type qui surgit et d'indices. quelqu'un peut-il m'éclairer ?
au cas ou cela pourrait être utile, je prépare la grande matrice, celle de 300*300, via excel puis word avant de la copier/coller dans l'IDE.
merci pour vos explications et votre aide.

[YCL-1]

Bonsoir,

effectivement c'est curieux mais je serai tenté de penser que votre matrice n'est pas correcte.
En êtes-vous sûr ?

Par exemple avec le test de sommer les lignes et les colonnes pour vérifier qu'ils sont bien des nombres :

sum( [sum(ligne) for ligne in matrice] )Autrement vous pouvez rajouter pour le debug un print lorsque l'erreur apparait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
try:
    La ligne ou le code à tester...
except TypeError:
    print(i, ProchainSommet)
    raise # Remonte l'erreur

[YCL-1]

Le problème doit venir de la fonction appartenance.

Car elle retourne k si elle remplie une condition. Mais si la boucle range(0,len(lignes)) se termine alors la fonction n'a pas prévu de retourner quelque chose, et par défaut une fonctionne retournera toujours None.

[thierry1967]

Merci YLC-1 pour ces conseils. Je vais regarder ça.
je suis novice en python, je ne maîtrise pas encore toute la sémantique de vos formules, notamment le TRY, je vais m'améliorer.