Le chemin le plus court
Comment un terminal de navigation GPS calcule-t-il l’itinéraire entre le lieu de départ et le lieu d’arrivée ?
Comment prend-il en compte des critères tels que distance, temps, coût (carburant et péages d’autoroutes) ?
Et comment fait-il pour proposer en quelques secondes un nouvel itinéraire alors que l’on vient d’oublier de tourner à droite comme il le suggérait ?
L’algorithme de Dijkstra
Quel est le plus court chemin pour aller de D à A ?
Pour trouver le plus court chemin, on bâti un tableau.
On sélectionne successivement les villes en commençant par celle de départ, D.
| D | B | E | C | F | A | prochaine ville |
| 3 D | 1 D | ∞ | ∞ | ∞ | E | |
| 2 E | 4 E | 6 E | ∞ | B | ||
| 4 E | ∞ | ∞ | C | |||
| 5 C | 8 C | F | ||||
| 6 F | A |
Partant de D :
- B est à une distance totale de 3 km : on note « 3 D » dans la colonne B.
- E est à une distance totale d’ 1 km : on note « 1 D » dans la colonne E.
- Pour les autres villes, pas encore visitées, on note « ∞ » pour infini.
- La prochaine ville sélectionnée est E (plus courte distance : 1 km).
Partant de D, via E :
- B est à une distance totale de 2 km (1+1) : on note « 2 E » dans la colonne B, car 2 est plus petit que 3 déjà présent. Si le résultat est plus grand, on ne change rien. Idem en l’absence de route directe entre E et B.
- C est à une distance totale de 4 km (1+3) : on note « 4 E » dans cette colonne.
- F est à une distance totale de 6 km (1+5) : on note « 6 E » dans la colonne F.
- A n’est pas directement reliée à E : ∞.
- La prochaine ville sélectionnée est B (plus courte distance : 2 km).
Etc…
L’algorithme se poursuit jusqu’à ce que la ville d’arrivée soit sélectionnée.
Remarques :
- c’est l’algorithme qui impose l’ordre de sélection.
- à la ligne 3, on aurait pu écrire « 4 B » dans la colonne C. Cependant, il y avait déjà un chemin de 4km sans passer par B : on garde donc « 4 E ».
Le plus court chemin est donc DECFA avec une distance totale de 6 km.
L’algorithme de Djjkstra est un algorithme de parcours en largeur du graphe : les villes sélectionnées sont
d’abord D, puis E et B, puis C et F, puis A.
Exercice :
- A l’aide d’un tableur (Libreoffice Calc, …) mettre en œuvre l’algorithme de Djjkstra pour trouver le plus court chemin entre Parme et Rome.
- Recommencer pour trouver le chemin le plus rapide, puis le moins cher.
Représentation d’un graphe par matrice d’adjacence
Afin d’implémenter l’algorithme de Djjkstra dans un langage informatique, il faut trouver une structure numérique pour le graphe.
Une solution consiste à :
- choisir un classement ordonné pour chaque nœud :
par exemple : D, B, E, C, F, A
- recenser, pour chaque nœud, la liste des nœuds directement adjacents :
D → B, E
B → D, E, C
E → D, B, C, F
C → B, E, F, A
F → E, C, A
A → C, F
- Construire la matrice d’adjacence, avec les coefficients $a_{ij}$ (distance, durée, coût, …) de la route
reliant le nœud $i$ au nœud $j$. (on peut choisir le coefficient 0 pour si les deux nœuds ne sont pas adjacents) :
\[ \left( \begin{array}{ccc}
0 & 3 & 1 & 0 & 0 & 0\\
3 & 0 & 1 & 2 & 0 & 0\\
1 & 1 & 0 & 3 & 5 & 0\\
0 & 2 & 3 & 0 & 1 & 3\\
0 & 0 & 5 & 1 & 0 & 1\\
0 & 0 & 0 & 3 & 1 & 0\end{array} \right)\]
Remarque : cette matrice est symétrique. C’est une caractéristique due au fait que tous les chemins sont à double sens.
Il devient ensuite aisé d’implémenter cette structure dans un langage informatique.
En Python par exemple :
m_distance = [[0,3,1,0,0,0], [3,0,1,2,0,0], [1,1,0,3,5,0], [0,2,3,0,1,3], [0,0,5,1,0,1], [0,0,5,1,0,1], [0,0,0,3,1,0]]
Cette liste, ordonnée, permet de représenter chaque ville par un simple indice.
