Discussion :

[usri06]

j'ai un arbre couvrant minimal (sous forme d'ensemble d’arêtes chaque arete est un couple (i,j) ) comment à partir de cet ensemble je puisse trouver un chemin entre de nœuds x et y ??
Comment extraire un tel chemin ??
ce chemin est t'il minimal puisque on a travaillé sur un arbre couvrant minimal ?

[bertry]

Salut,

comment à partir de cet ensemble je puisse trouver un chemin entre de nœuds x et y ??
Comment extraire un tel chemin ??

Utiliser un algo comme Dijkstra ou A*

ce chemin est t'il minimal puisque on a travaillé sur un arbre couvrant minimal ?

Non, ce chemin n'est pas forcement minimal:

Par exemple, sur ce graph, le plus court chemin entre le sommet le plus à gauche et le sommet le plus bas mesure 9, alors que si je ne passe que par l'arbre couvrante minimum il mesure 21.