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
A | B | C | D | E | F | G | |
---|---|---|---|---|---|---|---|
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
A | - | 6 | 2 | ∞ | ∞ | ∞ | ∞ |
C | - | 6 | - | 7 | ∞ | ∞ | ∞ |
B | - | - | - | 7 | ∞ | ∞ | ∞ |
D | - | - | - | - | 17 | 22 | ∞ |
E | - | - | - | - | - | 22 | 19 |
Chemin : A → C → D → E → G avec une distance de 19
Chemin : A → F
Correction
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
0 | ∞ | ∞ | ∞ | ∞ | ∞ | |
A | - | 4 | 4 | ∞ | ∞ | ∞ |
B | - | - | 4 | ∞ | ∞ | ∞ |
C | - | - | - | 7 | 5 | 10 |
E | - | - | - | 7 | - | 8 |
F | - | - | - | - | - | 8 |
ou
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
0 | ∞ | ∞ | ∞ | ∞ | ∞ | |
A | - | 4 | 4 | ∞ | ∞ | ∞ |
C | - | 4 | - | 7 | 5 | 10 |
B | - | - | - | 7 | 5 | 10 |
E | - | - | - | 7 | - | 8 |
F | - | - | - | - | - | 8 |
Chemin : A → C → E → F avec une distance de 8
Chemin : D → I
Correction
A | B | C | D | E | F | G | H | I | |
---|---|---|---|---|---|---|---|---|---|
∞ | ∞ | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | |
D | 3 | ∞ | ∞ | - | 7 | ∞ | 5 | ∞ | ∞ |
A | - | 10 | ∞ | - | 4 | ∞ | 5 | ∞ | ∞ |
E | - | 6 | ∞ | - | - | 5 | 5 | 7 | ∞ |
F | - | 6 | 8 | - | - | - | 5 | 7 | 7 |
G | - | 6 | 8 | - | - | - | - | 7 | 7 |
B | - | - | 7 | - | - | - | - | 7 | 7 |
C | - | - | - | - | - | - | - | 7 | 7 |
H | - | - | - | - | - | - | - | - | 7 |
Chemin : D → A → E → F → I avec une distance de 7
Chemin : A → J
Correction
A | B | C | D | E | F | G | H | I | J | |
---|---|---|---|---|---|---|---|---|---|---|
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
A | - | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ |
B | - | - | 217 | ∞ | 173 | 165 | ∞ | ∞ | ∞ | ∞ |
F | - | - | 217 | ∞ | 173 | - | ∞ | ∞ | 415 | ∞ |
E | - | - | 217 | ∞ | - | - | ∞ | ∞ | 415 | 675 |
C | - | - | - | ∞ | - | - | 403 | 320 | 415 | 675 |
H | - | - | - | 503 | - | - | 403 | - | 415 | 487 |
G | - | - | - | 503 | - | - | - | - | 415 | 487 |
I | - | - | - | 503 | - | - | - | - | - | 487 |
Chemin : A → C → H → J avec une distance de 487 km