Discussion :

[paxapaxa]

Bonjour,
Voici le code de l'algorithme de dijsktra et je souhaiterais intégrer des classes, des attributs dedans mais je ne sais pas quelle classe faire, quels objets et attributs créer pour que cela soit utile.
Je sais bien que c'est dans l'autre sens que l'on réfléchit mais on m'a imposé de travailler avec des classes après que le code soit déjà rédigé.
Merci de votre aide,

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
# -*- coding: utf-8 -*-
# Dijkstra
 
graphe = [[],[2,1,4,7],[1,1,5,1],[4,1,7,3,5,1],[1,7,3,1],[6,2,2,1,3,1],[5,2,7,3,8,1,9,4],[3,3,8,1,6,3],[6,1,7,1,9,2],[6,4,8,2],[2,1,3,1,11,3],[5,1,10,3]]
 
 
def recupere(Liste, sommet):
    """récupère l'indice dans la liste d'un sommet, s'il est présent"""
    if len(Liste)>0:
        for k in range(len(Liste)):
            if Liste[k][0]== sommet:
                return True, k
    return False, -1
 
def mini(Liste):
    """ renvoie l'indice du minimum dans la liste"""
    minim = Liste[0][1]
    indice = 0
    for k in range(len(Liste)):
        if minim> Liste[k][1]:
            minim = Liste[k][1]
            indice = k
    return minim, indice
 
def Dijkstra(G, depart, arrivee):
    solution =[]
    optimal = [[depart, 0, []]]
    atteint = []
    nbtotal = len(G)
    fini = False
    while not fini:
        sommet , distance, precedent = optimal[-1] #on prend le dernier sommet étudié dans la liste optimal
        nb = len(graphe[sommet])//2 # C'est le nombre de sommets qu'on peut atteindre à partir de ce sommet
        if nb>0:
            for k in range(0, 2*nb, 2):
                s = graphe[sommet][k] # on étudie le sommet s
                test, indice = recupere(optimal, s) 
                if not test : # si le sommet n'est pas déjà dans optimal
                    test, indice = recupere(atteint, s)
                    if test : # on regarde s'il a été atteint déjà
                        if atteint[indice][1] >  distance + graphe[sommet][k+1]:
                            atteint[indice][1] = distance + graphe[sommet][k+1] # on améliore le chemin
                            atteint[indice][2] = sommet # on réinitialise la façon de l'atteindre
                    else :
                        atteint.append([s, distance + graphe[sommet][k+1], sommet]) # on le rajoute dans les sommets atteints
 
            #on s'intéresse au nouveau sommet de chemin minimal qu'on vient de trouver
            minim, indice = mini(atteint)
            info = atteint.pop(indice)#on le supprime des sommets atteints en récupérant les informatiosn le concernant
            optimal.append(info) # on le rajoute aux sommets de chemin optimal
            if info[0]==arrivee:
                L = reconstruit_chemin(optimal,depart,arrivee)
                fini = True
            if len(atteint)==0:
                fini = True
    return L
 
 
def reconstruit_chemin(optimal, depart, arrivee):
    sommet = arrivee
    L=[arrivee]
    while sommet!=depart:
        test, indice = recupere(optimal, sommet)
        L.append(optimal[indice][2])
        sommet=optimal[indice][2]
    L.reverse()
    return L

[wiztricks]

Salut,

Voici le code de l'algorithme de dijsktra et je souhaiterais intégrer des classes, des attributs dedans mais je ne sais pas quelle classe faire, quels objets et attributs créer pour que cela soit utile.
Je sais bien que c'est dans l'autre sens que l'on réfléchit mais on m'a imposé de travailler avec des classes après que le code soit déjà rédigé.

Ben, vous pouvez exprimer en classes qu'un Graph est composé de Node et de Edge... et définir les attributs intéressants pour faire fonctionner l'algo. avec cette distribution des rôles.

- W