Cheminement.

1         Objet.

Il s'agit de trouver le plus court chemin entre deux sommets d'un graphe valué. On peut penser à une recherche d'itinéraire, mais on peut aussi remplacer "plus court" par "moins coûteux", ou par "plus rentable", etc..

2        Généralités.

2.1        Rappels:

2.1.1        Graphe valué

Soit G = (X, U) un graphe orienté. Il est dit valué si à chaque arc u de U est associée une valeur numérique v(u).

Cette valeur s'interprétera souvent comme une distance, un coût unitaire de transport. Dans ce cas un gain, (une subvention) aura une valeur négative.

2.1.2        Longueur d’un chemin

La longueur d'un chemin joignant 2 sommets du graphe valué G est la somme algébrique des valeurs des arcs de ce chemin.

2.1.3        Racine d'un graphe

Le sommet a de X est une racine du graphe G = (X,U) si, pour tout sommet x dans X, il existe un chemin joignant le sommet a au sommet x (G est donc connexe).

2.1.4        Arborescence de racine a

Une arborescence de racine a est un graphe partiel A de G tel que pour tout x sommet de G il existe un unique chemin dans A allant de a à x.

3        Problème du plus court chemin.

Soit a la racine d'un graphe valué connexe. On considère deux problèmes à priori distincts mais dont la solution relève des mêmes algorithmes:

1) Trouver le plus court chemin joignant un sommet a à un sommet x.

2) Trouver, pour chaque sommet x du graphe G = (X,U), le plus court chemin joignant le sommet a au sommet x.

3.1.1        Remarques

1) En associant à chaque sommet x un seul plus court chemin de a à x (même s'il en existe plusieurs), on construit ainsi une arborescence dite des plus courts chemins issus de a.

2) Les mêmes algorithmes conduisent à la recherche des plus longs chemins.

3.1.2        Potentiel

Soit A une arborescence de racine a, pour tout sommet x de G, on pose p(x) la longueur de l’unique chemin de A reliant a à x.

3.2       Théorème

Soit a une racine d'un graphe G = (X,U), p une fonction réelle sur X. Une condition nécessaire et suffisante pour que p représente les plus courtes distances entre a et les sommets de X est que:

1)      p (a) = 0.

2)     Pour tout arc u = (x, y) on ait

p (y) - p (x) <= v(x, y)    [R]

3) Le graphe partiel constitué des arcs (x, y) de U tels que p (y) - p (x) = v(x, y)   admet aussi a comme racine.

(On peut en déduire une arborescence "des plus courts chemins").

 

3.2.1        Démonstration de la condition nécessaire:

Soit C un plus court chemin joignant a au sommet x, le potentiel p (x) représente alors la longueur de ce chemin C. Si on ajoute l'arc (x, y) à ce chemin, on obtient un chemin (a,y) de longueur p(x) + v(x, y) qui ne peut être que supérieur (ou égal) à  p(y) qui est la plus courte distance de a à y.

Donc, pour tout arc (x, y):

               p (y)  <= p(x) + v(x, y)  ce qui prouve [R]

Enfin soit x un sommet du graphe et C un plus court chemin de a à x (longueur de C =   p(x)), alors si

(y, z) est un arc du chemin optimal (a, x), on a p (z) - p (y) = v(y, z)

En effet si p (z) - p (y) < v(y, z), on pourrait améliorer le chemin optimal de a à z donc de a à x.

 

On en déduit la propriété suivante qui est importante par ses conséquences (programmation dynamique)

3.2.2        Propriété

Tout sous chemin d'un chemin optimal et lui même optimal.

4        ALGORITHMES de plus court chemin.

Il existe plusieurs algorithmes de recherche du plus court chemin d'un sommet à un autre. Nous en donnons deux principaux qui diffèrent par leurs conditions d'application.

4.1        Algorithme de BELLMAN.

4.1.1        Conditions:

Graphe connexe sans circuit, et a racine du graphe.

4.1.2        Algorithme:

On pose p(a) = 0.

Tant qu'il existe au moins un sommet y dont le potentiel n'est pas encore calculé et dont on a calculé le potentiel p(x) pour tous les antécédents x, on calcule:

