Voila, je suis arrive tranquille a l'algo du plus court chemin avec dijkstra (mon graphe est entierement pondere et est oriente). Maintenant j'aimerais faire l'inverse. J'ai beau tourner l'algo de Dijkstra dans tous les sens, je me rends compte qu'on ne peut pas l'appliquer    
Conclusion : existe-t-il une autre solution que la recherche exhaustive ?
 
PS: j'ai cherche sur google mais j'ai rien trouve de bien convaincant comme doc.
 
EDIT : j'ai trouve ceci : http://mathforum.org/epigone/sci.m [...] ntu.edu.tw
...apparemment c l'algo de Floyd qu'il faudrait voir...

La recherche du plus long chemin??? Est-ce que t'es sur qu'il existe?

A priori, le chemin le plus long est infiniment long... ca va être dur à calculer...

Le chemin le plus long d'un point a un autre....
 
 
 
... c'est de ne pas y aller

 
tu cherches un chemin hamiltonien ?

Probleme NP-complet...  
Bonne chance

Ce problème prends du sens uniquement sur des graphes orientés. En effet, s'il existe plus d'un chemin entre deux points d'un graphe non orienté, ce problème n'as pas de solution puisqu'alors un cycle existe passant par ces deux points. Donc pour deux points d'un graphe non orienté, on a trois cas de figure:
-pas de chemin du tout, pas de solution
-un seul chemin, solution égale au cout de ce chemin
-plusieurs chemin, pas de solution non plus (aussi grand qu'on le souhaite)
 
Pour un graphe non orienté, c'est la même chose sauf qu'il peut y avoir plusieurs chemins entre deux points sans pour autant y avoir de cycle (et il est facile de le vérifier par un parcours quelconque).
En excluant ce cas, il reste deux cas de figure:
-pas de chemin du tout, pas de solution
-un ou plusieurs chemin, solution égale au cout du plus long chemin(s)
 
Dans ce dernier cas de figure, peut être peut on entreprendre d'appliquer un stratégie gloutone semblable à l'algo de dijkstra sur le calcul du plus court chemin à origine unique, mais j'avoue que je n'ai pas la preuve que ça marche

 
vivi   ... et meme le circuit hamiltonien :
(cf def ci apres) -> http://www.bruno-garcia.net/www/polyro/node11.html
 
En fait je cherche a resoudre le probleme du travelling salesman. (voyageur de commerce).
Bien entendu, j'arrive a trouver le chemin le plus court avec Dijkstra avec 8 villes. Je voudrais maintenant trouver le chemin le plus long avec ces 8 villes. (pour etablir des statistiques)...moi qui croyait au depart que c t un pb trivial (inverser Dijkstra) ben en fait c'est moins facile que ca    
J'ai pu voir dans un ebook de McGraw Hill :
 

 
je connais pas cet algo...v voir ca de plus pres

Pour le plus long chemin...
 
Prend le taxi !
 

j'ai pu voir encore :

 
Donc il doit bien exister un algo efficace

Et tu fais comment?

 
bon cette fois je crois que je tiens le bon bout

 
ben   , tu trouveras l'algo  

Oups désolé en fait je t'avais mal compris. Oui, pour trouver le chemin le plus court on utilise effectivement Dijkstra. J'avais compris que tu parvenais a résoudre le PVC avec 8 villes. Alors forcément je me demandais comment tu faisais, et si ca pourrait marcher avec plus de villes!

Algorithme de Bellman modifié ? ( mais bon si ya un cycle c'est mort. )
 
www.google.fr

je vais dire une connerie, mais t'as essayé en faisant 'nouvelle longueur = 1 / longueur' pour chaque segment ? ou avec une soustraction ? ça donne quoi ?

Ben de toutes facons si y'a un cycle le plus long chemin n'existe pas...

laisse faire, l'algo est aussi complique que de resoudre le voyageur de commerce. Ca revient au meme que de resoudre le PVC (c un pb de bonne permutation).

Ca revient au meme que si ton graphe est complet... je me trompe?

 
tiens je viens de faire une recherche sur les problemes NP-difficiles
dont :

 
Je l'a v dit, c'est le meme probleme que le PVC  
 
Ace17 : le graph est considere complet, c'est plus sportif comme ca
 
ou encore plus clairement :
 

 
y'en a pas mal sur ce site : http://www.csc.liv.ac.uk/~ped/teac [...] ed_np.html

et si tu passes tous tes poids en négatif, et que tu cherches le plus court, ça te donnerai pas ce que tu cherches ?

 
   
 
1) Dijsktra ne marche pas avec des poids negatifs.
 
2) l'algorithme de Floyd, meme s'il marche avec des poids negatifs,  ne resouds que le chemin le plus court entre une PAIRE de sommet. Trouver le chemin le plus long ne se reduit pas seulement a verifier le chemin le plus long entre toutes les paires de sommets.

