124
Recherche opérationnelle
Algorithme 2:
Algorithme de Ford
a) Si est le nombre de sommets du graphe, numéroter les sommets
de façon
quelconque.
b) Affecter provisoirement à tout sommet i un poids égal à 0 si
et à + si
c) Chercher un arc tel que
; on remplace alors par
d) Reprendre en c) jusqu'à ce qu'aucun arc ne permette plus de diminuer les .
Cette procédure fournit bien le ( ou les ) chemins de valeur minimale.
En effet, il est évident que les
sont des majorants des valeurs des plus courts chemins
entre
. Comme le graphe est sans circuit négatif, ce plus court chemin entre 1 et ,
s'il existe, a une valeur finie.
Et comme, d'après l'étape d, les
sont continument décroissantes tout en restant
positives, les
tendent vers une limite.
Montrons que cette limite
est bien la valeur du plus court chemin entre
. Il
existe un sommet tel que :
( est le dernier sommet utilisé pour diminuer . De même il existe un sommet
tel
que :
etc.
On constitue ainsi une suite
de sommets tels que
.
Montrons que s'il n'existe pas de circuit de valeur nulle, les sommets de la suite
précédente sont tous distincts. En effet, si l'on trouve un sommet deux fois, c'est que
l'on a la disposition suivante :
Pour le circuit
on a :