Le plus court chemin

CoursGraphes pondérés

Dans un graphe pondéré, chaque arête porte un nombre, son poids : une distance en km, une durée en minutes, un prix… La longueur d'une chaîne est alors la somme des poids de ses arêtes.

Les GPS et les sites d'itinéraires cherchent la chaîne de plus petit poids entre deux sommets. L'algorithme le plus célèbre pour cela a été inventé par Edsger Dijkstra en 1956.

MéthodeL'algorithme de Dijkstra, version dessin

1. Au départ : écris 0 sur le sommet de départ et ∞ sur tous les autres.
2. Choisis le sommet non traité qui a la plus petite valeur : c'est le sommet actif. Entoure-le.
3. Regarde ses voisins non traités. Pour chacun, calcule : valeur du sommet actif + poids de l'arête.
4. Si ce nombre est plus petit que la valeur du voisin : remplace la valeur, trace en couleur l'arête qui vient du sommet actif, et raye l'ancienne arête colorée qui arrivait à ce voisin (s'il y en avait une).
5. Si ce nombre est plus grand ou égal : ne change rien.
6. Le sommet actif est maintenant traité : encadre sa valeur, elle ne changera plus.
7. Recommence à l'étape 2 jusqu'à ce que tous les sommets soient traités.

À la fin, la valeur de chaque sommet est sa distance au départ, et les arêtes colorées forment les plus courts chemins.

Exemple : le graphe de la fiche méthode, depuis A

1. Départ : 0 sur A, ∞ sur tous les autres sommets.
2. Sommet actif A. B reçoit 3 et E reçoit 2 : on trace A–B et A–E.
3. Sommet actif E (car 2 < 3). F reçoit 2 + 5 = 7 et D reçoit 2 + 5 = 7 : on trace E–F et E–D. Vers B : 2 + 5 = 7, plus grand que 3, rien à faire.
4. Sommet actif B (3). Vers F : 3 + 1 = 4 < 7, on raye E–F et on trace B–F. Vers D : 3 + 4 = 7, égalité, rien à faire. Vers C : 3 + 2 = 5, on trace B–C.
5. Sommet actif F (4). Vers D : 4 + 2 = 6 < 7, on raye E–D et on trace F–D.
6. Sommet actif C (5). Vers D : 5 + 2 = 7, pas mieux que 6, rien à faire.
7. Dernier sommet D (6) : terminé.

Pour aller de A à D : A–B–F–D, longueur 6. Pour aller en C : A–B–C, longueur 5.

ExercicesChercher le plus court chemin

PythonDes itinéraires réels

Le module pyroutelib3 calcule un vrai itinéraire en téléchargeant les rues d'OpenStreetMap, puis en appliquant un algorithme de plus court chemin de la famille de Dijkstra.

1. Installe le module pyroutelib3 comme tu as installé Folium.
2. Copie et exécute le programme ci-dessous (il faut une connexion Internet : le premier calcul peut prendre une minute).

import folium
import pyroutelib3

# le réseau des chemins piétons, téléchargé au fur et à mesure
graphe = pyroutelib3.osm.LiveGraph(pyroutelib3.osm.FootProfile())

depart = graphe.find_nearest_node((44.16213, 4.617122))
arrivee = graphe.find_nearest_node((44.163942, 4.611689))
chemin = pyroutelib3.find_route_without_turn_around(graphe, depart.id, arrivee.id)
points = [graphe.get_node(n).position for n in chemin]

carte = folium.Map(location=[44.163, 4.614], zoom_start=16)
folium.PolyLine(points, color="red", weight=5).add_to(carte)
folium.Marker(points[0], popup="Départ").add_to(carte)
folium.Marker(points[-1], popup="Arrivée").add_to(carte)
carte.save("itineraire.html")

graphe = {
    "A": {"B": 3, "E": 2},
    "B": {"A": 3, "C": 2, "D": 4, "E": 5, "F": 1},
    "C": {"B": 2, "D": 2},
    "D": {"B": 4, "C": 2, "E": 5, "F": 2},
    "E": {"A": 2, "B": 5, "D": 5, "F": 5},
    "F": {"B": 1, "D": 2, "E": 5},
}

def dijkstra(graphe, depart):
    distance = {s: float("inf") for s in graphe}
    venant_de = {s: None for s in graphe}
    distance[depart] = 0
    a_traiter = list(graphe)
    while a_traiter:
        actif = min(a_traiter, key=lambda s: distance[s])
        a_traiter.remove(actif)
        for voisin, poids in graphe[actif].items():
            if distance[actif] + poids < distance[voisin]:
                distance[voisin] = distance[actif] + poids
                venant_de[voisin] = actif
    return distance, venant_de

def chemin(venant_de, arrivee):
    etapes = [arrivee]
    while venant_de[etapes[0]] is not None:
        etapes.insert(0, venant_de[etapes[0]])
    return "-".join(etapes)

distance, venant_de = dijkstra(graphe, "A")
for s in distance:
    print(s, distance[s], chemin(venant_de, s))