Python erreur dans mon programme

**GuillaumeB.** · 01/12/2013, 12h04

Bonjour,

Je suis en T°S spé ISN et j'ai un Dm à rendre pour dans deux semaines, le but étant d'améliorer l'algorithme de Dijkstra avec ce que l'on connais, voire un peu plus.

Voici mon code :

from tkinter import *

Nvilles = 6 # On définit le nombre de ville par défault, ici 6.

i=0 # Compteur pour la boucle
u=0

L0=[] # liste de base pour la matrice avec les distances entre les villes
L1=[]
L2=[]
L3=[]
L4=[]
L5=[]

while i<=6: # Remplissage des listes par l'utilisateur avec les distances qu'ils souhaitent sous forme de matrice
i=i+1
while u<6:
nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville A."))
L0.append (nombre)
u=u+1
i=i+1
u=0
while u<6:
nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville B."))
L2.append (nombre)
u=u+1
u=0
i=i+1
while u<6:
nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville C."))
L2.append (nombre)
u=u+1
u=0
i=i+1
while u<6:
nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville D."))
L3.append (nombre)
u=u+1
u=0
i=i+1
while u<6:
nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville E."))
L4.append (nombre)
u=u+1
u=0
i=i+1
while u<6:
nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville F."))
L5.append (nombre)
u=u+1
i=i+1

m_adjac = [L0,L1,L2,L3,L4,L5]

""" ALGROITME DE DIJKSTRA """
DIJ=list()
for i in range (Nvilles):
DIJ.append([1000000,"X","N"])
ville_select=0
dist_interm=0
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
DIJ[ville_select][2]="0"
dist_interm=DIJ[ville_select][0]
for i in range(1,Nvilles):
print (DIJ[i])
print ("\n")
chemin=list()
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])

Mafenetre = Tk()
Mafenetre.title('Alogrithme de Dijkstra')
Mafenetre.geometry('300x300+300+300')
Affichage = Label(Mafenetre, text="Le chemin le plus est (à lire à l'envert) est :")
Affichage.pack()
Affichage = Label(Mafenetre, text=(chemin))
Affichage.pack()
bouton=Button(Mafenetre,text='Quiter',command=Mafenetre.destroy)
bouton.pack()
Mafenetre.mainloop()

Lorsque je lance l'algo tous va bien pour ma boucle de création de matrice, et des que j'ai finis il me met une erreure : "IndexError: list index out of range". Et je ne vois absolument pas d'où cela pourrait venir ...

Merci de vos réponses !

Guillaume (ps: l'incrémentation ne marche pas à cause du copier coller je pense)

**wiztricks** · 01/12/2013, 12h25

Salut,

Sans les indentations, votre programme est illisible.
Essayez de le reposter en le mettant entre les balises code/code: jouez avec le "#" qui est dans le menu d’édition des messages.
Il s'agit d'obtenir:

Code :

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

1
2
from tkinter import *
Nvilles = 6 # On définit le nombre de ville par défault, ici 6.

- W

**GuillaumeB.** · 01/12/2013, 12h35

Oui pardon je ne savais pas comment faire, sa devrait être mieux la !

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
from tkinter import *
 
 
 
Nvilles = 6     # On définit le nombre de ville par défault, ici 6.
 
i=0      # Compteur pour la boucle
u=0
 
L0=[]   # liste de base pour la matrice avec les distances entre les villes
L1=[]
L2=[]
L3=[]
L4=[]
L5=[]
 
while i<=6:          # Remplissage des listes par l'utilisateur avec les distances qu'ils souhaitent sous forme de matrice
    i=i+1
    while u<6:
        nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville A."))
        L0.append (nombre)
        u=u+1
    i=i+1
    u=0
    while u<6:
        nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville B."))
        L2.append (nombre)
        u=u+1
    u=0
    i=i+1
    while u<6:
        nombre=int(input("Entrer les 6 distances entre les villes en fonction de votre ville C."))
        L2.append (nombre)
        u=u+1
    u=0
    i=i+1
    while u<6:
        nombre=int(input("Entrer les 6 distances entre les villes en fonction  de votre ville D."))
        L3.append (nombre)
        u=u+1
    u=0
    i=i+1
    while u<6:
        nombre=int(input("Entrer les 6 distances entre les villes en fonction  de votre ville E."))
        L4.append (nombre)
        u=u+1
    u=0
    i=i+1
    while u<6:
        nombre=int(input("Entrer les 6 distances entre les villes en fonction  de votre ville F."))
        L5.append (nombre)
        u=u+1
    i=i+1
 
m_adjac = [L0,L1,L2,L3,L4,L5]
 
 
 
""" ALGROITME DE DIJKSTRA """
DIJ=list()
for i in range (Nvilles):
    DIJ.append([1000000,"X","N"])
ville_select=0
dist_interm=0
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
    DIJ[ville_select][2]="0"
    dist_interm=DIJ[ville_select][0]
    for i in range(1,Nvilles):
        print (DIJ[i])
    print ("\n")
chemin=list()
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])
 
 
 
