Floyd-Warshall — toutes les distances d'un graphe en trois lignes

(a) Le plus court chemin de $i$ à $j$ passant par les sommets intermédiaires inférieurs à $k$ soit passe par le sommet $k-1$ (et se décompose en $i\to k-1\to j$), soit ne passe pas par $k-1$. La récurrence s'écrit : $$D_k(i,j)=\min (D_{k-1}(i,j),D_{k-1}(i,k-1)+D_{k-1}(k-1,j))$$ avec $D_0(i,j)$ initialisée à la valeur du poids de l'arc de $i$ à $j$ (ou $\infty$ en l'absence d'arc). (b)

def floyd_warshall(M: list) -> list:
    n = len(M)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if M[i][k] + M[k][j] < M[i][j]:
                    M[i][j] = M[i][k] + M[k][j]
    return M

INF = float("inf")
# Sommets s, a, b indexés par 0, 1, 2
M = [[0, 2, 3],
     [INF, 0, INF],
     [INF, -2, 0]]
floyd_warshall(M)
assert M[0][1] == 1  # s -> b -> a : poids 3 - 2 = 1

L'algorithme de Floyd-Warshall gère correctement les arcs de poids négatifs (contrairement à Dijkstra) tant qu'il n'y a pas de cycle de poids négatif. (c) Floyd-Warshall s'exécute en $O(n^3)$ en temps et nécessite une simple matrice en espace. Dijkstra exécuté $n$ fois prend $O(n^3)$ en temps avec une implémentation par tableau simple, mais peut descendre à $O(n\cdot (n+m)\log n)$ avec un tas. Floyd-Warshall est donc préférable sur les graphes denses ou en présence d'arcs négatifs, tandis que Dijkstra répété est plus rapide sur les grands graphes creux sans arcs négatifs.