Salut,
 
J'ai un petit problème à résoudre, je dois modéliser un réseau routier par un graphe et adapter l'algo de Ford Fulkerson de sorte d'étudier la capacité d'un réseau routier reliant la ville X et la ville Y. Les divers trajets suivis par les véhicules peuvent utiliser des routes de capacités variables et traverser des villes de taille variable.
 
J'ai bien compris l'algo de Ford Fulkerson mais pour l'implémentation c'est autre chose    
 
Pour la structure de données à utiliser mon idée est la suivante: un graphe peut être représenté par des liste, je définit une liste des noeuds et à chacun de ces noeuds, j'associe une listes de noeuds successeurs et une liste de noeuds prédéceseurs.
 
Quelqu'un a-t-il une idée pour l'algo "détaillé" et/ou pour l'implémentation?
Est-ce que d'après vous la structure de données que je veux utiliser est adéquate?
 
D'avance merci
Si vous voulez plus de détails n'hésitez pas  
Toute remarque est évidement la bien venue...

N'importe quelle structure est adéquate du moment qu'elle respecte les contraintes de l'algo. Au vu de ce que tu dis, la réponse pourrait autant être oui que non car tu ne donnes pas assez de détail. Pour l'algo, on en trouve plein d'implémentations différentes sur le net (généralement avec un problème de transport de café sur des bateaux)

L'algo que j'utilise ici fait intervenir une chaine augmentante et le graphe d'écarts (ou réseau résiduel).
 
J'espère que c'est un peu plus clair!?

Je connais le principe de l'algo, merci. Ce n'est pas ça qui manque dans ton explication, c'est la manière dont tu va l'implémenter. Si tu en as déjà une version en LDA, la structure à utiliser t'apparaitra tout naturellement.

Ok excuse moi
Ben non pas encore !!!
 
Comme tu le sais cette version de l'algo n'est valable que pour un réseau ayant une source et un puit, je considère donc 2 sommets fictifs qui seront respectivement la source et le puit de mon réseau (de la source partira un arc allant au sommet X, et du puit arrivera un arc partant de Y) pour les sommets (villes) ayant une capacité, je les éclate en 2 sommets (entrée et sortie de la ville) dont l'arc les joignant a une capacité égale à celle du sommet initial.
Voilà où j'en suis... pas très loin je sais... c'est pour ça que je demande de l'aide

hint: As-tu réellement besoin des sommets fictifs?

Je pense que oui car l'algo de FF recherche le flot max dans un réseau ayant une source et un puit.
Or dans un réseau routier (que je dois modéliser), ou l'on doit rechercher le flot max entre 2 villes X et Y on n'est pas certain (et c'est même très rarement le cas) qu'il n'y a que des "arcs partants" du sommet X et que des "arcs arrivants" au sommet Y. L'utilisation de ces sommets fictifs permet d'utiliser FF.
As-tu une autre solution?

FF ne recherche pas entre une source et un puit, il recherche entre 2 points, un point de départ et un point d'arrivée, qui "bornent" le réseau"...
 
X ne ressemble-t-elle pas a un point de départ et Y a un point d'arrivée? (ce qu'essaie de te dire Gizmo)

Non justement, X et Y sont deux sommets quelconques du réseau... le fait d'utiliser 2 sommets fictifs permets de rechercher le flot entre 2 sommets qui "bornent le réseau"
Rq: le flot max entre X et Y et entre les 2 sommets fictifs sont égaux
ça réponds à ta question?
 

hint2: condition d'arrêt.

lorsqu'il n'y a plus de chemin augmentant dans le réseau résiduel

Pour ta structure de donnée, il faut que tu te poses la question de savoir ce que tu privilégie : la rapidité d'exec ou d'implémentation. Cela dépend aussi du langage et de la taille de tes instances.