Mafenetre = Tk()
Mafenetre.title('Alogrithme de Dijkstra')
Mafenetre.geometry('300x300+300+300')
Affichage = Label(Mafenetre, text="Le chemin le plus est (à lire à l'envert) est :")
Affichage.pack()
Affichage = Label(Mafenetre, text=(chemin))
Affichage.pack()
bouton=Button(Mafenetre,text='Quiter',command=Mafenetre.destroy)
bouton.pack()
Mafenetre.mainloop()

**wiztricks** · 01/12/2013, 13h09

Salut,

Pas facile de s'assurer que votre code cohérent avec le pseudo-code présenté ici.

En regardant ce qui est saisi, on dirait que toutes les villes sont reliées entre elles: a chaque "ville" saisie une distance vers les 5 autres est entrée.

Vous voulez faire quoi exactement?

- W

**GuillaumeB.** · 01/12/2013, 13h16

De base notre prof nous a donné ce code :

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
Nvilles=6
 
L0=[0,3,1,0,0,0]  
L1=[3,0,1,2,0,0]
L2=[1,1,0,3,5,0]
L3=[0,2,3,0,1,3]
L4=[0,0,5,1,0,1]
L5=[0,0,0,3,1,0]
 
m_adjac=[L0,L1,L2,L3,L4,L5]
 
DIJ=list()
for i in range (Nvilles):
    DIJ.append([1000000,"X","N"])
ville_select=0
dist_interm=0
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
    DIJ[ville_select][2]="0"
    dist_interm=DIJ[ville_select][0]
    for i in range(1,Nvilles):
        print (DIJ[i])
    print ("\n")
chemin=list()
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])

Le but du DM est de commenter le code, et d'en apporter une amélioration.
Ce que je voulais faire, c'est que l'utilisateur puisse entrer lui même la matrice qu'il souhaite ( elle comporte la distance entre les villes)et ensuite afficher le plus court chemin dans une fenêtre Tkinter.

**wiztricks** · 01/12/2013, 13h47

Dans ce cas, c'est que les variables avec lesquelles travaillent l'algo. ne sont pas construites comme attendu.
A mon sens, la première amélioration a faire est de mettre le précieux boulot du prof dans une boite appelée fonction: on se concentre sur ce qui entre et ce qui sort sans trop s'occuper du détail.
Ca donne un fonction plus_court_chemin a qui on balance une matrice d'adjacence et qui retourne les résultats affiches.

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
# -*- coding: utf-8 -*-
def plus_court_chemin(m_adjac):
    Nvilles = len(m_adjac)
    DIJ=list()
    for i in range (Nvilles):
        DIJ.append([1000000,"X","N"])
    ville_select=0
    dist_interm=0
    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
        DIJ[ville_select][2]="0"
        dist_interm=DIJ[ville_select][0]
        ## for i in range(1,Nvilles):
        ##     print (DIJ[i])
        ## print ("\n")
    chemin=list()
    ville=Nvilles-1
    chemin.append(ville)
    while ville !=0:
        ville=DIJ[ville][1]
        chemin.append(ville)
    return chemin[::-1], DIJ[Nvilles-1][0]
 
if __name__ == '__main__':
 
    Nvilles=6
 
    L0=[0,3,1,0,0,0]  
    L1=[3,0,1,2,0,0]
    L2=[1,1,0,3,5,0]
    L3=[0,2,3,0,1,3]
    L4=[0,0,5,1,0,1]
    L5=[0,0,0,3,1,0]
 
    m_adjac=[L0,L1,L2,L3,L4,L5]
    chemin, total_distance = plus_court_chemin(m_adjac)
 
    print ("plus court chemin: ",chemin)
    print ("distance totale : ", total_distance)

Cela fait, peut importe comment seront saisies les villes ou affiche le résultat... pourvu que cela respecte ce qui est attendu par la fonction. (i.e. l'interface)

- W
edit: oops, j'ai remplace "chemin.reverse()" par chemin[::-1].

PS: une amelioration a faire serait le choix du depart et de l'arrivee.

Python erreur dans mon programme

Python

Vue hybride

Discussions similaires

Partager

Partager