Une source vers tous, tous vers un, un vers un

Plutôt que d'exécuter $n$ fois Dijkstra (une fois depuis chaque point de départ), ce qui prendrait un temps prohibitivement long, on commence par inverser l'orientation de tous les arcs du graphe orienté d'origine (on remplace chaque arc $u\to v$ par $v\to u$, opération en $O(n+m)$). On lance alors un unique Dijkstra sur ce graphe inversé en prenant la cible $T$ comme source. La distance trouvée de $T$ vers un sommet $u$ dans le graphe inversé correspond exactement à la distance minimale de $u$ vers $T$ dans le graphe d'origine.