2016 chapitre 5 plus courts chemins le dehevat .pdf

---

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.13, et a été envoyé sur fichier-pdf.fr le 27/11/2016 à 11:41, depuis l'adresse IP 90.104.x.x. La présente page de téléchargement du fichier a été vue 192 fois.
Taille du document: 138 Ko (3 pages).
Confidentialité: fichier public

Aperçu du document

---

Algorithmes de plus courts chemins

1

Présentation
G = (S, A) est valué (ou
A
→
R
application ϕ
(i, j) 7→ ϕ (i, j)

Un graphe (par forcément orienté)

pondéré) lorsque chaque arête (arc)

poids. On dénit donc une

.

Il peut être pratique de prolonger cette application à
Si

c = a0 = i, ..., ap = j

est un chemin de

i

vers

j,

S×S

en posant

ϕ (i, j) = +∞

on appelle longueur de

c, ϕ (c) =

est muni d'un

(i, j) ∈
/ A.

lorsque

p−1
P

a = (i, j)

ϕ (ak , ak+1 ),

somme des poids des

k=0
arêtes traversées.
Le problème de plus court chemin entre
longueurs des chemins de

i

à

Remarque : si sur un chemin de
pas de plus court chemin de

i

et

j

est donc de trouver un chemin

c

tel que

ϕ (c)

soit minimale parmi les

j.
i

à

i à j il existe un circuit (i.e. un cycle) de longueur strictement négative alors il n'existe
j ; on emprunte autant de fois que l'on veut cette boucle pour avoir une longueur aussi

petite que l'on veut.
Dans la suite on n'envisage pas une telle situation et même on ne considère que des pondérations positives.
Proposition
Si il existe un chemin de

i

à

j

alors il existe un plus court chemin.

En eet, l'ensemble des longueurs des chemins de

i

vers

j

est une partie non vide de

R+ ,

minorée ; il admet une borne

inférieure. On établit que c'est un plus petit élément.

