130
Recherche opérationnelle
Sur l'exemple de la figure 8, cette méthode donne les vecteurs suivants :
On pouvait s'arrêter à
Pour trouver le chemin de valeur minimale, on cherche le sommet tel que :
1
1
(5)
1
(5)
1
= i
i

puis le sommet tel que :
2
1
(5)
2
(5)
1
= i
i
i
i

Etc.
L'algorithme de Bellmann-Kalaba est souvent plus performant que l'algorithme de Ford
au niveau du temps de calcul sur ordinateur par le fait des retours en arrière fréquents
dans l'algorithme de Ford. Sa complexité est en
.
Méthode matricielle
C'est une généralisation de l'algorithme précédent (Bellmann-Kalaba) ; c'est une bonne
méthode lorsque :
a) il s'agit d'obtenir les distances minimales entre chaque couple de sommets de graphe;
b) il n'est pas utile de conserver les itinéraires de valeur minimale entre les couples de
sommets, mais seulement les valeurs de ces itinéraires.
Cette méthode s'appuie sur une opération matricielle d'un type particulier : pour un
graphe quelconque, on considère la matrice
constituée par les valeurs
des
arcs du graphe (s'il n'y a pas d'arcs reliant
,
). Soit alors la matrice :
1
1
2 =
M
M
M
L'opération
ayant le sens suivant :
Sommets
1
2
3
4
5
6
7
8
9
10
Itérations
p = 1
1
3
0
p = 2
4
3
5
1
3
0
p = 3
7
5
8
4
3
4
1
3
0
p = 4
9
7
5
6
4
3
4
1
3
0
p = 5
8
7
5
6
4
3
4
1
3
0
p = 6
8
7
5
6
4
3
4
1
3
0
p = 7
8
7
5
6
4
3
4
1
3
0
p = 8
8
7
5
6
4
3
4
1
3
0