Python erreur dans mon programme

Version imprimable

01/12/2013, 12h04
GuillaumeB.

Python erreur dans mon programme

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 ... :D

Merci de vos réponses !

Guillaume (ps: l'incrémentation ne marche pas à cause du copier coller je pense)
01/12/2013, 12h25
wiztricks
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:

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

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

Code:

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

01/12/2013, 13h09
wiztricks

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

De base notre prof nous a donné ce code :

Code:

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.

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:

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.

01/12/2013, 14h21
GuillaumeB.

D'accord merci beaucoup. J'avoue avoir du mal à comprendre tous le script ...

Je vais déjà essayer de comprendre le détail de celui qu'on m'a donné et je proposerais l'amélioration que vous m'avez donner, avec l'affichage de ma solution dans une fenêtre comme j'avais prévu.

Merci et bonne journée.