Une société fait appel à des services de transport pour effectuer ses livraisons d’une ville A à une ville H. Les liaisons possibles de ville à ville et les coûts sont traduits dans le tableau suivant :
|   |
A |
B |
C |
D |
E |
F |
G |
H |
|
A |
  |
15 |
5 |
15 |
  |   |   |   |
|
B |
  |   |
20 |
  |   |   |   |   |
|
C |
  |   |   |
12 |
  |   |
8 |
  |
|
D |
  |   |   |   |
25 |
20 |
  |
28 |
|
E |
  |   |   |   |   |   |   |
12 |
|
F |
  |   |   |   |   |   |   |
10 |
|
G |
  |   |   |   |
25 |
17 |
  |   |
|
H |
  |   |   |   |   |   |   |   |
1. Dessiner le graphe orienté correspondant.
Par exemple, on orientera l’arête A-B de A vers B, pondérée par 15.
2. Déterminer le coût minimal d’une livraison de A vers H à l’aide de l’algorithme de Dijkstra.
Revoir le savoir-faire 5.
