Algorithme de Dantzig-Ford

Infos
L'algorithme de Ford-Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d'un graphe orienté. Le graphe peut être avec ou sans circuit et les poids (longueur) peuvent être positifs ou négatifs (contrairement à l'algorithme de Dijkstra). L'étude portera ici sur le principe du plus court chemin car c'est le plus utilisé.
Algorithme de Dantzig-Ford

L'algorithme de Ford-Dantzig résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre deux sommets d'un graphe orienté. Le graphe peut être avec ou sans circuit et les poids (longueur) peuvent être positifs ou négatifs (contrairement à l'algorithme de Dijkstra). L'étude portera ici sur le principe du plus court chemin car c'est le plus utilisé.

Entrées - Sorties

Entrées :
- Tableau G_SUCC
- Tableau G_ANT Sortie :
- Un système de chemin représenté par un arbre qui peut être appelé arbre final par exemple.

Structure de donnée

Intéressons nous d'abord de savoir comment on va organiser toutes nos données. Voici les différents éléments qui vont composer notre algorithme :
- Tableau de listes chainées - G_SUCC (Contient les successeurs des différents sommets)
- Tableau de listes chainées - G_ANT (Contient les antécédents des différents sommets)
- Un point d'origine x0 (Bloc mémoire stockant un entier)
- Tableau - Long (Contient la longueur d'un plus court chemin de x0 à x)
- Tableau - ANT (Contient les antécédents dans 'arbre finale')
- Tableau de liste chainées - SUCC (Contient les successeurs dans 'arbre finale')

Principe de l'algorithme

- On construit un arbre qui atteint tout les sommets du graphe depuis x0.
- On améliore au mieux cet arbre pour avoir la meilleure solution possible.

Amélioration de l'arbre

Soit d(a, b) la longueur de l'arc entre les sommets F et G. Si entre deux points F et G : Long(F) + d(F, G) < Long(G) alors le chemin n'est pas optimal. Dans ce cas :
- On modifie l'antécédent de G par F (au lieu de J par exemple).
- On modifie les successeurs de J (on enlève G) et F (on ajoute G). On remarque que G transite mais est toujours atteint.

Algorithme

1. Initialisation
- Construire un arbre dont la racine est x0 qui atteint tous les sommets.
- Calculer la longueur Long(x) associée à tout x accessible. (Mettre une valeur d'erreur autrement, par exemple +inf) 2. Corps tant que !cdt_arret faire chercher un arc plus court tel que Long(y) > Long(x) + d(x, y) /
- ---- principe de correction successive ----
-/ si arc(x, y) n'existe pas alors cdt_arret sinon si y est entre x0 et x dans l'arbre alors cdt_arret sinon modifier l'antécédent de y dans l'arbre par x (Cf:3.1) ajuster Long(y) pour les sommets atteignables depuis y dans l'arbre fin si fin si fin tant que

Le problème est-il résolu ?

Il faut voir avec du recul l'algorithme donné précédemment, on a deux possibilités de finir l'algorithme :

Le stop d'échec

Ce stop (cdt_arret) est réalisé par le test si y est entre x0 et x dans l'arbre alors. En effet, ici on obtient un circuit de longueur négative. Le problème ne convient donc pas à cet algorithme.

Le stop de réussite

Ce stop (cdt_arret) est réalisé par le test si arc(x, y) n'existe pas alors. En effet, ici ce test correspond à la non existence d'un chemin plus court : Long(y) > Long(x) + d(x, y) ne peut être trouvé.

Liens Internes

-Algorithme de Dijkstra
-Algorithme de Ford-Bellman

Sources

- Cours dispensé à l'Institut Supérieure d'Informatique de Modélisation et de leurs Applications ISIMA Dantzig-Ford Catégorie:Algorithme de recherche
Sujets connexes
Algorithme de Dijkstra   Algorithme de Ford-Bellman  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^