Skip to content

Plus court chemin

Objectifs

  • Définir le problème du plus court chemin
  • Appliquer l'algorithme de Dijkstra

Cours

Appuyez sur F pour passer en plein écran.
Version plein écran ou imprimable.

Exercices

Exercice : Dijkstra

Appliquer l'algorithme de Dijkstra sur les graphes suivants :

Chemin : A → G

Correction
ABCDEFG
0
A-62
C-6-7
B---7
D----1722
E-----2219

Chemin : A → C → D → E → G avec une distance de 19

Chemin : A → F

Correction
ABCDEF
0
A-44
B--4
C---7510
E---7-8
F-----8

ou

ABCDEF
0
A-44
C-4-7510
B---7510
E---7-8
F-----8

Chemin : A → C → E → F avec une distance de 8

Chemin : D → I

Correction
ABCDEFGHI
0
D3-75
A-10-45
E-6--557
F-68---577
G-68----77
B--7----77
C-------77
H--------7

Chemin : D → A → E → F → I avec une distance de 7

Chemin : A → J

Correction
ABCDEFGHIJ
0
A-85217173
B--217173165
F--217173-415
E--217--415675
C-----403320415675
H---503--403-415487
G---503----415487
I---503-----487

Chemin : A → C → H → J avec une distance de 487 km

Sources