c est un chemin de i vers j , en supprimant les éventuels circuits on obtient un chemin élémentaire, de longueur inférieure.
c il existe un chemin élémentaire de longueur inférieure. Or l'ensemble des chemins élémentaires de i
vers j est ni (le graphe est constitué d'un nombre ni de sommets), et par suite l'ensemble de leurs longueurs est lui
Si

Pour tout chemin
aussi ni.

La recherche d'un plus court chemin s'appuie sur le lemme suivant, dit lemme d'optimalité :

c = a0 = i, ..., ap = j est un plus court chemin de i vers j , alors pour tout k ∈ [[0, p]],
c1 = a0 = i, ..., ak est un plus court chemin de i à ak et c2 = ak , .., ap = j est un plus court

Si

chemin de

ak

à

j.

Preuve :
Soit

c01

ϕ (c01 )

un chemin de

a0

à

ak .

La concaténation de

+ ϕ (c2 ) > ϕ (c) = ϕ (c1 ) + ϕ (c2 )

c01

et de

par minimalité de

c2

c.

est un chemin de

i

à

j

de longueur

On en déduit immédiatement que

Les problèmes de plus courts chemins que l'on peut étudier sont :
1. les plus courts chemins d'un sommet

i

à tous les autres

2. les plus courts chemins entre tous les sommets et un sommet
3. les plus courts chemins entre tous les couples de sommets.

1

j

ϕ (c01 ) > ϕ (c1 )

2

Algorithme de Floyd-Warshall

2.1

Principe de l'algorithme

La fonction de valuation est donnée par l'intermédiaire d'une matrice
Si

(i, j) ∈ A, wij = ϕ (i, j),

sinon

W = (wij )06i,j6n−1

où

n = |S|.

wi,j = +∞.

On prolonge l'addition et la relation d'ordre à

R ∪ {+∞}

par : pour tout réel

x

x + (+∞) = (+∞) + x = +∞, (+∞) + (+∞) = +∞
x 6 +∞, +∞ 6 +∞
Dans un chemin

c = a0 = i, ..., ap = j ,

On dénit la suite de matrices

1.

D(0) = W

2.

dij

(k+1)

nous appellerons sommets intermédiaires les sommets



(k)

D(k) = dij



ak , 1 6 k 6 p − 1.

, où



(k) (k)
(k)
= min dij , dik + dkj

Proposition :

i, j, k ,

Pour tout

.

si il existe un chemin de
sinon,

i

à

j

de sommets intermédiaires

(k)

< k , dij

est la longueur d'un tel plus court chemin

(k)

dij = +∞

Le résultat se prouve par récurrence sur

D(n)

La matrice

k.

est la matrice des longeurs des plus courts chemins où les sommets intermédiaires sont dans

[[0, n − 1]],

donc les matrices des longueurs des plus courts chemins.
On remarque que le graphe est connexe si et seulement si pour tout

(k+1)

D(k+1) on détermine les n2 coecients dij
k pour parvenir à D(n) . Cet algorithme est donc

Pour calculer la matrice
et on boucle sur

(n)

(i, j) ∈ S 2 , dij ∈ R.
en temps constant (une addition et une comparaison),

de complexité

O n3




.

Ne nous contentons pas des distances, déterminons le chemin.
Si

(k)

(k)

(k)

dij > dik + dkj

, le sommet qui précède

est le sommet qui précède
Sinon (

<k

(k)

(k)

(k)

dij 6 dik + dkj

j

j

dans un plus court chemin de

) alors le sommet qui précède

est aussi le sommet qui précède

j

à

j

de sommets intermédiaires

<

j

vers

j

(k)
k , pij

P

= −1

vers

(0)
pij

et


=

(
=

=



i
−1

(k)

pkj
(k)
pij

j

de sommets intermédiaires

dans un plus court chemin de

(k)
pij



i

vers

(k)
où pij

j

si
si

∈ [[0, k − 1]]

(i, j) ∈ A
(i, j) ∈
/A
(k)

(k)

(k)

dij > dik + dkj
(k)
(k)
(k)
dij 6 dik + dkj

si
si

2

i

vers

j

< k+1

< k.
de sommets intermédiaires

de sommets intermédiaires

sinon.

Pour cela

(k+1)
pij



(k)

i

de sommets intermédiaires

dans un plus court chemin de

On dénit donc parallèlement la suite de matrices

i

k

dans un plus court chemin de

< k + 1.

s'il existe un plus court chemin de

2.2

Traduction

On se contente de pondérations entières ; l'abscence d'arête entre les sommets

i

et

j

se traduit par un poids inni. On

dénit un type regroupant les entiers et l'inni, on prolonge la relation < et l'addition à ces entiers étendus .

type entier_etendu = infini | N of int;;
let inf_strict x y = match x,y with
| infini, infini -> false
| infini, N(_) -> false
| N(_), infini -> true
| N(p),N(q) -> p<q;;
let somme x y = match x,y with
| infini, infini -> infini
| infini, N(_) -> infini
| N(_), infini -> infini
| N(p),N(q) -> N(p+q);;

Une fonction itération, permet de calculer les matrices
et

P (k) .

Pour nir, la fonction

floyd,





(k+1)
(k+1)
(k+1)
(k)
D(k+1) = di,j
et P
= pi,j
à partir des matrices D

à partir de la matrice de pondération, calcule la matrice des plus-courts chemins et

des prédecesseurs dans un plus court-chemin.

let iteration d p k n =
for i = 0 to (n-1) do
for j = 0 to (n-1) do
let s = somme d.(i).(k) d.(k).(j) in
if inf_strict s d.(i).(j) then begin
d.(i).(j) <- s;
p.(i).(j) <- p.(k).(j)
end;
done;
done;;
let floyd poids = (*calcule les plus_courts chemins et les prédecesseurs
let n = vect_length poids in
let d = make_matrix n n infini and p = make_matrix n n (-1) in
for i = 0 to (n-1) do
for j = 0 to (n-1) do
d.(i).(j) <- poids.(i).(j);
if inf_strict d.(i).(j) infini then p.(i).(j) <- i
done; done;
for k = 0 to (n-1) do iteration d p k n done;

dans un tel chemin *)

(d,p);;

Exercice : écrire une fonction qui prend en entrée la matrice des prédecesseurs, deux sommets
des sommets dans un plus court chemin de

i

vers

j.

3

i

et

j,

et qui calcule la liste



Sur le même sujet..

---