Introduction

Le problème du plus court chemin est un problème de la vie quotidienne qui peut être utilisé pour résoudre plusieurs situation de problème de décision.

Le problème du plus court chemin

2-1. Définition d'un graphe valué

Un graphe valué est un graphe aux arcs desquels on associe un nombre réel appelé longueur de l'arc.

On notera l(x,y) la longueur de l'arc (x,y).

2-2.Définition de la longueur d'un chemin

Etant donné un chemin d'un sommet x à un sommet y, on appelle longueur du chemin, la somme des longueurs des arcs qui le constituent.

Remarques

Le nombre réel associé à chaque arc peut représenter bien autre chose qu'une longueur au sens géométrique du terme. Par exemple, un temps, un coût, ... c'est pourquoi il peut être négatif.

Dans certains ouvrages, on utilise le mot "poids" plutôt que "longueur".

2-3.Définition du problème de plus court chemin

On peut s'intéresser à la recherche d'un plus court chemin dans un graphe :

1 - entre deux sommets donnés

2 - d'un sommet à tous les autres

3 - entre tous les couples de sommets

Le problème 2 n'est pas plus difficile à résoudre que le problème 1 et le problème 3 peut être résolu par application du problème 2 à tous les sommets.

On s'intéresse donc au problème 2.

2-4.Le problème du plus court chemin

Etant donné un graphe valué et s un sommet racine de ce graphe, trouver les plus courts chemins de ce sommet à tous les sommets du graphe.

Remarques

1 - Si le sommet de départ n’est pas racine du graphe, il existe des sommets qui ne seront pas accessibles, le problème du plus court chemin ne se pose alors que pour les sommets descendants de

s. Dans le graphe 1 ci-dessous, le sommet "c" n'est pas descendant du sommet s.

2 - Le graphe 2 présente une particularité qui va interdire de trouver une solution au problème du plus court chemin de s aux autres sommets du graphe.

Il existe dans ce graphe un circuit de longueur négative : le circuit a, b, c, a a pour longueur -1. On peut construire le chemin s, a, b, c, a, b, c, a, b... dont la longueur n'est pas bornée inférieurement.

On peut donc faire diminuer autant que l’on veut la longueur des chemins de s à a en empruntant une infinité de fois le circuit.

Un tel circuit est appelé "circuit absorbant".

Modélisation d’un problème de décision

Le problème :

Un problème de remplacement de matériel.

Vous devez décider de la politique de remplacement dans un parc automobile pour les années à venir.

Sachant que le coût d'entretien annuel d'un véhicule croît avec l'âge alors que son prix de revente diminue, vous vous demandez quand il est opportun de remplacer un véhicule par un neuf. Initialement vous disposez d'un véhicule neuf et il vous faut déterminer à quelle période il faudra le remplacer par un véhicule neuf.

On suppose être dans un environnement déterministe, c'est à dire que l'avenir est connu avec certitude, au moins en ce qui concerne l'évolution des coûts.

Ce deuxième problème donne lieu au même type de modélisation que celui de la recherche d’un itinéraire optimal, ce qui n’est pas évident a priori. Il est possible de le représenter par un problème de plus court chemin dans un graphe.

3-1.Analyse des décisions à prendre

Première modélisation

A la fin de chaque année, on examine ce qu'on fait du véhicule : on le garde ou on en change.

Deuxième modélisation

Chaque fois qu'on change de véhicule on décide a priori du nombre de périodes pendant lequel on le conservera.

Dans l'un et l'autre des cas, on connaît les conséquences en terme de coût (achat, entretien, revente).

Il s'agit de représenter la succession des décisions que l'on peut prendre.

Première modélisation

A la fin de la première année, la décision à prendre est de vendre ou de garder.

Il en est de même à la fin de chaque année.

Les différentes étapes sont représentées par un sommet.

Initialement on est au sommet 0 avec un véhicule neuf que l'on achète. Les conséquences financières sur l'année 1 dépendent du choix fait à la fin de l'année : si on vend le véhicule à la fin de l'année on se trouve dans la situation représentée par le sommet 1.1, si on le garde on est dans un autre état représenté par le sommet 1.2. Les 2 arcs (0, 1.1) et (0, 1.2) correspondent à ces deux décisions.

Pour l'année 2, quelque soit l'état en début d'année (1.1 ou 1.2) on aura 2 choix possibles à la fin de l'année : vendre ou garder.

