bonsoir, je cherche un algorithme simple et rapide + code c++ pour la recherche de plus long chemin entre tout couple de sommets dans un graphe en utilisant la matrice d'adjacence.
résultat matrice des distances
j'ai essayé de modifier l'algorithme de floyd mais sa n'a pas marché pour moi.
Merci

Precise ce que tu veux. Tu veux le plus long plus court chemin ? ou tu veux le plus long plus long chemin?

le chemin de distance maximale, le plus long plus long chemin mr godrik

Sur un graphe arbitraire le probleme est NP-Difficile:
https://en.wikipedia.org/wiki/Longest_path_problem

mr godrik, ce n'est pas un graphe arbitraire, c'est un graphe orienté sans cycle mais de grande taille (réseau routier)

bluepoint_ non ça marchera pas

Si ton graphe est un DAG, alors il existe une solution en temps linéaire (cf liens wikipedia de Godrik)

Merci

oui c'est un DAG la solution est dans la multiplication des poids par (-1) en cherchant le plus court chemin puis on renverse les résulta Merci á vous.

Un reseau routier est un DAG? What The Fuck?

bluepoint, en general ca ne marche pas ed faire *-1 et de chercher le plus court chemin parceque faire *-1 introduit des cycles negatifs. auquel cas les algo de plus court chemin ne sont pas elementaire et les algo comme dijkstra et FB ne marchent pas.

Comme c'est un dag alors tu peux faire le hack du *-1, mais c'est dommage parceque l'algo ne va pas etre lineaire.

Enfin bon, si c'est un dag et que toutes les aretes sont positive alors c'est completement trivial en effet. C'est quasiment le meme algo que topological sort. Le plus long chemin par d'un sommet sans predecesseur et va a un sommet sans sucesseur. En d'autre terme le plus llong chemin est recursivement defini par programmation dynamique. Il suffit d'initialiser les plus long chemin a 0 partout. Et iterativement prendre un sommet sans predecesseur et mettre a jour ces successeur sur un arc x->y tu fais PLC(y) = max (PLC(y), PLC(x)+l(x,y)) et ensuite tu retire x. Si tu implementes la suppression de x et l'extraction de sommet sans predecesseur correctement, alors l'algo est en O(E).

en faite, je décompose le réseau routier en un ensembles des sous réseaux acycliques pour avoir les DAGs, Merci godrik.