Problème du plus court chemin
Objectifs
- Définir le problème du plus court chemin
- Appliquer l'algorithme de Dijkstra
Cours
F pour passer en plein écran ou O pour afficher la vue d'ensemble.
Versions sans animation, plein écran, imprimable.
Exercices
Dijkstra
Appliquer l'algorithme de Dijkstra sur les graphes suivants :
Chemin : A → G
Solution
| 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
Solution
| 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
Solution
| 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
Solution
| 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