On pose donc
D
2 =
⎡
⎢
⎢
⎢
⎣
0 4 1 10 6
5 0 3 6 2
1 1 0 4 3
7 2 5 0 4
1 1 2 7 0
⎤
⎥
⎥
⎥
⎦
P
2 =
⎡
⎢
⎢
⎢
⎣
1 2 3 2 5
1 2 3 4 5
1 2 3 4 2
2 2 2 4 2
1 2 1 4 5
⎤
⎥
⎥
⎥
⎦
.
III) On compare maintenant D
2
i,j et D
2
i,3 + D
2
3,j . On a
D
2
1,3 + D
2
3,2 = 1 + 1 = 2 < 4 = D
2
1,2
D
2
1,3 + D
2
3,4 = 1 + 4 = 5 < 10 = D
2
1,4
D
2
2,3 + D
2
3,1 = 3 + 1 = 4 < 5 = D
2
2,1
D
2
4,3 + D
2
3,1 = 5 + 1 = 6 < 7 = D
2
4,1
D
2
5,3 + D
2
3,4 = 2 + 4 = 6 < 7 = D
2
5,4
et D
2
i,3 + D
2
3,j D
2
i,j dans les autres cas, donc
D
3 =
⎡
⎢
⎢
⎢
⎣
0 2 1 5 4
4 0 3 6 2
1 1 0 4 3
6 2 5 0 4
1 1 2 6 0
⎤
⎥
⎥
⎥
⎦
P
3 =
⎡
⎢
⎢
⎢
⎣
1 3 3 3 3
3 2 3 4 5
1 2 3 4 2
2 2 2 4 2
1 2 1 1 5
⎤
⎥
⎥
⎥
⎦
.
IV) Regardons si on peut raccourcir les chemins en les faisant passer par le sommet
4. On a D
3
i,4 + D
3
4,j D
3
i,j pour tous i, j , donc
D
4 = D
3
et
P
4 = P
3 .
V) Il reste à considérer le passage éventuel par le sommet 5. On a
D
4
2,5 + D
4
5,1 = 2 + 1 = 3 < 4 = D
4
2,1
D
4
4,5 + D
4
5,1 = 4 + 1 = 5 < 6 = D
4
4,1
et D
4
i,5 + D
4
5,j D
4
i,j dans les autres cas, d’où
D
5 =
⎡
⎢
⎢
⎢
⎣
0 2 1 5 4
3 0 3 6 2
1 1 0 4 3
5 2 5 0 4
1 1 2 6 0
⎤
⎥
⎥
⎥
⎦
P
5 =
⎡
⎢
⎢
⎢
⎣
1 3 3 3 3
5 2 3 4 5
1 2 3 4 2
2 2 2 4 2
1 2 1 1 5
⎤
⎥
⎥
⎥
⎦
.
Dans le tableau D
5 , le nombre D
5
i,j est la durée d’un plus court chemin de i vers
j . Pour trouver un tel chemin, on utilise le tableau P
5 , car P
5
i,j est le sommet qui
suit i dans un plus court chemin de i vers j .
Cherchons par exemple un plus court chemin de 4 vers 3 : on a P
5
4,3 = 2 donc le
chemin commence par les sommets 4,2 ; le sommet suivant est P
5
2,3 = 3, donc (4,2,3)
est un plus court chemin pour aller de 4 vers 3 ; sa durée est D
5
4,3 = 5.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 85