Algorithme des K plus courts chemins dans un graphe dirigé

Bonjour à tous,

J'ai cherché des exemples de code source Java idéalement, qui fait l'implémentation, la plus simple possible des algorithmes qui permet de détermine les K plus court chemin dans un graphe dirigé, pour les cas suivant :

1. Algorithmes de FordBellman
2. Algorithmes de dijkstra
3. Algorithmes de floydWarshall
4. S'il y d'autres qui sont plus performant (temps d'exécution et complexité) je suis preneurs

.

NB: Mes recherche en permise de trouver des exemples correctement exploitable pour :
dijkstra : http://www.vogella.com/tutorials/Jav...a/article.html
floydWarshall : http://javascool.gforge.inria.fr/?pa..../exercice.htm

Merci pour toutes vos suggestions et propositions

salut

il y a aussi l'algorithme A* très utilisé dans les jeux vidéo

:salut:

Les algorithmes que tu proposes sont parmi les plus efficaces en restant exacts (liste plus complète : https://en.wikipedia.org/wiki/Shorte...shortest_paths) : A* est une approche heuristique à la recherche de chemin (il estime la distance encore à parcourir entre un nœud et la destination sans la calculer). Pour améliorer les temps de calcul, en fonction de la forme du graphe, tu peux encore utiliser une représentation hiérarchique du graphe (pour trouver le plus court chemin entre ta rue et un hôtel à Zagreb, tu ne considères pas tous les petits chemins, plutôt le chemin jusqu'à une autoroute, puis le chemin en restant sur autoroute jusqu'à proximité de ta destination). Bien évidemment, gagner en temps complexifie le code.

OK, merci pour vos réponses.

Je c'est pour un grand graphe il peut avoir un problème combinatoire (peu prendre grand temps) pour un résultat

Donc je me demande s'il y a une solution pour réduire ce problème ? (Idéalement une proposition avec la méthode Branche and bound) sinon tout autre suggestion et proposition serai la bienvenu,

NB: si possible des exemples avec du code en java serai appréciable

Citation:

---

Envoyé par geforce

(Idéalement une proposition avec la méthode Branche and bound)

---

Une formulation en nombres entiers ? Voir https://en.wikipedia.org/wiki/Shorte...ng_formulation : d'abord résoudre ce programme (par séparation et évaluation, si tu le souhaites), puis explorer toutes les solutions de même coût pour les K chemins (puis ajouter une contrainte imposant un coût strictement supérieur aux meilleurs chemins pour aller chercher d'autres chemins pour atteindre les K, mais des chemins suboptimaux — ça peut très bien fonctionner avec des coûts entiers, nettement moins bien avec des réels). Dans ce cas, tu es pile poil dans du "classique" (sauf que peu de gens implémentent des algorithmes de résolution, c'est déjà très bien fait par d'autres).

Citation:

---

Envoyé par geforce

Donc je me demande s'il y a une solution pour réduire ce problème ?

---

Tu n'as pas d'explosion combinatoire, puisque les algorithmes sont polynomiaux (si c'est bien ça la question). Par contre, ça peut prendre beaucoup de temps (d'où les solutions heuristiques à la A* ou HPA*).

En y réfléchissant un peu (mais pas trop), A* implémente une forme de séparation et évaluation : partant de l'origine, tu choisis une branche à continuer en fonction de la distance (euclidienne) qui reste à parcourir après cette branche jusqu'à la destination ; ensuite, tu retires la branche évaluée et tu ajoutes les nœuds nouvellement accessibles dans l'ensemble des nœuds actifs.

Bonjour dourouc05,

Je n’ai pas très bien compris ta 1er réponse tu parles d'un exemple de séparation évaluation avec des nombre entier ? Si c'est le cas peu tu me faire un déroulement que je puisse appliquer par la suit avec un algorithme de parcours de graphe?

Puis pour la 2em, je crois que c'est moi qui a fait une erreur (oui c'est vrais que l’algorithme peu prendre beaucoup de temps) amis serai plus problématique NP-complet.

Merci

J'aurais tendance à penser l'approche par nombres entiers indépendante du parcours de graphe : la traversée est modélisée sous la forme d'(in)équations au lieu d'opérations directement sur le graphe (le parcours consiste à créer ces équations).