École Supérieure Privée d’Ingénierie et de Technologies
Graphes & Applications
Série d’exercices 2 : Recherche de plus court chemin
Niveau : 4ème année Année Universitaire : 2024-2025
Exercice 1
On considère le réseau social décrit ci-dessous :
A B C
D E
F G H
1. Déterminer le parcours de A vers H composé d’un nombre minimal de liens.
2. Déterminer le parcours de A vers H composé d’un nombre minimal de sommets.
Exercice 2
Une société offshore a besoin d’une voiture pour ses 5 années d’activités. Au début de sa première
année (t = 0), la société achète une voiture neuve et au début de chaque année t, elle a la possibilité
soit de la garder durant l’année [t, t + 1[ ou de la vendre au prix v(i), où i est l’âge de la voiture au
moment de la vente, et acheter une nouvelle au prix p(t). À la fin de sa dernière année d’activités,
la société revendra sa voiture sans en racheter d’autre. Le coût annuel de maintenance d’une voiture
dépend de son âge i au début de chaque année t, et il est désigné par m(i). Les valeurs p(t), v(i) et
m(i) étant supposées actualisées à la date t. L’objectif est de déterminer une politique qui permet
à la société de bénéficier d’une voiture durant les 5 années de ses activités avec un coût global
minimal.
1. Montrer que l’objectif revient à déterminer un plus court chemin entre deux sommets parti-
culiers dans un graphe qu’on précisera.
2. Résoudre ce problème avec les données suivantes :
Age de la voiture i (ans) /Année t 0 1 2 3 4 5
Prix d’achat p(t) 22000 24000 25000 25000 26000 -
Prix de vente v(i) - 19000 16000 12000 9000 5000
Coût annuel de maintenance m(i) 2000 3000 5000 6000 8000 -
1
Exercice 3
Déterminer le plus court chemin entre le sommet (1) et tout autre sommet du graphe représenté
ci-dessous.
2
5
1 −1
2 3
4 −2
9 4 6
−4
8 6 −5
6 3 −3 5
Exercice 4 3
On considère le réseau routier décrit ci-dessous :
3 1
B 2 G
0 8 4 2 1 0
A 3 D 7 E 3 H
3 2 3 2 5
C 8 F
1 4
Dans ce graphe, les arcs représentent des tronçons de route à sens unique et les poids qui leurs
sont associés représentent les temps de passage. Les arêtes représentent des tronçons de route à
double sens et les poids qui leurs sont associés représentent les temps de passage (dans les deux
sens). Les sommets représentent les carrefours du réseau routier et les poids qui leurs sont associés
représentent les temps d’arrêt. L’objectif est de déterminer le parcours de durée minimale de A
vers H.
1. Montrer que le problème revient à déterminer le plus court chemin dans un graphe orienté
que l’on déterminera.
2. Déterminer alors le plus court chemin de A vers H.
Exercice 5
Appliquer l’algorithme de Floyd sur les deux graphes suivants.
1 2 2 1 2 2
−1 3 −2 0 −1 3 2 −1
−1 1
4 3 4 3
3 −1
