Du point de vue mathématique, une carte routière peut être vue comme un graphe orienté et pondéré, c’est-à-dire un ensemble de carrefours (les sommets) reliés par des routes (les arcs) a priori à sens unique et de longueurs variables. La longueur de l’arc reliant le sommet u au sommet v est notée l (uv ).
.jpg)
Un graphe orienté pondéré.
Pour aller d’un sommet u à un sommet v on suit un chemin, c’est-à-dire une succession d’arcs qui nous mènent de proche en proche vers notre but. La longueur totale du chemin est simplement la somme des longueurs de chacun des arcs traversés. Par exemple, le chemin cba (l’arête cb suivie de l’arête ba) est de longueur 3 + 12 = 15. Le chemin ed, réduit à un seul arc, a pour longueur 9, la longueur de cette arête.
Il peut arriver, bien sûr, qu’un chemin passe par plus d’arc qu’un autre tout en étant de longueur inférieure. Il en va ainsi de cbda, de longueur 3 + 2 + 1 = 6, plus petite que celle de cba. Enfin, il se peut également que deux sommets ne puissent être joints par un sommet. Dans notre exemple, il est en particulier impossible d’aller de b vers e. Par convention, le « plus court chemin » de b à e ...
Lire la suite