Cours 5

L'algorithme de Dantzig-Ford résout un problème de plus court chemin. Il sert à trouver un chemin optimal (le plus court ou bien le plus long) entre un sommet initial et tous les autres sommets d'un graphe orienté. Le graphe peut être avec ou sans circuit et les poids (longueur) peuvent être positifs ou négatifs

George Bernard Dantzig (8 novembre 1914 à Portland - Oregon - 13 mai 2005 à Palo Alto, en Californie) est un mathématicien américain, notamment inventeur de l'algorithme du simplexe en optimisation linéaire.

3.1 Objectif de l'algorithme de Dantzig-Ford :

Chercher dans un réseau (graphe) les plus courts chemins qui relient un sommet de départ s_deb à tous les autres sommets du graphe.

3.2 Description de l'algorithme de Dantzig-Ford :

d[sdeb] ← 0 // Initialisation

$ = {sdeb}

pour tout sommet s ∈ S et s ≠sdeb faire

d[s] ← ∞

Γ ^-1[s] ← NIL

Fin pour

Tant que $ ≠ ∅ faire // Itérations

retirer le premier sommet u de $

pour tout arc (u, v) ∈ A faire

si d[v] > d[u] + w(u, v) alors

d[v] ← d[u] + w(u, v)

Γ ^-1[v] ← u

$ ← v

Fin si

Fin pour

Fin pour

3.3 Principe de l'algorithme de Dantzig-Ford :

La méthode de Dantzig-Ford trouve les longueurs de tous les plus courts chemins. Elle part du graphe vide, puis insère les sommets : 0, 1, 2… n−1. Au fur et à mesure, avant d’insérer le sommet k, elle gère D[i][j] les plus courtes distances du sommet i au sommet j, pour i et j inférieurs à k.

3.4 Exemple d'application :

4. Algorithme de Floyd-Warshall :

matrice d'adjacence de (matrice )

La première matrice des prédécesseurs Γ ^-1 contient :

• NIL s'il n'y a pas d'arc menant de i à j,

• i si i=j,

• i s'il existe une arc de i à j≠i.

for

to for