Pour simplifier, on suppose qu'à la fin de l'année 4 on vend le véhicule, il n'y a donc qu'un seul arc issu d'un sommet numéroté 3.i. Quelle que soit la situation dans laquelle on se trouve à la fin de l'année 3, on vend à la fin de l'année 4.

Le graphe obtenu est une arborescence.

Un chemin du sommet 0 à un des sommets du niveau 4 représente une suite de décisions possibles.

Par exemple, le chemin qui passe par les sommets 0, 1.1, 2.2, 3.3 puis 4.4 correspond à un premier véhicule vendu à la fin de la première année, remplacé par un véhicule que l'on garde à la fin de la deuxième année pour le revendre à la fin de la troisième année pour le remplacer et le revendre à la fin de la 4ème année.

A chaque arc de ce graphe on associe un nombre réel correspondant aux conséquences financières de la décision pour l'année : on suppose pour simplifier que le prix d'acquisition PA ne varie pas et on connaît le coût d'entretien annuel CEi ainsi que la valeur de revente RVi d'un véhicule en fonction de son âge.

Par exemple, pour l'arc(0, 1.1) le coût total annuel est de PA + CE1 - RV1 : prix d'achat plus coût d'entretien la première année moins valeur de revente au bout d'un an.

Pour (0, 1.2) ce coût est : PA + CE1 puisqu'on ne revend pas.

Pour (1.2, 2.3) on a un coût de CE2 - RV2 puisqu'on utilise un véhicule pendant sa deuxième année et qu'on le revend à la fin.

On value ainsi tous les arcs. On notera la présence d'arcs qui peuvent être valués par un nombre négatif ; par exemple il est probable que CE2 - RV2 soit négatif

La recherche de la meilleure stratégie est modélisée par la recherche du plus court chemin dans ce graphe du sommet racine aux sommets de niveau 4.

Deuxième modélisation

Dans ce modèle, les décisions correspondent à la durée pendant laquelle on va garder un véhicule neuf.

Ceci est pertinent dans la mesure où lorsqu'on achète un nouveau véhicule peu importe l'âge de celui que l'on vient de vendre. Dans le graphe précédent, qu'on soit au sommet 2.1 ou au sommet 2.2 on aborde l'année 3 avec obligation d'acheter un véhicule après avoir vendu un véhicule d'un an d'âge dans le premier cas et de deux ans d'âge dans le second. Mais les décisions à prendre ultérieurement sont identiques.

Dans cette deuxième modélisation, on représente la suite des décisions par un graphe dont les sommets correspondent aux échéances i= 0, 1,..., 4.

Un arc du sommet i au sommet j indique l'acquisition d'un véhicule neuf à la date i et à sa revente à la date j.

Un chemin du sommet 0 au sommet 4 représente une suite de décisions.

Par exemple, le chemin correspondant à l’arc (0,1) suivi de l’arc (1,4) correspond à l'acquisition d'un véhicule pour 1 an suivi d'un deuxième véhicule gardé 3 ans.

Comme dans le modèle précédent, on associe à chaque arc l'évaluation des coûts consécutifs à la décision représentée : achat plus coût d'entretien pendant les années où le véhicule est conservé moins valeur de revente.

A l'arc (0, 1) on associe une longueur égale au prix d'acquisition additionné de l’entretien pendant 1 ans diminué de la valeur de revente au bout de 1 ans.

A l'arc (0, 4) qui correspond à l'acquisition d'un véhicule pour 4 ans, on associe le prix d'acquisition plus les coûts d'entretien pendant 4 ans diminué de la valeur de revente au bout de 4 ans.

La recherche de la meilleure stratégie est modélisée par la recherche du plus court chemin dans ce graphe du sommet 0 au sommet 4.

Résolution du problème du plus court chemin

4-1. Le cas où toutes les longueurs seraient positives

L'algorithme présenté est le très célèbre algorithme de Moore-Dijkstra.

Algorithme de MOORE-DIJKSTRA : énoncé

Les données

- un graphe dont les arcs sont valués par des nombres positifs,

- un sommet s racine du graphe à partir duquel on veut déterminer les plus courts chemins aux autres sommets,

- pour chaque sommet x de X, l’ensemble succ(x) de ses successeurs.

Initialisation

POUR tous les sommets x dans S Poser λ(x) = + ∞