Hello,
 
Pour les DAGs (directed acyclic graph), avec le tri topologique [g]inversé[\g] on sais trouver la longueur du plus long chemin. c'est facile à faire avec un DFS (parcourt depht first search), tu peux utiliser l'ordre preorder. Je sais pas si ça peux t'aider car ce n'est que pour les DAGs.

 
Oui tout a fait    
...et tu sais comment on construit un DAG ?   ... comme tu l'a dis : avec un depth-first search. Bref en gros tu construis tout l'arbre, donc c'est un peu pourri   . Comme d'hab, 10 noeud OK, 11 ca commence a ralentir, 12 c'est mort.  

Construire un DAG ? ben si tu n'as pas de cycle alors tu as un DAG. Pour voir si ton graphe est un DAG il suffit que tu lances un DFS et que tu vérifie qu'il n'y a pas de backedges. Un DAG ce n'est qu'un graphe sans cycles.
 
Mais en fait je pense pas que ca te convienne car il s'agit ici du plus long chemin en terme d'étape, de sommet travesé, on ne tiens pas compte des poids sur les arcs commes le fait dijkstra

mais le DFS c'est juste pour faire le tri topologique et ne t'inquiète pas ca marche avec plus de 10 noeuds biensur... DFS c'est un tps proportionel à V2 si tu utilises un matrice d'adjacense et V+E pour une liste d'adjacence ... donc rien de terrible
 
V= nb de sommets
E= nb d'arcs
 
quand tu dis construire tout l'arbre ? tu veux dire du backtracking ? oui mais ca c'est la pire des solutions que tu peux faire ... oui ca marche mais c'est vraiment pas optimal, ce n'est pas un dfs, mais un backtracking (ou brute force)

joubliais, apres la tri topologique, il reste a faire un truc en un tps proportionel à V ... donc au total ca reste la complexité du DFS.  
 
si tu penses que ca te convient comme truc je peux te poser l'algo en pseudo code mais je te demande avant pour pas faire l'effort de m'en souvenir pour rien (meme si c un bon exo) =)

mexx20=> avec ton tri topologique tu crées tout l'arbre. Je veux dire que tu vas tout le parcourir avec un DFS !. Parcourir un arbre entièrement va poser un énorme problème de temps !. Il s'agit d'un algo à complexité exponentielle (= NP-complet). Comme je l'ai dis, pour un graphe avec 10 noeuds OK, 11 ça ralenti, 12 c'est mort (==> complexité de x puissance N, x constante et N taille du probleme (dans ce cas N = nombre de noeuds/relations)).
De toute facon, il n'est pas difficile de voir que c'est un problème NP-complet, pourquoi ?
 
Imagine que tu developpes TOUT l'arbre SAUF une arête (la dernière qui te crée la dernière feuille de l'arbre). Ben il se peut très bien que en ayant developpé cette dernière arête, celle-ci appartient au chemin le plus long (dans le cas où son coût est gigantesque par rapport à toutes les autres arêtes) => conclusion : ben tu es obligé de développer tout l'arbre pour être sûr d'avoir la solution optimale. Bon après il y a toujours moyen de faire un algo de type B&B (branch and bound) qui permet de couper des branches dans ton arbre. Mais l'algo devient difficile pour ne pas gagner énorme...ton algo restera toujours d'une complexité exponentielle du fait que tu résouds le problème en développant l'arbre.
 
