Discussion :

[Yakurena]

Bonsoir,
Je suis en train de concevoir l'algorithme de Ford-Fulkerson pour calculer les flux possibles dans un réseau routier. J'aimerais être sur de la façon de faire pour ne pas partir sur un "mauvais chemin" dans le codage. Voici la façon que j'ai utilisée :
- Pour représenter le graphe, une liste de successeurs( moins d'espace mémoire qu'une matrice). Je n'ai pas prévu de liste de predecesseurs, car logiquement, 2 villes sont toujours reliées dans les 2 sens (sauf en cas de sens interdit, mais il n'y en a jamais sur les grandes routes). Elle serait donc inutile : un successeurs serait toujours en même temps predecesseur. J'ai aussi prévu des champs "capacité" et "flux" pour chaque element de la liste des successeurs, qui correspond à la capacité et au flux de l'arc correspondant. J'aurais pu aussi faire un tableau pour cela, mais cela aurait aussi fait de l'espace mémoire inutile (avec les cases qui correspondent à des arcs qui n'existent pas).
- Je me suis aussi demandé si je pouvais prendre des arêtes au lieu d'arcs, vu que les arcs sont toujours symétriques (dans les 2 sens ou pas du tout). Le problème est que je n'ai jamais vu l'algo de F-F appliquable avec des graphes non orientés ; j'aimerais savoir si c'est possible ?
- Pour coder l'algorithme, il y'a un truc qui me paraît bizarre : quand je trouve un arc dont la destination est le sommet "courant", je peux prendre cet arc en décrémentant son flux(d'après l'algo). Concrètement, cela reviendrait donc à "virer" une voiture d'une voie de circulation, mais je ne vois pas en quoi ça trouve un chemin dans l'autre sens? J'ai aussi un doute sur la condition pour prendre un arc "à l'envers" : logiquement, ce serait que son flux soit supérieur ou égal à 0 (cad qu'il y'ait au moins une voie de circulation occupée) ?
- Pour le reste, j'ai aussi prévu une structure de liste chaînée pour contenir tous les sommets d'un chemin qu'on trouve, avec leur marquage(pris vers l'avant ou vers l'arrière).
Voilà, ce serait bien si vous pouviez me donner vos avis sur cette façon de faire pour savoir s'il y'a des choses à changer avant de me lancer dans le codage ...
Merci d'avance.

[Matthieu Brucher]

Si tu le fais en C++, regarde du côté de la librairie de graphes de Boost, ça sera plus simple peut-être pour toi.
En gros, pour stocker tout ça, on stocke la liste des noeuds, puis à chaque noeud, on donne une liste de successeurs avec leur capacité.