Algorithme de Dantzig et 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é.

Sommaire 1 Entrées - Sorties 2 Structure de donnée 3 Principe de l'algorithme 3.1 Amélioration de l'arbre 3.2 Algorithme 3.3 Le problème est-il résolu ? 3.3.1 Le stop d'échec 3.3.2 Le stop de réussite 4 Liens internes 5 Sources

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 l'arbre final)
• Tableau de liste chainées - SUCC (Contient les successeurs dans l'arbre final)

Principe de l'algorithme

1. On construit un arbre qui atteint tout les sommets du graphe depuis x0.
2. 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