PS : et quand je parle du plus long chemin, c'est bien en terme de poids, pas du nombre d'arête du chemin (qui revient à dire que toutes les arêtes ont un poids de 1...ce qui est réducteur comme généralisation du problème.) hein  

Bon apparement tu n'as pas bien compris.
 
Oui le problème du plus long chemin EN TERME DE POIDS est "intractable" (NP-Complet si tu veux). Il faut un backtracking (recherce exhaustive).  
 
Moi je suis venu te dire qu'il existe une solution efficace pour le problème en TERME DES SOMMETS.  
 
Tu dis que c'est réducteur, je ne suis pas d'accord. Il s'agit de 2 problèmes différents.  
 
Encore une fois : un DFS n'est pas un backtracking.
 
[quote]
ne t'inquiète pas ca marche avec plus de 10 noeuds biensur... DFS c'est un tps proportionel à V2 si tu utilises un matrice d'adjacense et V+E pour une liste d'adjacence ... donc rien de terrible
 
V= nb de sommets
E= nb d'arcs  
[\quote]
 
Tu peux lancer DFS sur des graphes enormes pour construire un tri topologique. Aucun problèmes.
 
Bon maintenant; il reste à savoir si pour ton application tu as besoin du plus long chemin en terme de poids ou en terme de sommets.

Ouais pour le coup de la généralisation finalement tu as quand meme raison car comme tu le dis si bien ce sont des arcs de longueur 1. Enfin voilà, si t'es intéressé par l'algo pour ce cas particulier donc, fait moi signe et je te montrerai que le tri topologique c'est une connerie qui fonctionne sur des graphes gigantesques.

En fait c'est meme tres réducteur
1. Tout les poids sont à 1.
2. C'est uniquement pour les DAGs
3. Ca te calcule uniquement les plus longs chemins d'un sommet vers n'importe quel autre. Il ne s'agit de pas de paires de sommets ...
 
Ouais c'est bien nul comme truc, mais c'est la seule méthode efficace dont je me souvienne, mais je pense qu'il y a d'autres astuces pour d'autres types de graphes pour éviter la recherce exhaustive  ... => Google

 
Ouai bof j'apelle pas ca efficace. Honnêtement, ca sert a quoi un algo de chemin le plus court/long en utilisant un DAG. Rien qu'a faire un tri topologique, tu construis l'arbre donc, si tu parcours l'arbre en entier, ca ne sert a rien de construire un DAG apres  

Heu... pas efficace ? V^2 ou V+E ... :-|
 
C'est efficace car ce n'est ni plus ni moins qu'un DFS.
 
On ne construit pas l'arbre des solutions on fait un simple parcours du graph ! C'est linéaire. Tu veux du constant ? T'es fou toi
 
Je te rappelle que le tri topologique ce n'est rien de terrible, un simple DFS ! Il suffit de garder la numérotation postordre. Il exisste d'autres méthodes comme celle qui consiste à retirer les sources une à une en diminuant le degré entrant, mais c'est équivalent en terme de complexité. Il y a d'autre méthodes, toutes équivalentes.
 
Je ne te parle pas de construire un DAG, mais c'est une hypthèse que ton graph soit un DAG.

Mais bon, c'est pour une classe de graph correspondant aux critères énoncés plus haut. Mais c'est toujours comme ça pour les problèmes où on ne connait pas de solutions efficaces, il y a toujours certaines classes parfois très restreintes pour lesquelles il existe de solutions efficaces. Jusqu'au jour où un génie magicien nous sortira la solution élégante.
 
Bon allez pour l'exercice voici de mémoire l'algo pas très compliqué finalement :
 

 
Voilà, ici tu auras le tri topologique, après un simple DFS
Ensuite, il reste un truc de la meme complexité, donc ca reste toujours celle du DFS.
 

 
Alors c'est simple mais un peu complexe à s'y retrouver : la longueur du plus long chemin de post[i] vaut lg[i]. Si maintenant tu veux connaitre le chemin le plus long en partant du sommet s, il suffit de parcourir le vecteur chemin de cette façon :
 

