Discussion :

[zo-68]

Bonjour,

Je me retrouve, en écrivant un code Python, devant un problème pour le dijkstra

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
import numpy as np
oo = np.inf  #Définir l'infini
sommets = [0,1,2,3,4]
 
Adj = np.array([[0,8,2,1,oo],
                [8,0,5,6,1],
                [2,5,0,oo,3],
                [1,6,oo,0,oo],
                [oo,1,3,oo,0] ])
 
def plusCourt(T,I):
    minimum = oo
    indice = 0
    for i in I:
        if T[i] < minimum and T[i] > 0:
            indice = i
            minimum = T[i]
    return indice
 
 
def dijkstra(Adj,s0):
    n = len(Adj)
    Dist = oo * np.ones(n)
    Dist[s0] = 0
    NonMarques = [k for k in range(n)]
    Marques = [ ]
    while len(Marques) < n:
        i = plusCourt(Dist,NonMarques)
        Marques.append(i)
        NonMarques.remove(i)
        for k in NonMarques:
            if Dist[i] + Adj[i,k] < Dist[k]:
                Dist[k] = Dist[i] + Adj[i,k]
    return Dist

En effet, en testant dijkstra(Adj,0) avec l'exemple, aucun soucis. Mais si je tente 1,2,3,4, je reçois l'erreur suivante

Code :

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

1
2
3
4
5
6
7
8
<tmp 1> in dijkstra(Adj, s0)
     28         i = plusCourt(Dist,NonMarques)
     29         Marques.append(i)
---> 30         NonMarques.remove(i)
     31         for k in NonMarques:
     32             if Dist[i] + Adj[i,k] < Dist[k]:
 
ValueError: list.remove(x): x not in list

Comment corriger ça?

Merci d'avance!

[wiztricks]

Salut,

Comment corriger ça?

Avec l'instruction "print" vous affichez les valeurs retournées par "plusCourt" pour voir laquelle est retournée 2 fois.
Puis vous réfléchissez au pourquoi.

- W

[zo-68]

En effet ma fonction plusCourt renvoie toujours l'indice 0 si le s0 choisit dans dijkstra est différent de 0, ce qui fait que c'est le 0 qui revient plusieurs fois.

Je vais voir si je peux trouver comment je vais avancer, et je reviens à vous si je bloque encore.

Merci!

Edit: Plutot qu'un supérieur strict à 0, il fallait un supérieur ou égal.
Merci, problème réglé!