Discussion :

[MLK jr]

Bonjour,

Je suis à la recherche d'un algorithme parcourant un graphe orienté valué et permettant de me retourner les n plus courts chemin entre 2 points.

Les algorithmes classique de recherches de plus court chemin tel Dijkstra ou Bellman ne m'apporte qu'un unique chemin.

Quelqu'un a-t-il une idée pour réaliser ceci, ou bien sinon une idée pour un algo bourrin qui me calculerai l'intégralité des chemins du graphe?

Merci par avance pour toute aide

[chebreg]

je te propose la methode suivante :

Soit G ton graphe,
1- Tu lance un premier algorithme 'Dijkstra' classique. tu aurra comme resultat chemin constitué de x Arcs. tu sauvegarde cette liste (disons dans Larc(x) )

2- tu fait une boucle de x fois. et à chaque iteration tu concidére ton graphe en enlevant un arc de la liste Larc(x), tu obtient un graphe G' tel que : G'=G-Larc[i].
Si tu lance un 'Dijkstra' sur G' tu obtiendra le chemin le plus court ....
3- au final tu doit trier les chemins trouvés, pour selectionner le nombre voulu.

N! je croie que j'ai pas tres bien expliquer l'algo. mais l'idée est là

[benratti]

Je trouve la solution de chebreg pas tres naturel... j'aurais plutot tendense a essayer d'adapter 'Dijkstra' pour lui permettre de faire ce que tu veux.

Il faut en particulier regarder ce que fait dijkstra lorsque que tu as une egalité entre deux chemin, je me souviens plus tres bien mais il me semble qu'il oublie tout simplement un des deux chemins. Par exemple, si tu as un chemin de A vers B de meme coup que A vers B en passant par C, alors, il ne fait rien. Il suffirait simplement de se souvenir de ce chemin dans ta structure de donné. Ensuite, ca doit etre possible de recuperer tous les chemins egaux.

[FrancisSourd]

L'algorithme d'Eppstein résout ce problème

http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html

[Matthieu Brucher]

Avec Dijsktra, on ne garde pas que le chemin le plus court à chaque itération ? A la place, stocke les n plus courts chemins et travaille là-dessus. Pour moi, c'est une adaptation simple de Dijsktra, chercher les n plus courts chemins.

[MLK jr]

Merci beaucoup à tous, en effet l'algorithme de Eppstein répond exactement à mes besoins, je vais voir si j'en trouve une bonne implémentation ou une que je pourrais transcrire sans trop de problème en Java.

Sinon en effet une transformation de l'algo de Dijkstra peut-être possible d'après ce que je viens de trouver.

Merci encore pour votre aide

[MLK jr]

Pour info si jamais le sujet pouvait intéresser quelqu'un, j'ai trouvé sur le site de l'INRIA un package Java contenant un algorithme de recherches de n plus courts chemins.

http://www-sop.inria.fr/mascotte/mascopt/release/docs-1.2/mascoptLib-1.2/mascoptLib/algos/abstractalgos/KShortestPath.html
et
http://www-sop.inria.fr/mascotte/mascopt/