Licence d'Informatique
Module L1S - Option O1
2002-2003

TD 3

Plus courts chemins


1.
Faire tourner l'algorithme de Dijkstra sur le graphe orienté pondéré suivant :

 

 
 

2.
Trouver un graphe orienté pondéré (avec certains poids négatifs) sur lequel l'algorithme de Dijkstra ne fournit pas une solution correcte.
3.
Faire tourner l'algorithme du rang, puis celui du tri topologique, sur le graphe suivant :

 

 
 

4.
Faire tourner l'algorithme de Bellman sur le graphe orienté pondéré suivant :

 

 
 

5.
L'algorithme général de Ford-Dantzig, pour calculer les plus courts chemins à partir d'un sommet $s\in V(G)$ dans un graphe orienté pondéré (G,c), peut se décrire comme suit :
(0)
Faire tourner l'algorithme de Dijkstra sur (G,c) ; en déduire une arborescence T dans A(G) et une fonction $\lambda$ sur V(G) ;
(1)
Tant qu'il existe $a=(x,y)\in A(G)-T$ tel que $\lambda(y)>\lambda (x)+c(x,y)$, ajouter l'arc a à T ; si un circuit est créé, il est absorbant et STOP, sinon on supprime de T l'autre arc d'extrémité finale y et on diminue de $\lambda (y)-\lambda(x)-c(x,y)$ la fonction $\lambda$ sur y et tous ses descendants dans T ;

 
Faire tourner l'algorithme de Ford-Dantzig sur le graphe orienté pondéré suivant :

 

 
 


Bruno Beauquier