Existence De : PAS DE PLUS COURT CHEMIN 1 3 4 5 2 6 7 8 9 2 6 6
1 3 2 -6 35
Page 9
Graphe des plus courts chemins 041 325 6 3 2 5 2 13 2 4 1
2
Page 10
En rouge : x est la longueur dun plus court chemin du sommet
i=0 au sommet x 041 325 6 3 2 5 2 13 2 4 1 2 0358 6 7
Page 11
Graphe des plus courts chemins Comment caractriser, grce aux
valeurs de les arcs qui font partie de plus courts chemins dans
(E,, l ) partir de i ? 041 325 6 3 2 5 2 13 2 4 1 2 0358 6 7
Page 12
Graphe des plus courts chemins u = (x,y) est dans un plus court
chemin dans (E,, l ) partir de i si et seulement si : y x l (u) 041
325 6 3 2 5 2 13 2 4 1 2 0358 6 7
Page 13
Graphe des plus courts chemins u = (x,y) est dans un plus court
chemin dans (E,, l ) partir de i si et seulement si : y x l (u) 041
325 6 3 2 5 2 13 2 4 1 2 0358 6 7
Page 14
Graphe des plus courts chemins 041 325 6 3 2 5 2 13 2 4 1 2
0358 6 7 c est un plus court chemin dans (E,, l ) partir de i si et
seulement si : c est un chemin dans (E, )
Page 15
Arborescence des plus courts chemins (E,A) est une arborescence
des plus courts chemins pour (E,, l ) de racine i si : (E,A) est
une arborescence de racine i, et E = {x E, x } (E,A) est un
sous-graphe du graphe des plus courts chemins pour (E,, l ) 041 35
6
Page 16
Arborescence des plus courts chemins = APMin ? 14 32 1 1 1
2
Page 17
14 32 1 1 1 2 APCC (relative au sommet 1)
Page 18
Arborescence des plus courts chemins = APMin ? 14 32 1 1 1 2
APMin
Page 19
Trouver un plus court chemin de i=0 d=6 041 325 6 3 2 5 2 13 2
4 1 2 0358 6 7
Page 20
Trouver un plus court chemin de i=0 d=6 041 325 6 3 2 5 2 13 2
4 1 2 0358 6 7 Partir de i ?
Page 21
041 325 6 3 2 5 2 13 2 4 1 2 0358 6 7 Trouver un plus court
chemin de i=0 d=6 Partir de i ?
Page 22
Trouver un plus court chemin de i=0 d=6 041 325 6 3 2 5 2 13 2
4 1 2 0358 6 7 Partir de d !
Page 23
Trouver un plus court chemin de i=0 d=6 041 325 6 3 2 5 2 13 2
4 1 2 0358 6 7 Partir de d !
Page 24
Trouver un plus court chemin de i=0 d=6 041 325 6 3 2 5 2 13 2
4 1 2 0358 6 7 Partir de d !
Page 25
Trouver un plus court chemin de i=0 d=6 041 325 6 3 2 5 2 13 2
4 1 2 0358 6 7 Partir de d !
Page 26
Trouver un plus court chemin de i=0 d=6 x = d ; C = (x) Tant
que x != i Soit y (x) tel que y x l ((y,x)) x = y ; C = x + C 041
325 6 3 2 5 2 13 2 4 1 2 0358 6 7
Page 27
Trouver un plus court chemin de i d x = d ; C = (x) Tant que x
!= i Soit y (x) tel que y x l ((y,x)) x = y ; C = x + C 041 325 6 3
2 5 2 13 2 4 1 2 0358 6 7
Page 28
Trouver un plus court chemin de i d x = d ; C = (x) Tant que x
!= i Soit y (x) tel que y x l ((y,x)) x = y ; C = x + C 041 325 6 3
2 5 2 13 2 4 1 2 0358 6 7
Page 29
Trouver un plus court chemin de i d x = d ; C = (x) Tant que x
!= i Soit y (x) tel que y x l ((y,x)) x = y ; C = x + C 041 325 6 3
2 5 2 13 2 4 1 2 0358 6 7
Page 30
Trouver un plus court chemin de i d x = d ; C = (x) Tant que x
!= i Soit y (x) tel que y x l ((y,x)) x = y ; C = x + C 041 325 6 3
2 5 2 13 2 4 1 2 0358 6 7
Page 31
Trouver un plus court chemin de i d x = d ; C = (x) Tant que x
!= i Soit y (x) tel que y x l ((y,x)) x = y ; C = x + C 041 325 6 3
2 5 2 13 2 4 1 2 0358 6 7
Page 32
Algorithme de Bellman
Page 33
3 1 2 5 8 1 7 2 6 4 4 2 -2 2 3 2 Algorithme de Bellman :
exemple i =
