Dijkstra à la main, puis en machine

Le déroulé. On note $\infty$ une distance encore inconnue ; à chaque étape on fixe le sommet non traité de plus petite distance provisoire (encadré ci-dessous par des crochets), puis on met à jour ses voisins.

étape	$A$	$B$	$C$	$D$	$E$	on fixe
départ	$0$	$\infty$	$\infty$	$\infty$	$\infty$	$A$ $(0)$
après $A$	$0$	$2$	$5$	$\infty$	$\infty$	$B$ $(2)$
après $B$	$0$	$2$	$3$	$6$	$\infty$	$C$ $(3)$
après $C$	$0$	$2$	$3$	$4$	$11$	$D$ $(4)$
après $D$	$0$	$2$	$3$	$4$	$7$	$E$ $(7)$

Les deux mises à jour intéressantes. Après avoir fixé $B$, la distance de $C$ passe de $5$ à $3$ : le détour $A\to B\to C$ coûte $2+1=3$, moins que l'arête directe $AC=5$. De même, après $D$, la distance de $E$ passe de $11$ à $7$, car $A\to B\to C\to D\to E$ coûte $4+3=7$ contre $3+8=11$ par $CE$.

Distances finales. $A:0$, $B:2$, $C:3$, $D:4$, $E:7$.

La vérification en Python.

def dijkstra(G, source):
    dist = {s: float("inf") for s in G}
    dist[source] = 0
    a_traiter = set(G)
    while a_traiter:
        u = min(a_traiter, key=lambda s: dist[s])
        if dist[u] == float("inf"):
            break
        a_traiter.remove(u)
        for v, poids in G[u]:
            if dist[u] + poids < dist[v]:
                dist[v] = dist[u] + poids
    return dist

G = {"A": [("B", 2), ("C", 5)],
     "B": [("A", 2), ("C", 1), ("D", 4)],
     "C": [("A", 5), ("B", 1), ("D", 1), ("E", 8)],
     "D": [("B", 4), ("C", 1), ("E", 3)],
     "E": [("C", 8), ("D", 3)]}

print(dijkstra(G, "A"))
# {'A': 0, 'B': 2, 'C': 3, 'D': 4, 'E': 7}

Ce que l'exemple illustre. Le plus court chemin vers $E$ emprunte quatre arêtes ($A,B,C,D,E$) alors qu'un chemin de deux arêtes existe ($A\to C\to E$, de longueur $13$) : le plus court n'est pas celui qui compte le moins d'arêtes.

Un graphe non orienté se saisit deux fois. Chaque arête apparaît dans la liste des deux extrémités. L'oublier revient à orienter le graphe sans le vouloir, et peut rendre certains sommets inatteignables.