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.
