Algorithme de dijkstra

Merci !

Exercices
Classe(s) : Tle ES

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 :

&nbsp

A

B

C

D

E

F

G

H

A

&nbsp

15

5

15

&nbsp &nbsp &nbsp &nbsp

B

&nbsp &nbsp

20

&nbsp &nbsp &nbsp &nbsp &nbsp

C

&nbsp &nbsp &nbsp

12

&nbsp &nbsp

8

&nbsp

D

&nbsp &nbsp &nbsp &nbsp

25

20

&nbsp

28

E

&nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp

12

F

&nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp

10

G

&nbsp &nbsp &nbsp &nbsp

25

17

&nbsp &nbsp

H

&nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp &nbsp

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.