recherche du plus cours chemins entre 2 sommets d'1 graphes

**must19** · 04/04/2006, 13h40

je faire un programme qui cherche le plus cours chemins entre deux sommets d'un graphe. et on ma imposé l'Algorithme de SOLLIN.

je sais pas trop comment ca marche et ne trouve pas trop d'explications su cet algorithme.

une explication sur le fonctionnement de cette algorithme serai la bienvenue.
et meme de la docs des site qui en parle.

et merci

**FrancisSourd** · 04/04/2006, 13h53

Je connais un algorithme de Sollin pour les arbres couvrants de coût min mais pas pour les plus courts chemins.

**nicolou** · 04/04/2006, 14h10

Salut,
j'ai trouvé çà :

Code :

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

1
2
3
4
5
6
7
8
Algorithme de Sollin
(1) Choisir arbitrairement un sommet en dehors de ceux déjà retenus et relier par l’arête
de valeur la plus faible ce sommet à l’un des sommets auxquels il est adjacent
(2) Lorsque l’ensemble des sommets a été utilisé entièrement :
a. le résultat est un arbre et le problème est résolu
b. on n’a que des sous-arbres et on considère chacun comme les sommets d’un
multi-graphe, les arêtes de ce multi-graphe étant toutes les arêtes qui sont
susceptibles de connecter deux à deux ces sous-arbres et reprendre l’étape (1)

et une autre description de la procédure ici :
http://www-igm.univ-mlv.fr/~berstel/Elements/EAChap7.pdf

Je n'ai jamais utilisé cet algo, on m'avait fait utiliser l'algorithme de Dikjstra pour résoudre le pb du "voyageur de commerce" (c'est exactement le pb auquel tu es confronté, donc avec quelques recherches sur ces 3 mots tu dois pouvoir trouver pas mal d'infos)

Je connais un algorithme de Sollin pour les arbres couvrants de coût min mais pas pour les plus courts chemins.

En fait je pense que c'est la même chose, sauf que le poids associé aux arêtes est caractérisé par une distance.

Nico

**FrancisSourd** · 05/04/2006, 11h51

Non, le problème du plus court chemin n'est ni celui du voyageur de commerce, ni celui de l'arbre couvrant. Il s'agit de 3 problèmes bien distincts et résolus par des algorithmes différents.