Itinéraires et graphes
Un des intérêts de la cartographie numérique est de permettre des calculs à partir des informations enregistrées.
On considère la situation suivante :
Un automobiliste souhaite faire le trajet Poitiers-Châteauroux.
En consultant plusieurs cartes IGN, il a repéré les "nœuds" routiers possibles où pourrait passer son itinéraire :
Poitiers (P), Chauvigny (Cv), Bonneuil-Matours (B), Pleumartin (Pl), Saint-Savin (Sv), Preuilly-sur-Claise (Pr), Tournon-Saint-Martin (T), Le Blanc (L), Mézières-en-Brenne (M), Méobecq (Mo), Saint-Gaultier (SG), Châteauroux (Ct).
Afin de modéliser la situation, il simplifie la représentation des nœuds et des liaisons routières en utilisant un graphe où les sommets sont les nœuds cités plus haut et les arêtes sont les liaisons routières.
En s'aidant de la carte, il reporte sur le graphe les distances en km pour obtenir un graphe pondéré :
L'automobiliste souhaite déterminer le plus court chemin entre P et Ct.
Pour ce faire, il va suivre un algorithme appelé algorithme de Dijkstra, du nom du mathématicien hollandais Edsger Dijkstra (1930-2002) qui l'a inventé en 1959.
Méthode : Algorithme de Dijkstra
initialisation : partir du sommet de départ P et noter à côté la distance en provenance de P : 0(P) et entourer cette distance pour signifier que le sommet a été traité ;
attribuer provisoirement aux sommets adjacents à P les poids des arêtes qui les relient à P
Tant que tous les sommets n'ont pas été traités, faire :
parmi tous les sommets provisoirement pondérés, sélectionner définitivement le sommet Pmin de poids minimum ;
entourer son poids pour signifier que ce sommet est fixé ;
pour chaque sommet P' non traité et adjacent à Pmin, calculer la somme S du poids de Pmin et du poids de l'arête reliant Pmin à P' :
si S est inférieure au poids provisoire de P' ou que celui-ci n'a pas de poids provisoire, affecter S à P' comme nouveau poids provisoire en notant la provenance de Pmin entre parenthèse : S(Pmin)
sinon, laisser le poids provisoire existant de P'
Mise en oeuvre
Etape n°1
On part de P et on note 0(P) au sommet P puis, on entoure ce nombre pour signifier qu'il est fixé.
On reporte sur les sommets adjacents les poids des arêtes : 22(P) pour B et 25(P) pour Cv.
Etape n°2
On sélectionne B de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on affecte 22 + 18 = 40(B) à Pl et on ne change pas le poids de Cv : 22 + 14 = 36 > 25.
Etape n°3
On sélectionne Cv de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on affecte 25 + 19 = 44(Cv) à Sv et 25 + 33 = 58(Cv) à T.
Etape n°4
On sélectionne Pl de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on affecte 40 + 19 = 59(Pl) à Pr et, comme 40 + 17 = 57 < 58, on affecte 57(Pl) à T.
Etape n°5
On sélectionne Sv de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on affecte 44 + 17 = 61(Sv) à L et on ne change pas le poids de T : 44 + 24 = 68 > 57.
Etape n°6
On sélectionne T de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on affecte 57 + 24 = 81(T) à M et on ne change pas le poids de Pr ( 57 + 14 = 71 > 59) ni celui de L (57 + 16 = 73 > 61).
Etape n°7
On sélectionne Pr de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on ne change pas le poids de M (59 + 24 = 83 > 81).
Etape n°8
On sélectionne L de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on affecte 61 + 31 = 92(L) à Mo et on affecte 61 + 30 = 91(L) à SG.
Etape n°9
On sélectionne M de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on affecte 81 + 39 = 120(M) à Ct et on ne change pas le poids de Mo ( 81 + 20 = 101 > 92).
Etape n°10
On sélectionne SG de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : on ne change pas le poids de Mo (91 + 13 = 104 > 92) ni celui de Ct (91 + 31 = 122 > 120).
Etape n°11
On sélectionne Mo de poids minimal et on actualise les poids des sommets adjacents s'ils sont inexistants ou de valeur inférieure : comme 92 + 25 = 117 < 120 on affecte 117 à Ct.
Conclusion
Le chemin le plus court (dans ce graphe) pour aller de Poitiers à Châteauroux a une longueur de 117 km et pour savoir où il passe, on remonte les sommets à partir du sommet d'arrivée en utilisant les sommets entre parenthèses : P --> Cv --> Sv --> L --> Mo --> Ct