C'est pas efficace, d'accord, c'est optimal

 
Deux phrases contradictoires ? (en anglais : ALL-PAIRS-SHORTEST-PATH => cf. Floyd)
 

 
La valeur du poids n'a pas d'importance. Le probleme reste NP-Complet
 

 
Oui le DFS est efficace en mémoire. En temps non !
 

 
Encore contradictoire. Ton parcours de tous les chemins possibles dans ton graphe, c'est comme la complexité d'un arbre. Imagine un graphe complètement connecté, le temps du DFS explose.
 

 
Encore contradictoire.
 
Et enfin, le rappelle le sujet de l'algo (peut etre plus explicite cette fois): Etant donné un graphe sans cycle, orienté et pondéré, trouver le chemin le plus long.
 
Et pour finir :

 
Je pense donc qu'il est inutile de s'attarder plus sur ce problème...que j'ai abandonné depuis longtemps .

"Ca te calcule uniquement les plus longs chemins d'un sommet vers n'importe quel autre. Il ne s'agit de pas de paires de sommets ...  "
 
Non ce n'est pas contradictoire. Bon, soyons plus clair car il vrai que cette phrase porte à confusion. En fait ce dont je parle c'est : tu donnes un sommet S et depuis ce sommet il te calcule le plus long chemin, mais tu ne sais pas où tu vas aboutir, c'est ça que je voulais te dire lorsque je disais "vers n'importe quel sommet". Tu l'aurais compris si tu avais un peu regardé l'algo ...
 
Moi je laisse tomber le problème de faire comprendre que dans certains problèmes non résolu il y a parfois des cas particulier où une solution efficace existe. En l'occurence les graphes ayant les caractéristiques précitées plus haut.
 
Oui je sais bien que tu veux la solution générale, moi j'ai juste dis ce que je savais sur le sujet. Et puis on en sais rien, ca dépend des applications, tu pouvais aussi ne pas être certain de ce que tu souhaitais.
 
Soit tu es de mauvaise foi, soit tu ne comprend rien.
 
Ca m'apprendra à perdre mon temps à vouloir rendre service, j'ai comme l'impression que tu n'as même pas fait l'effort de comprendre ce que je voulais dire.  
 
Et puis arrête de te cacher derrière Floyd et Sedgewick, les choses évoluent, la théorie des graphes est étudiée massivement de part le monde et tes bouquins sont statiques.

Pour la complexité du DFS, je maintient ce que j'ai dis. Elle est moindre que celle d'un backtracking (recherche exhaustive).

Honnêtement je préfère une bonne explication à un algo. Et d'après ton explication j'ai comme l'impression que tu parcours tout l'arbre.
Pour le DFS ca te parcours un chemin du graphe, backtracking, ca te parcours tout les chemins du graphe. On peut assimiler le backtraking comme une succession de DFS
Bon pour résumer de la complexité du DFS:

 
et voila

Non, je ne parcours pas tout l'arbre, je ne fais qu'un tri topologique avec un DFS.
 
Bon, un DFS n'a pas une complexité exponentielle. Sa complexité temporelle est en V^2 si tu utilises une matrice d'adjacence pour représenter ton graphe (de part la structure d'une matrice) et en V+E si tu utilises une listes d'adjacence (de part la structure de liste). Il s'agit donc d'une complexité temporelle LINEAIRE (part rapport aux données). Ca n'explose rien du tout avec tes 12 sommets de rien du tout.
 
Faut-il te rappeller l'algo du DFS ? De toute façon je l'ai posté plus haut.
 
Par contre un backtracking (qui parcout l'arbre de toutes les solutions, aussi appelé recherche exhaustive) à une complexité exponentielle. Et dans ce cas en effet, ca explose vite lorsque le nombre de sommets grandit.
 
Les complexités que tu exposes de je-ne-sais-ou sont celles d'une recherche exhaustive.
 
Je pense donc que tu confonds DFS et backtracking. Si c'est le cas, je te pardonne. Sinon je souhaite te voir bruler vif.
 
Bon, et pour l'algo je veux bien t'expliquer son fonctionnement si le code ne te suffit pas mais je perd un petit peu patience.