p (y) = p (xo) + v(xo, y) = Min { p (x) + v(x, y) / x antécédent de y } et on note:

A(y) = xo

l'antécédent correspondant à la longueur minimum

 

Le graphe étant sans circuit, il est toujours possible de calculer le potentiel d'au moins un sommet supplémentaire, jusqu'à ce que tous les sommets soient munis d'un potentiel.

L'ensemble des arcs (A(x),x) forme un graphe partiel qui est une arborescence de racine a.

 


Exemple: On considère le graphe

et on cherche l'arborescence des plus courts chemin issus de a.

La recherche des potentiel conduit à:


 


Interprétation en terme de transport. Si la valeur des arcs est interprétée comme le coût de transport unitaire d’un certain bien du sommet de départ au sommet d’arrivée, le problème du plus court chemin est celui de l’itinéraire le plus économique.

4.1.1        Recherche des plus long chemin:

On peut reprendre tout ce qui a été dit en remplacant la relation ® du Théorème 3.2 par

p (y) - p (x) >= v(x, y)

Pour calculer les plus longs chemins issus du sommet A il suffit de remplacer Min par Max dans l'algorithme de Bellman

4.2       Niveaux dans un graphe sans circuit.

Soit G un graphe connexe sans circuit avec une racine a. (S'il existe plusieurs racines, on peut ajouter un sommet artificiel comme antécédent à celles ci pour avoir une racine unique).

On associe à chaque arc la valeur 1. Le potentiel des sommets calculés en cherchant les plus longs chemins fournissent un  moyen de classer les sommets. Il est alors appelé rang ou niveau du sommet.


La méthode des niveaux donne un outil commode pour la représentation des graphes sans circuit.

 



Graphe obtenu en classant les sommets par niveaux:

 


4.3       Programmation dynamique:

4.3.1        Principe:

Permet de prendre une décision se présentant comme une séquence de choix interdépendants.

Le problème est représenté comme un graphe où les sommets correspondent aux états possibles du système au niveau de la niéme décision, et les arcs décrivent les "transitions" possibles du passage d'un état possible d'une décision à un état possible de la décision suivante, les valeurs sur les arcs sont les coûts associés à ces transitions.

4.3.2        Exemple

Une entreprise doit lancer la fabrication d'un nouveau produit. Compte tenu des résultats d'une étude marketing, le volume des ventes (qui doit aller en s'accroissant) nécessitera l'achat de 4 machines identiques à la fin de l'année.

Cet investissement doit être réaliser sur la totalité de l'année en répartissant les achats successifs sur les trimestres. On sait que:

Le nombre initial de machines est nul et doit être de 4 à la fin du quatrième trimestre.

Les demandes nécessitent au minimum 1, puis 2, puis 3 et enfin 4 machines pour les quatre trimestres considérés

Les achats de machines ont lieu en début de trimestre

Les prix d'achat varient selon les trimestres et les quantités achetées selon le tableau suivant:

Nb de machines

Achetées

1er trimestre

(K€)

2nd trimestre

(K€)

3ème trimestre

(K€)

4ème trimestre

(K€)

1

2

3

4

60

110

170

220

80

150

230

300

70

120

190

240

40

70

100

130

 

Question: Quel est le plan d'achat le plus économique ?

Corrigé: On prendra comme sommets le nombre cumulé de machines achetées jusqu'au Nième trimestre (inclus):.

Point de départ:

A0 (départ pas de machine),

Fin premier trimestre:

B1 : On doit disposer d'un serveur au moins 1er trimestre (donc 1 acheté), mais on peut aussi en acheter tout de suite 2 (B2), ou 3 (B3) ou 4 (B4), anticipant les achats ultérieurs.

Fin second trimestre:

C2: On doit disposer de 2 serveurs au 2ème trimestre

etc….

 

Notons que B0 n'a pas de sens compte tenu de la demande, de même C0 et C1, etc…

 

On passe de A0 en B1 en achetant une machine, de B1 à C2 en achetant encore une machine etc..

On recherche le plus court chemin de A0 à E4. D'où la politique optimale: Achat de 3 machines au trimestre 1 et d'une machine au dernier trimestre.

4.4       Le problème des circuits: Algorithme de FORD:

4.4.1        Exemple

On recherche les plus courts chemins issus de a dans le graphe ci-dessous

 

 

 

 

 

 

 

 

 

 

On peut noter que chaque circuit bè cè dè b est de valeur –1 et provoque une diminution de 1 du potentiel (s'il existait) de ces 3 sommets. On dira que le circuit ci – dessus est absorbant pour un problème de plus court chemin. Le problème est donc sans solution.

 

Par contre on peut trouver une solution au problème du plus long chemin.

On a une situation analogue pour un problème de plus long chemin et un circuit de valeur positive.

 

Le problème des plus courts/longs chemins n'a pas de solution en présence de circuits absorbants.

4.4.2        Condition d'utilisation de l'algorithme de Ford:

Pas de circuits absorbants.

4.4.3        Algorithme de Ford (recherche de plus court chemin):

Soit a la racine du graphe G(X,U).

On pose

p(a) = 0 et

p(x) = +¥ pour tout x dans X, x différent de a.

et on pose comme règle de calcul que pour tout nombre fini v,  ¥ + v égal +¥.

 

On classe les sommets en mettant a en premier puis les autres sommets dans un ordre quelconque.

On effectuera la boucle suivante tant qu'une des valeurs p sera modifiée dans la boucle précédente

Pour chaque sommet x autre que a:

            Pour chaque sommet y antécédent de x:

                        si p (x) > p(y) + v(x, y)  poser p (x) = p(y) + v(x, y)

4.4.4        Algorithme "manuel" sur la recherche des plus long chemin dans l’exemple:

Dans ce cas l'algorithme se formule ainsi:

On pose

p(a) = 0 et

p(x) = -¥ pour tout x dans X, x différent de a.

et on pose comme règle de calcul que pour tout nombre fini v,  -¥ + v égal -¥.

On classe les sommets en mettant a en premier puis les autres sommets dans un ordre quelconque.

On effectuera la boucle suivante tant qu'une des valeurs p sera modifiée dans la boucle précédente

Pour chaque sommet x autre que a:

                        Pour chaque sommet y antécédent de x:

                                   si p (x) < p(y) + v(x, y)  poser p (x) = p(y) + v(x, y)

 

arcs

arcs antécédents

p initial

Boucle 1

Boucle 2

Boucle 3

a

 

0

0

0

0

b

ab=2

bd=1

-¥

abè0+2

dbè -¥+1

p(b) = 2

abè0+2

dbè 2+1

p(b) = 3

abè0+2

dbè 2+1

p(b) = 3

c

ac=5

bc=1

-¥

acè0+5

bcè2+1

 p(c) = 5

acè0+5

bcè3+1

 p(c) = 5

acè0+5

bcè3+1

 p(c) = 5

d

cd=-3

-¥

cdè5-3

p(d) = 2

cdè5-3

p(d) = 2

cdè5-3

p(d) = 2

5        Exemple.

5.1.1        Exemple

Déterminer le plus long chemin allant du sommet a au sommet g dans le graphe suivant:

 


 

 


Sommets

 

Départ

Boucle 1

Boucle 2

Boucle 3

a

 

0

0

0

0

b

ab=7

cb=-3

-¥

7

7

7

c

ac=8

ec=0

-¥

8

10

10

d

bd=8

ed=4

gd=-2

-¥

15

16

17

e

be=3

-¥

10

10

10

f

cf=1

ef=0

-¥

10

11

11

g

eg=5

fg=8

-¥

18

19

19

 


On vérifie alors que cette solution est bien optimale: 

 


pour tous les arcs (x, y), on a bien p(y) - p(x) – v(x, y) > 0.

 

Remarque:

1)     Pour des "petits graphes", il est également possible de raisonner directement sur le graphe.

2)     Il est également possible d'ignorer certains des arcs créant des cycles pour se ramener à l'algorithme de Bellman, puis de réinjecter ces arcs un à un en utilisant la même méthode.