Poser λ (s) = 0 E = Ø S = X

Corps de l’algorithme

TANTQUE il existe x dans S

FAIRE

Choisir dans S le sommet x avec λ (x) minimum

Mettre x dans E et l’enlever de S

POUR y ϵ succ(x) Ո S {on examine tous les successeurs de x qui sont dans S}

SI λ (y) > λ (x) + l(x,y) ALORS poser λ (y) = λ (x) + l(x,y) et père (y) = x

FINPOUR

FINFAIRE

FIN

Les résultats

Pour chaque sommet, λ (x) est égal à longueur d'un plus court chemin de s à x.

Père(y) = x indique que le sommet x est le prédécesseur de y sur le plus court chemin de s à y.

Exemple

Avant de démontrer la validité de cet algorithme mettons-le en oeuvre sur le graphe suivant :

La suite des calculs est résumée dans le tableau suivant :

Détermination des plus courts chemins

Les étiquettes fournissent la longueur des plus courts chemins de s aux différents sommets.

Pour déterminer les plus courts chemins eux-même, on remonte de "père" en père" : par exemple le sommet e a pour père d, qui a pour père b, qui a pour père c, qui a pour père s.

On en déduit que le plus court chemin de s à e est le chemin s c b d e de longueur 6.

Algorithme de Bellman

Données

- Un graphe valué sans circuit dont les sommets sont numérotés dans l'ordre du tri topologique

- Le sommet de départ s est racine du graphe et il est numéroté 1

- On connaît pour chaque sommet x ses prédécesseurs Pred(x).

Initialisation

Poser λ (1) = 0

Corps de l'algorithme

POUR x de 2 à n

FAIRE (on examine les prédécesseurs du sommet x)

Calculer λ (x) = min (λ (y) + l(y,x)) pour y dans Pred(x) (on parcourt les prédécesseurs de x, on calcule (λ (y) + l(y,x) et on prend le minimum de ces quantités)

POSER père(x) = y avec y prédécesseur y de x pour lequel ce minimum est atteint

FINFAIRE

FINPOUR

FIN

Résultats

λ (x) est égale à la longueur d'un plus court chemin de s à x.

Père(x) détermine le sommet prédécesseur de x sur le plus court chemin de s à x.

Algorithme de Ford-Bellman : Enoncé

Données

- un graphe valué dont les sommets sont numérotés de 1 à n,

- le sommet de départ s est racine du graphe ; il est numéroté 1,

- on connaît pour chaque sommet x ses prédécesseurs pred(x).

Initialisation

Poser λ (1) = 0

POUR x de 2 à n

Poser λ (x) = + ∞ et père(x) = vide

FINPOUR

Poser fin : = FAUX

Corps de l'algorithme

TANTQUE fin = FAUX

POUR x de 2 à n (on passe en revue tous les sommets)

FAIRE (on examine les prédécesseurs du sommet x)

Calculer min (λ (y) + l(y,x)) pour y dans Pred(x)

SI λ (x) > min (λ (y) + l(y,x)) ALORS

Poser λ (x) = min (λ (y) + l(y,x))

Poser père(x) = y avec y prédécesseur y de x pour lequel ce minimum est atteint

FINFAIRE

FINPOUR

SI aucune étiquette modifiée ALORS Poser fin : = VRAI

FINTANTQUE

FIN

Le problème du plus long chemin dans un graphe

Jusqu'à présent on ne s'est intéressé qu'à la détermination de plus courts chemins.

Certains problèmes sont modélisés par le problème de recherche de plus long chemin dans un graphe comme on le verra à la leçon suivante.

La modification des algorithmes précédents est généralement immédiate. Par exemple, dans l'algorithme de Bellman, il suffit de remplacer les min par max.

Dans le cas général, on modifie l'algorithme de Ford-Bellman de la manière suivante :

Calculer min (λ (y) + l(y, x)) pour y dans Pred(x)

SI λ (x) > min (λ (y) + l(y, x)) ALORS

Poser λ (x) = min (λ (y) + l(y, x))

est remplacé par :

Calculer max (λ (y) + l(y, x)) pour y dans Pred(x)

SI λ (x) < max (λ (y) + l(y, x)) ALORS

Poser λ (x) = min (λ (y) + l(y, x))

Mais attention s'il existe un circuit de longueur positive il n'y a pas de solution.