Problème du plus court chemin

On appelle problème du plus court chemin le problème suivant :
Etant donné un graphe G, associons à chaque arc u un nombre l(u)>=0 que nous appellerons « la longueur » de l’arc u.
Trouver un chemin élémentaire µ, allant d’un sommet a à un sommet b et tel que la longueur totale
l(µ)=∑_u=µ l(u)
Soit aussi petite que possible.
EXEMPLE
Considérons une carte de géographie, et cherchons la route la plus courte pour se rendre d’une localité a à une localité b. On tracera le graphe en remplaçant chaque route entre deux localités par deux arcs d’orientation opposées, et on résoudra le problème du plus court chemin en prenant pour li la longueur kilométrique de la route correspondant à l’arc i.
On peut aussi, de cette façon chercher le trajet le plus « rapide » ou le plus « économique », etc.…
Le problème du plus court chemin a été résolu de façons analogue par de nombreux auteurs ; le plus rapide moyens de calcul semble être l’algorithme suivant proposé par G.Dantzig :
Considérons sur le graphe le sommet de départ a=a₁, le sommet d’arrivée b=a_n et déterminons pour tout sommet x un nombre t(x), qui sera le « temps minimum d’arrivée en x ».
On opère par étapes :
1. Au début, on pose t(a₁)=0. Cette fonction est donc définie sur l’ensemble A₁= {a₁} ;
2. Supposons que à la k^ème étape on ait définit la fonction t sur un ensemble un ensemble A_k ={a₁,....,a_k} ; on associera à chaque sommet a_j ∈ a_k un sommet b_j <> A_k tq (a_j,b_j) ∈U et tq la longueur l(a_j,b_j) soit minimum ; puis on cherchera le sommet a_q∈ A_k tq
t(a_q)+l(a_q,b_q)=min_j{t(a_j)+l(a_j,b_j)}
On pose alors :
A_k+1=A_k U {b_q},
t(b_q)=t(a_q)+l(a_q,b_q).
Montrons que t(b_q)représente bien le temps minimum d’arrivée en b_q et que le plus court chemin pour aller en b_q passe par a_q ;en effet admettons que t(a_j) soit le temps minimum d’arrivées en a_j (pour tout a_j ∈A_k) ;tout chemin qui sort de A_k a une longueur>= t(a_q)+l(a_q,b_q)=t(b_q), et pour aller en b_q on est bien forcé de sortir de A_k,puisque a1∈A_k
On montera que chaque fois qu’on décide d’un sommet b_q, on peut sans inconvénients supprimer dans le graphe tous les arcs entrant dans b_q
Rq
Admettons qu’on puisse sans difficultés trouver le sommet b_j qu’on doit associer à a_j ∈ A_k ; pour décider du (k+1)ième sommet, il suffit alors de faire seulement K comparaisons : le nombre maximum de comparaisons à effectuer pour un graphe G de n sommet est :
1+2 + + (n-1)=1/2*n(n-1).
On peut aussi procéder avec un deuxième dessinateur qui simultanément, et de la même façon, déterminera des coefficients t(b_i) représentant la longueur des plus court chemin allant de b à c.