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 :

 

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.