Bonjour,

J'ai un gros soucis: si je comprend très bien comment appliquer l'algorithme de Prim sur un graphe (pas de soucis), je ne comprend pas contre absolument pas la façon dont il est écrit (alors que je comprend parfaitement Dijkstra):

Je vais reprendre l'exemple donner sur la page wiki https://fr.wikipedia.org/wiki/Algori...im#Pseudo-code

Code:
fonction prim(G, s)
       pour tout sommet t
              cout[t] := +∞
              pred[t] := null
       cout[s] := 0
       F := file de priorité contenant les sommets de G avec cout[.] comme priorité
       tant que F ≠ vide
            t := F.defiler
            pour toute arête t--u
                si cout[u] > poids(t--u)
                       pred[u] := t
                       cout[u] := poids(t--u)
                       F.notifierDiminution(u)
                        
       retourner pred
Concrètement, sur l'exemple à gauche de ce code sur la page wiki, pour moi ce code ferait coût [D]=1 puis coût [B]=3 mais par l'arc AB (et non DB comme le fait Prim, puisque qu'on est censé parcourir tous les voisins de A avec ce code écrit tel quel). Ensuite seulement, t pointerait sur D.

Hors on est d'accord, c'est pas du tout ce qui censé se passer. Qu'est-ce que je ne comprend pas?

Et comment l'algo fait pour à chaque Tant Que:

- N'agir que sur l'arête la plus faible avant de changer t, plutôt que sur tous ses voisins.

- La rechercher sur toute la composante connexe et non pas seulement le sommet unique qu'est censé être t...

Je suis complètement perdu T_T, je vous serai très reconnaissant si vous pouviez m'aider. Merci d'avance.