L'algorithm de Bellman-Ford

Exercice 1 – L’algorithme de Bellman-Ford

L’algorithme de Bellman-Ford r ́sout le probl`me des plus courts chemins avec origine unique dans

e

e

́

le cas le plus g ́n ́ral o` les poids des arcs peuvent avoir des valeurs n ́gatives. Etant donn ́ un

e e

u

e

e

graphe orient ́ pond ́r ́ G = (V, E), de fonction de poids w, et une origine s, l’algorithme retourne

e

ee

une valeur bool ́enne indiquant s’il existe un circuit de poids n ́gatif accessible depuis s. S’il n’en

e

e

existe pas, l’algorithme donne les plus courts chemins ainsi que leurs poids.

Les notations sont les suivantes: π[v] contient le pr ́d ́cesseur de v sur le chemin (NIL s’il n’y en a

e e

pas), δ(u, v) est le poids du plus court chemin de u vers v (∞ s’il n’existe pas), d[v] est une variable

qui est une borne sup ́rieure du poids du plus court chemin de s vers v (cf. question 4).

e

Bellman-Ford(G, w, s)

• Initialisation:

– pour chaque sommet v ∈ V faire: d[v] ← ∞, π[v] ← NIL

– d[s] ← 0.

• pour i de 1 ` |V | − 1 faire:

a

– pour chaque arc (u, v) ∈ E faire: (relˆchement de l’arc (u, v))

a

∗ si d[v] > d[u] + w(u, v)

∗

alors d[v] ← d[u] + w(u, v), π[v] ← u

• pour chaque arc (u, v) ∈ E faire:

– si d[v] > d[u] + w(u, v) alors retourner FAUX

• retourner VRAI.

1 - On consid`re le graphe ci-dessous. Faire tourner l’algorithme en prenant comme source le

e

sommet z. Mˆme question en changeant le poids de l’arc (y, v) ` 4.

e

a

5

u

6

-3

8

z

7

v

-2

7

2

-4

x

9

y

2 - Quelle est la complexit ́ de cet algorithme?

e

3 - Montrer qu’apr`s le relˆchement de l’arc (u, v), d[v] ≤ d[u] + w(u, v).

e

a

4 - Montrer que d[v] ≥ δ(s, v) pour tout sommet v ` tout instant de l’algorithme. Montrer que

a

lorsque d[v] a atteint sa borne inf ́rieure δ(s, v), il n’est plus jamais modifi ́.

e

e

5 - Consid ́rons un plus court chemin (s, . . . , u, v) pour deux sommets u et v donn ́s. Montrer que

e

e

si d[u] = δ(s, u) ` un moment pr ́c ́dent l’appel du relˆchement de (u, v) dans l’algorithme, alors

a

e e

a

on a toujours d[v] = δ(s, v) apr`s l’appel.

e

6 - Montrer que, si G ne contient aucun circuit de poids n ́gatif accessible depuis s, alors, ` la fin

e

a

de l’ex ́cution de l’algorithme, d[v] = δ(s, v) pour tout sommet v accessible depuis s.

e

7 - Montrer que pour chaque sommet v, il existe un chemin de s vers v si et seulement si Bellman-

Ford se termine avec d[v] < ∞.

Nous pouvons ` pr ́sent d ́montrer la validit ́ de l’algorithme.

a e

e

e

8 - Montrer que si G ne contient aucun circuit de poids n ́gatif accessible depuis s, alors l’algorithme

e

retourne VRAI, on a d[v] = δ(s, v) pour tous les sommets v ∈ V , et le sous-graphe des sommets

v dont π(v) = NIL et des arcs (π(v), v) est une arborescence des plus courts chemins de racine s.

Montrer que si G contient un circuit de poids n ́gatif accessible ` partir de s, l’algorithme renvoie

e

a

FAUX (on pourra raisonner par l’absurde).

Exercice 2 – L’algorithme de Johnson

On s’int ́resse maintenant au probl`me consistant ` calculer les plus courts chemins pour tout

e

e

a

couple

...