Algo ford-fulkerson (theorie des graphes)

[ben-am]

Bonjour
voila je suis étudiant en informatique et j'ai un module de théorie des graphe , je suis tombé sur un exercice qui me bloque jusqu'à présent, on avait étudié avec notre prof l'algorithme de ford-fulkerson pour trouver dans n'importe quel graphe le flux maxima et bien évidemment le chemin qui correspond, dans cette exercice y'a un graphe et ce qui est demandé c'est de trouver le chemin qui a le moins d'obstacles sachant que chaque arête a un nombre d'obstacle précis,
je voie pas comment je pourrais utiliser ford-fulkerson dans ce cas la

merci de bien vouloir m'aider

[fatal_error]

salut,

et si c'était pas ford fulkerson qu'il faut utiliser?
En tout cas, moi non plus jvois pas. Genre dans FF, on est pas obligé de saturer une arrete alors que pour franchir tous les obstacles...si.
En plus, dans FF on peut avoir deux chemins utilisés simultanéments pour subvenir au flot max,alors que dans lexo, ben il en faut qu'un oO.

Donc autant pondre ton algo comme un grand.
On peut prendre un graphe de debut S, et d'arrivée P.
Puis remonter les aretes qui pointent vers P en mettant à jour la distance du noeud par rapport à P.
genre :

Code: Tout sélectionner

ListeNoeuds = P (noeud du début vaut noeud de fin)
pour tous les noeuds N de G, N = infini
marqueMoi(G,ListeNoeuds)
debut
 listeAExplorer = vide
 pour tous les noeuds N de ListeNoeuds
  pour toutes les aretes parentes A de N
   listeAExplorer += N
   si poids de N + poids de A < poids Noeud parent de N
   alors
     Noeud parent pointe vers N
     poids Noeud parent = poids de N + poids de A
   finsi
  fin pour
 fin pour
 marqueMoi(G,listeAExplorer)
fin

Apres faut voir si ya des cycles et choses de ce mauvais gout...
Au final, ben t'as tous les successeurs de S, qui pointe vers leur suivant et le chemin est déterminé. T'as plus qu'a choisir le successeur de S avec le poids le moins important.

enfin, je pense:D

[ben-am]

non mais je peux utiliser l'algo de djikstra par exemple sa ira bcp plus vite, j'aimerai juste savoir si c'est possible avec ford fulkerson ou quelque chose qui y dérive

[fatal_error]

erf oui pour djikstra. J'avais pensé A* pis jme suis dit "non c'est moins sur", et du coup j'ai zappé Mr djikstra...

Bref pour revenir à fulkerson, ce que j'aurais envie de faire, perso, c'est de garder à peu près le même algo, sauf que sur les arrêtes, tu mets toutes les capacités avec des valeurs négatives. Et tu autorises des flots négatifs.

Le plus petit flot possible (en valeur absolue) c'est donc celui qui vaut exactement la capacité de l'arrete.

Toujours est-il que je pense pas que ca garantisse un unique chemin.