Initialement, on choisit simplement le chemin (i, j) comme plus court chemin ; en
notant P
0 le premier tableau, on a donc P
0
i,j = j et
P
0 =
⎡
⎢
⎢
⎢
⎣
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
⎤
⎥
⎥
⎥
⎦
Mais pour aller par exemple de 5 à 3, il vaut mieux passer par le sommet 1, car on
a D
0
5,1 + D
0
1,3 = 1 + 1 < 3 = D
0
5,3 . On va systématiquement comparer la durée d’un
trajet direct à celle d’un trajet passant par le sommet 1.
I) Formons un tableau D
1 contenant les durées des plus courts chemins passant
éventuellement par le sommet 1. On pose donc
D
1
i,j =
D
0
i,1 + D
0
1,j si D
0
i,1 + D
0
1,j < D
0
i,j
D
0
i,j
sinon
Si l’on a trouvé que le chemin (i, 1, j) est plus rapide que (i, j), il faut modifier
le tableau P en posant P i,j = 1. On définit donc un tableau P
1 tel que
P
1
i,j =
1 si D
0
i,1 + D
0
1,j < D
0
i,j
j sinon
Nous avons remarqué que le chemin (5, 1, 3) a un poids 2 inférieur au poids de
(5, 3), donc on pose D
1
5,3 = 2 et P
1
5,3 = 1. On vérifie qu’aucun autre chemin ne
peut être raccourci en passant par le sommet 1. Il vient donc
D
1 =
⎡
⎢
⎢
⎢
⎣
0 4 1 1000 6
5 0 3 6 2
1 1 0 4 4
1000 2 10 0 9
1 1 2 7 0
⎤
⎥
⎥
⎥
⎦
P
1 =
⎡
⎢
⎢
⎢
⎣
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 1 4 5
⎤
⎥
⎥
⎥
⎦
II) On cherche maintenant le plus court chemin de i vers j passant éventuellement
par les sommets 1 et 2. Pour cela, on recommence les opérations précédentes en
comparant D
1
i,j et D
1
i,2 + D
1
2,j et en retenant le chemin le plus court. Voici les
améliorations possibles :
D
1
1,2 + D
1
2,4 = 4 + 6 = 10 < 1000 = D
1
1,4
D
1
4,2 + D
1
2,1 = 2 + 5 = 7 < 1000 = D
1
4,1
D
1
3,2 + D
1
2,5 = 1 + 2 = 3 < 4 = D
1
3,5
D
1
4,2 + D
1
2,1 = 2 + 5 = 7 < 1000 = D
1
4,1
D
1
4,2 + D
1
2,3 = 2 + 3 = 5 < 10 = D
1
4,3
D
1
4,2 + D
1
2,5 = 2 + 2 = 4 < 9 = D
1
4,5
84 – GRAPHES
notant P
0 le premier tableau, on a donc P
0
i,j = j et
P
0 =
⎡
⎢
⎢
⎢
⎣
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
⎤
⎥
⎥
⎥
⎦
Mais pour aller par exemple de 5 à 3, il vaut mieux passer par le sommet 1, car on
a D
0
5,1 + D
0
1,3 = 1 + 1 < 3 = D
0
5,3 . On va systématiquement comparer la durée d’un
trajet direct à celle d’un trajet passant par le sommet 1.
I) Formons un tableau D
1 contenant les durées des plus courts chemins passant
éventuellement par le sommet 1. On pose donc
D
1
i,j =
D
0
i,1 + D
0
1,j si D
0
i,1 + D
0
1,j < D
0
i,j
D
0
i,j
sinon
Si l’on a trouvé que le chemin (i, 1, j) est plus rapide que (i, j), il faut modifier
le tableau P en posant P i,j = 1. On définit donc un tableau P
1 tel que
P
1
i,j =
1 si D
0
i,1 + D
0
1,j < D
0
i,j
j sinon
Nous avons remarqué que le chemin (5, 1, 3) a un poids 2 inférieur au poids de
(5, 3), donc on pose D
1
5,3 = 2 et P
1
5,3 = 1. On vérifie qu’aucun autre chemin ne
peut être raccourci en passant par le sommet 1. Il vient donc
D
1 =
⎡
⎢
⎢
⎢
⎣
0 4 1 1000 6
5 0 3 6 2
1 1 0 4 4
1000 2 10 0 9
1 1 2 7 0
⎤
⎥
⎥
⎥
⎦
P
1 =
⎡
⎢
⎢
⎢
⎣
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 1 4 5
⎤
⎥
⎥
⎥
⎦
II) On cherche maintenant le plus court chemin de i vers j passant éventuellement
par les sommets 1 et 2. Pour cela, on recommence les opérations précédentes en
comparant D
1
i,j et D
1
i,2 + D
1
2,j et en retenant le chemin le plus court. Voici les
améliorations possibles :
D
1
1,2 + D
1
2,4 = 4 + 6 = 10 < 1000 = D
1
1,4
D
1
4,2 + D
1
2,1 = 2 + 5 = 7 < 1000 = D
1
4,1
D
1
3,2 + D
1
2,5 = 1 + 2 = 3 < 4 = D
1
3,5
D
1
4,2 + D
1
2,1 = 2 + 5 = 7 < 1000 = D
1
4,1
D
1
4,2 + D
1
2,3 = 2 + 3 = 5 < 10 = D
1
4,3
D
1
4,2 + D
1
2,5 = 2 + 2 = 4 < 9 = D
1
4,5
84 – GRAPHES