Dijkstra vs Bellman-Ford vs Floyd-Warshall

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La réponse courte

L'algorithme de Dijkstra, l'algorithme de Bellman-Ford et l'algorithme de Floyd-Warshall trouvent tous des plus courts chemins dans un graphe pondéré, mais ils répondent à des questions différentes dans des conditions différentes. Deux questions permettent de choisir entre eux : vous faut-il les distances depuis une seule source ou entre toutes les paires de sommets, et une arête peut-elle avoir un poids négatif ?

Ici V est le nombre de sommets et E le nombre d'arêtes. En une phrase : utilisez Dijkstra par défaut, passez à Bellman-Ford lorsque les poids peuvent être négatifs, et utilisez Floyd-Warshall lorsqu'il vous faut la table complète des distances d'un graphe d'au plus quelques centaines de sommets. Lorsqu'il vous faut toutes les paires dans un grand graphe creux avec des arêtes de poids négatif, l'algorithme de Johnson de la section 7 combine les deux premiers. La suite de ce guide exécute les trois sur le même graphe et montre où chacun l'emporte et où chacun échoue.

2. Un graphe, trois réponses

L'exemple suivi est un petit graphe orienté à six sommets et sept arêtes, dont une arête de poids négatif, B → A de poids -4. Considérez les poids comme des coûts : un coût négatif est un remboursement, comme une route à péage qui vous paie pour l'emprunter, ou une étape d'un procédé chimique qui libère de l'énergie.

S → A  3      S → B  6      A → C  4      B → A  -4
C → T  2      B → D  3      D → T  4

6 sommets, 7 arêtes, aucun cycle ; source S

Le chemin le moins coûteux de S à T est S, B, A, C, T, de coût 6 - 4 + 4 + 2 = 8. Il commence par le premier pas le plus cher, vers B, et le rattrape grâce au remboursement. Le programme ci-dessous implémente les trois algorithmes sous leur forme classique des manuels et les exécute depuis S.

import heapq
INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def dijkstra(adj, s):
    """Glouton : fixe le sommet non fixé le plus proche, sans jamais y revenir."""
    dist = {v: INF for v in adj}
    dist[s] = 0
    done, heap = set(), [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue                      # entrée périmée du tas
        done.add(u)
        for v, w in adj[u]:
            if v not in done and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def bellman_ford(adj, s):
    """Relâche chaque arête, tour après tour, jusqu'à ce que plus rien ne change."""
    dist = {v: INF for v in adj}
    dist[s] = 0
    for _ in range(len(adj) - 1):
        changed = False
        for u in adj:
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    changed = True
        if not changed:
            break
    return dist

def floyd_warshall(adj):
    """Toutes les paires : autorise les sommets comme étapes, un à la fois."""
    d = {u: {v: 0 if u == v else INF for v in adj} for u in adj}
    for u in adj:
        for v, w in adj[u]:
            d[u][v] = min(d[u][v], w)
    for k in adj:
        for i in adj:
            for j in adj:
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

G = graph([('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
           ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)])
dj, bf, fw = dijkstra(G, 'S'), bellman_ford(G, 'S'), floyd_warshall(G)['S']
for v in G:
    print(v, dj[v], bf[v], fw[v], '' if dj[v] == bf[v] else '<- Dijkstra is wrong')
# S 0 0 0
# A 3 2 2 <- Dijkstra is wrong
# B 6 6 6
# C 7 6 6 <- Dijkstra is wrong
# T 9 8 8 <- Dijkstra is wrong
# D 9 9 9

Bellman-Ford et Floyd-Warshall renvoient les vraies distances. Dijkstra annonce 3 pour A, 7 pour C et 9 pour T, toutes trop élevées, et il ne signale aucune erreur : les mauvaises réponses ressemblent exactement aux bonnes. La section 4 explique pourquoi. Sur un graphe à poids positifs ou nuls, les trois seraient d'accord, et la seule différence serait la vitesse.

3. Ce que fait chaque algorithme

Les trois algorithmes reposent sur une seule opération, la relaxation. Chaque sommet v porte une distance provisoire dist[v], qui vaut au départ l'infini, ou 0 pour la source. Relâcher l'arête u → v de poids w revient à se demander s'il est moins coûteux de passer par u et, si c'est le cas, à l'enregistrer :

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Une distance provisoire ne fait que diminuer, et c'est toujours le coût d'un chemin réel. Les algorithmes ne diffèrent que sur deux points : quelles arêtes ils relâchent, et dans quel ordre.

• Dijkstra conserve les sommets non fixés dans une file de priorité. Il prend à chaque fois celui dont la distance provisoire est la plus petite, déclare cette distance définitive et relâche ses arêtes sortantes. Chaque sommet est fixé une fois et chaque arête relâchée une fois. Edsger Dijkstra l'a conçu en 1956, en une vingtaine de minutes selon ses propres dires, et l'a publié en 1959. Le guide de l'algorithme de Dijkstra le suit pas à pas.
• Bellman-Ford ne fait aucun choix. Il relâche toutes les arêtes, dans un ordre fixé quelconque, et recommence. Un plus court chemin sans cycle a au plus V - 1 arêtes, et après le tour i, tout plus court chemin d'au plus i arêtes a été trouvé, donc V - 1 tours suffisent toujours. Le nom associe Richard Bellman, qui a publié la méthode par tours en 1958, et Lester Ford, dont l'article de 1956 donnait la règle générale : relâcher les arêtes jusqu'à ce que plus rien ne s'améliore. Alfonso Shimbel et Edward Moore ont trouvé des méthodes équivalentes à la même époque. Le guide de l'algorithme de Bellman-Ford démontre cette borne.
• Floyd-Warshall calcule toute la table d'un coup. Il autorise les sommets comme étapes intermédiaires, un à la fois : après l'étape k, la case [i][j] contient le chemin le moins coûteux de i à j dont les sommets intermédiaires sont tous pris parmi les k premiers. Trois boucles imbriquées et une ligne d'arithmétique. Bernard Roy en 1959 et Stephen Warshall en 1962 ont publié le même schéma pour l'accessibilité, et Robert Floyd l'a adapté aux plus courts chemins en 1962. Le guide de l'algorithme de Floyd-Warshall établit la récurrence.

Sur l'exemple, Bellman-Ford parcourt les arêtes dans l'ordre où elles ont été énumérées. Dès son premier tour, il abaisse A à 2 lorsqu'il atteint les arêtes sortant de B, mais à ce moment il a déjà utilisé l'ancienne valeur 3 pour fixer C = 7. Le deuxième tour propage l'amélioration jusqu'à C = 6 et T = 8. Le troisième tour ne change rien, donc l'algorithme s'arrête tôt au lieu d'exécuter les V - 1 = 5 tours. Le nombre de tours nécessaires dépend de l'ordre des arêtes, mais ne dépasse jamais V - 1.

4. Pourquoi Dijkstra échoue avec des arêtes de poids négatif

La rapidité de Dijkstra repose sur une promesse : quand un sommet sort de la file de priorité, sa distance est définitive. Cette promesse s'appuie sur un argument qui exige des poids positifs ou nuls. Supposons que u soit le sommet non fixé le plus proche. Tout autre chemin vers u doit quitter la région fixée en passant par un sommet non fixé x, qui est déjà au moins aussi loin que u, et le reste du chemin ne peut qu'ajouter du coût. Avec une arête de poids négatif, le reste du chemin peut retrancher du coût, et l'argument s'effondre.

C'est exactement ce qui se passe dans l'exemple. Dijkstra fixe S à 0, puis A à 3, parce que 3 est inférieur au 6 de B. Lorsque B est fixé et que son arête vers A propose 6 - 4 = 2, A est déjà définitif et l'amélioration est perdue. Tout ce qui repose sur A hérite de l'erreur : C est fixé à 3 + 4 = 7 au lieu de 6, et T à 9 au lieu de 8.

Deux corrections tentantes ne fonctionnent pas :

• Ajouter une constante à chaque poids. Ajouter 4 rend tous les poids positifs ou nuls, mais cela facture 4 pour chaque arête, si bien que les chemins comportant plus d'arêtes sont davantage pénalisés. Sur le graphe décalé, Dijkstra trouve S, A, C, T, de coût décalé 21 contre 24 pour le vrai plus court chemin S, B, A, C, T, qui a une arête de plus. Avec les poids d'origine, ce chemin coûte 9, et non 8. L'algorithme de Johnson, à la section 7, montre la repondération qui fonctionne.
• Permettre aux sommets fixés de rouvrir. Si un sommet peut revenir dans la file chaque fois que sa distance baisse, l'algorithme devient correct pour les arêtes de poids négatif tant qu'il n'y a pas de cycle négatif. Mais la promesse qui le rendait rapide disparaît, et Donald Johnson a montré en 1973 que l'algorithme de Dijkstra ainsi adapté aux arêtes de poids négatif peut prendre un temps exponentiel, de l'ordre de n 2n étapes sur une famille de graphes à n sommets. Bellman-Ford, avec sa garantie en O(V E), est alors le choix le plus sûr.

Avec des poids positifs ou nuls, rien de tout cela ne se produit : Dijkstra est correct et c'est le plus rapide des trois. Les poids nuls ne posent aucun problème : l'argument exige seulement qu'aucune arête ne diminue le coût.

5. Cycles négatifs

Un cycle négatif est un cycle dont les poids ont une somme inférieure à zéro. S'il est accessible depuis la source et peut atteindre la cible, il n'existe aucun plus court chemin : refaire un tour du cycle coûte toujours moins cher. La distance vaut moins l'infini, et un algorithme doit signaler le cycle plutôt qu'un nombre. Ajoutez l'arête C → B de poids -5 à l'exemple, et le cycle B, A, C, B coûte -4 + 4 - 5 = -5.

• Bellman-Ford le détecte avec un tour supplémentaire. Sans cycle négatif, plus rien ne peut s'améliorer après V - 1 tours ; si le tour V fait encore baisser une distance, un cycle négatif existe, et remonter les pointeurs de parent depuis le sommet modifié mène jusqu'à lui.
• Floyd-Warshall le détecte sur la diagonale. La case [v][v] vaut 0 au départ et ne peut devenir négative que s'il existe un parcours fermé passant par v de poids total négatif. Un cycle négatif existe donc exactement lorsqu'une case de la diagonale finit sous zéro. Dès que cela se produit, les autres cases ne sont plus des distances significatives, et Stefan Hougardy a montré en 2010 qu'elles peuvent devenir exponentiellement grandes : le plus sûr est donc de vérifier la diagonale à l'intérieur de la boucle et de s'arrêter dès qu'une case devient négative.
• Dijkstra ne peut pas en détecter. Il suppose simplement que la situation ne se présente pas.

INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def negative_cycle(adj):
    """Bellman-Ford depuis une source virtuelle reliée à chaque sommet avec un coût 0.
    Renvoie un cycle négatif sous forme de liste de sommets, ou None."""
    dist = {v: 0 for v in adj}
    parent = {v: None for v in adj}
    for _ in range(len(adj)):                  # un tour de plus que d'habitude
        last = None
        for u in adj:
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v], parent[v], last = dist[u] + w, u, v
        if last is None:
            return None                        # un tour calme : aucun cycle négatif
    for _ in range(len(adj)):                  # reculer assez loin pour tomber sur le cycle
        last = parent[last]
    cycle, v = [last], parent[last]
    while v != last:                           # suivre les parents sur un tour du cycle
        cycle.append(v)
        v = parent[v]
    cycle.reverse()                            # les parents pointent vers l'arrière
    return cycle + cycle[:1]

def floyd_warshall_diagonal(adj):
    """Sommets dont la distance à eux-mêmes ressort négative."""
    d = {u: {v: 0 if u == v else INF for v in adj} for u in adj}
    for u in adj:
        for v, w in adj[u]:
            d[u][v] = min(d[u][v], w)
    for k in adj:
        for i in adj:
            for j in adj:
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return [v for v in adj if d[v][v] < 0]

edges = [('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
         ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)]
print(negative_cycle(graph(edges)))
# None
bad = graph(edges + [('C', 'B', -5)])          # B -> A -> C -> B coûte -4 + 4 - 5 = -5
print(negative_cycle(bad))
# ['C', 'B', 'A', 'C']
print(floyd_warshall_diagonal(bad))
# ['A', 'B', 'C']

La fonction lance Bellman-Ford depuis une source virtuelle reliée à chaque sommet avec un coût 0 ; elle trouve donc un cycle négatif n'importe où dans le graphe, et pas seulement un cycle accessible depuis S. Sur l'exemple d'origine, un tour finit par ne plus rien changer et elle renvoie None. Avec l'arête supplémentaire, elle renvoie le cycle C, B, A, C, le même cycle écrit à partir d'un autre départ, et Floyd-Warshall signale A, B et C sur sa diagonale. Lors de tests sur des milliers de graphes aléatoires, la diagonale a signalé un cycle négatif exactement lorsqu'il en existait un, mais n'a pas toujours signalé chaque sommet capable d'en atteindre un : utilisez-la donc comme un test par oui ou non.

Un piège attrape beaucoup de monde. Dans un graphe non orienté, une arête peut être parcourue dans les deux sens, si bien qu'une seule arête de poids négatif constitue déjà un cycle négatif : u, v, u. Bellman-Ford exécuté sur la version orientée d'un graphe non orienté signalera donc un cycle négatif dès qu'une arête est négative, un écueil que détaille le livre Algorithms de Sedgewick et Wayne. Les plus courts chemins simples à poids négatifs dans les graphes non orientés exigent d'autres méthodes, plus élaborées.

6. Vitesse : lequel est le plus rapide, et quand

Pour une source unique, l'ordre est clair dès que Dijkstra s'applique : O((V + E) log V) avec un tas binaire, contre O(V E) pour Bellman-Ford. Sur un graphe de 10 000 sommets et 50 000 arêtes, cela représente environ un million d'opérations de tas contre jusqu'à 500 millions de relaxations d'arêtes. Floyd-Warshall n'est pas une méthode à source unique, et l'exécuter pour une seule source gaspille presque tout son travail.

Pour toutes les paires, la comparaison est plus serrée, car les alternatives consistent à exécuter un algorithme à source unique depuis chaque sommet :

Les bornes asymptotiques cachent des constantes ; le programme ci-dessous compte donc les opérations élémentaires que chaque méthode effectue réellement sur deux graphes orientés aléatoires de 100 sommets : un graphe creux de 300 arêtes et un graphe dense de 4 950, soit la moitié de toutes les arêtes possibles. Pour Dijkstra, il compte séparément les vérifications d'arêtes et les opérations de tas, car une opération de tas coûte environ log V étapes.

import heapq, random
INF = float('inf')

def random_graph(n, m, seed):
    """n sommets, m arêtes orientées distinctes de poids 1..100."""
    rnd = random.Random(seed)
    pairs = rnd.sample([(u, v) for u in range(n) for v in range(n) if u != v], m)
    adj = {v: [] for v in range(n)}
    for u, v in pairs:
        adj[u].append((v, rnd.randint(1, 100)))
    return adj

def all_pairs_dijkstra(adj):
    """Dijkstra depuis chaque sommet. Compte les vérifications d'arêtes et les opérations de tas."""
    checks = heap_ops = 0
    for s in adj:
        dist, heap = {v: INF for v in adj}, [(0, s)]
        dist[s] = 0
        while heap:
            d, u = heapq.heappop(heap)
            heap_ops += 1
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                checks += 1
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))
                    heap_ops += 1
    return checks, heap_ops

def all_pairs_bellman_ford(adj):
    """Bellman-Ford depuis chaque sommet, avec arrêt anticipé quand un tour ne change rien."""
    m, checks = sum(len(a) for a in adj.values()), 0
    for s in adj:
        dist = {v: INF for v in adj}
        dist[s] = 0
        for _ in range(len(adj) - 1):
            changed = False
            for u in adj:
                for v, w in adj[u]:
                    if dist[u] + w < dist[v]:
                        dist[v], changed = dist[u] + w, True
            checks += m
            if not changed:
                break
    return checks

n = 100
for name, m in [('sparse', 3 * n), ('dense', n * (n - 1) // 2)]:
    adj = random_graph(n, m, seed=1)
    checks, heap_ops = all_pairs_dijkstra(adj)
    print(f'{name:6} E={m:4}  Dijkstra x V: {checks:7,} checks + {heap_ops:6,} heap ops   '
          f'Bellman-Ford x V: {all_pairs_bellman_ford(adj):9,}   Floyd-Warshall: {n ** 3:,}')
# sparse E= 300  Dijkstra x V:  27,565 checks + 21,388 heap ops   Bellman-Ford x V:   226,200   Floyd-Warshall: 1,000,000
# dense  E=4950  Dijkstra x V: 495,000 checks + 64,770 heap ops   Bellman-Ford x V: 2,712,600   Floyd-Warshall: 1,000,000

Sur le graphe creux, Dijkstra depuis chaque sommet demande environ 49 000 étapes contre 1 000 000, un nombre fixe, pour Floyd-Warshall, soit un facteur d'environ 20. Sur le graphe dense, l'écart se referme presque, et une fois compté le coût logarithmique de chaque opération de tas, la boucle interne très simple de Floyd-Warshall, qui parcourt la mémoire dans l'ordre et n'a besoin d'aucune file de priorité, l'emporte souvent en pratique. Bellman-Ford depuis chaque sommet est le plus lent dans les deux cas, même avec l'arrêt anticipé. La règle empirique : en dessous de quelques centaines de sommets, ou lorsque la plupart des paires de sommets sont reliées par une arête, utilisez Floyd-Warshall pour sa simplicité ; sur les grands graphes creux, utilisez Dijkstra ou Johnson depuis chaque sommet.

7. Toutes les paires avec des arêtes de poids négatif : l'algorithme de Johnson

L'algorithme de Donald Johnson, de 1977, réunit le meilleur des deux. Il exécute Bellman-Ford une fois pour calculer un nombre h(v) pour chaque sommet : la distance depuis une source virtuelle reliée à tous les sommets avec un coût 0. Il remplace ensuite chaque poids par

w'(u, v) = w(u, v) + h(u) - h(v)

Comme h vérifie h(v) ≤ h(u) + w(u, v) pour chaque arête, tout nouveau poids est positif ou nul. Et le long de tout chemin de s à t, les termes se télescopent, si bien que le coût de chaque chemin change de la même quantité, h(s) - h(t). Les plus courts chemins restent les plus courts, et Dijkstra peut désormais être exécuté depuis chaque sommet. Contrairement à l'ajout d'une constante, cette repondération ne dépend pas du nombre d'arêtes d'un chemin.

import heapq
INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def dijkstra(adj, s):
    dist, heap = {v: INF for v in adj}, [(0, s)]
    dist[s] = 0
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def johnson(adj):
    """Toutes les paires avec arêtes de poids négatif : un Bellman-Ford, puis Dijkstra depuis chaque sommet."""
    h = {v: 0 for v in adj}                    # distances depuis une source virtuelle
    for _ in range(len(adj)):
        for u in adj:
            for v, w in adj[u]:
                h[v] = min(h[v], h[u] + w)
    for u in adj:
        for v, w in adj[u]:
            if h[u] + w < h[v]:
                raise ValueError('negative cycle')
    # repondération : chaque arête devient positive ou nulle, chaque chemin change de h[s] - h[t]
    lifted = {u: [(v, w + h[u] - h[v]) for v, w in adj[u]] for u in adj}
    return {s: {t: d - h[s] + h[t] for t, d in dijkstra(lifted, s).items()} for s in adj}, lifted

G = graph([('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
           ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)])
dist, lifted = johnson(G)
print({u: [(v, w) for v, w in lifted[u]] for u in ('S', 'A', 'B')})
# {'S': [('A', 7), ('B', 6)], 'A': [('C', 0)], 'B': [('A', 0), ('D', 3)]}
print(dist['S'])
# {'S': 0, 'A': 2, 'B': 6, 'C': 6, 'T': 8, 'D': 9}
print(dist['B'])
# {'S': inf, 'A': -4, 'B': 0, 'C': 0, 'T': 2, 'D': 3}

Dans l'exemple, h(A) = -4 et tous les autres sommets reçoivent 0. L'arête de poids négatif B → A devient 0, S → A passe de 3 à 7 et A → C descend de 4 à 0, et Dijkstra sur les nouveaux poids, corrigé ensuite par h, donne les vraies distances depuis chaque source, y compris la ligne de B avec sa valeur négative -4. Si Bellman-Ford trouve un cycle négatif à la première étape, l'algorithme de Johnson s'arrête et le signale.

8. Quand aucun des trois n'est le meilleur choix

Certains graphes ont une structure qu'une méthode plus simple ou plus rapide peut exploiter :

• Graphes non pondérés. Si chaque arête compte pour 1, le parcours en largeur trouve toutes les distances depuis une source en O(V + E). Dijkstra donnerait la même réponse plus lentement. Voir BFS vs DFS.
• Graphes acycliques. Dans un graphe orienté acyclique, traitez les sommets dans un ordre topologique et relâchez une fois les arêtes sortantes de chaque sommet. Cela prend O(V + E) et fonctionne avec des poids négatifs. Le graphe d'exemple n'a aucun cycle : cette méthode l'aurait donc résolu en une seule passe.
• Poids 0 et 1 uniquement. Une file à double entrée remplace la file de priorité : les arêtes de poids 0 vont à l'avant et celles de poids 1 à l'arrière, ce qui donne un temps linéaire.
• Une source et une cible, avec une bonne estimation. La recherche A* ajoute une estimation de la distance restante à la priorité de Dijkstra et explore beaucoup moins de sommets sur les cartes. Voir l'algorithme de recherche A*.

9. Mémoire et reconstruction des chemins

Les distances ne suffisent souvent pas : on veut le chemin lui-même. Dijkstra et Bellman-Ford stockent un parent par sommet, le sommet d'où est arrivé le meilleur chemin, et le chemin vers t se lit à rebours depuis t. Cela coûte O(V) de mémoire supplémentaire. Floyd-Warshall a besoin d'une table complète V sur V d'entrées « saut suivant » à côté de sa table des distances, si bien que sa mémoire est en O(V2). Pour 10 000 sommets avec des entrées de 8 octets, la table des distances occupe à elle seule environ 800 mégaoctets, et la table des sauts suivants en ajoute autant. C'est la mémoire, plus que le temps, qui exclut généralement Floyd-Warshall sur les grands graphes.

10. Où sert chacun d'eux

• Dijkstra est le choix par défaut partout où les coûts sont physiques : navigation routière, correspondances aériennes et protocoles de routage à état de liens d'Internet, comme OSPF, dans lesquels chaque routeur calcule des plus courts chemins sur une carte du réseau.
• Bellman-Ford convient aux situations où chaque nœud ne connaît que ses voisins. Les protocoles de routage à vecteur de distances comme RIP répètent son étape de relaxation à travers le réseau, chaque routeur mettant à jour sa table à partir des tables de ses voisins. Sa capacité à trouver les cycles négatifs permet de repérer un arbitrage de devises : avec des poids -log(rate), une suite d'échanges qui se termine avec plus d'argent qu'au départ est exactement un cycle négatif.
• Floyd-Warshall remplit des tables de distances complètes pour les petits graphes : matrices de distances pour le partitionnement de données ou le problème du voyageur de commerce, et la fermeture transitive, c'est-à-dire la question de savoir quels sommets peuvent atteindre lesquels, qui est la version publiée par Warshall.

11. Un domaine de recherche toujours actif

Les plus courts chemins sont l'un des plus anciens problèmes de l'algorithmique, et les bornes bougent encore. En 2022, Aaron Bernstein, Danupon Nanongkai et Christian Wulff-Nilsen ont montré que les plus courts chemins à source unique avec des poids entiers négatifs peuvent être calculés en temps quasi linéaire, bien en dessous du O(V E) de Bellman-Ford. En 2024, Bernhard Haeupler et ses coauteurs ont prouvé que l'algorithme de Dijkstra, muni d'un tas convenablement conçu, est universellement optimal pour ordonner les sommets par distance : sur chaque graphe fixé, son pire cas sur l'ensemble des poids d'arêtes est à un facteur constant près le meilleur que puisse atteindre un algorithme. Et en 2025, Ran Duan et ses coauteurs ont donné un algorithme déterministe pour les graphes orientés à poids positifs ou nuls qui s'exécute en temps O(E log2/3 V), ce qui bat le O(E + V log V) de Dijkstra sur les graphes creux. Il échappe à ce que l'on a longtemps appelé la barrière du tri parce que, contrairement à Dijkstra, il ne produit pas les sommets dans l'ordre de leur distance. Chacun des trois articles a reçu un prix du meilleur article. Aucun de ces résultats n'a encore remplacé les trois classiques dans le code de tous les jours, où la simplicité et les petites constantes comptent davantage.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les algorithmes, bornes et attributions ci-dessus proviennent des sources suivantes, classées par ordre chronologique.

1. Shimbel, A. (1955). "Structure in Communication Nets." Dans Proceedings of the Symposium on Information Networks, 199 à 203. Brooklyn : Polytechnic Press of the Polytechnic Institute of Brooklyn.
2. Ford, L. R. (1956). Network Flow Theory. Paper P-923. Santa Monica : RAND Corporation.
3. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 à 90.
4. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1, 269 à 271.
5. Moore, E. F. (1959). "The Shortest Path Through a Maze." Dans Proceedings of an International Symposium on the Theory of Switching, 285 à 292. Cambridge, MA : Harvard University Press.
6. Roy, B. (1959). "Transitivité et connexité." Comptes Rendus de l'Académie des Sciences 249, 216 à 218.
7. Floyd, R. W. (1962). "Algorithm 97: Shortest Path." Communications of the ACM 5(6), 345.
8. Warshall, S. (1962). "A Theorem on Boolean Matrices." Journal of the ACM 9(1), 11 à 12.
9. Johnson, D. B. (1973). "A Note on Dijkstra's Shortest Path Algorithm." Journal of the ACM 20(3), 385 à 388.
10. Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1), 1 à 13.
11. Fredman, M. L. et Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM 34(3), 596 à 615.
12. Moy, J. (1998). "OSPF Version 2." RFC 2328. Internet Engineering Task Force.
13. Malkin, G. (1998). "RIP Version 2." RFC 2453. Internet Engineering Task Force.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition. Cambridge, MA : MIT Press.
15. Frana, P. L. et Misa, T. J. (2010). "An Interview with Edsger W. Dijkstra." Communications of the ACM 53(8), 41 à 47.
16. Hougardy, S. (2010). "The Floyd-Warshall Algorithm on Graphs with Negative Cycles." Information Processing Letters 110(8 à 9), 279 à 281.
17. Sedgewick, R. et Wayne, K. (2011). Algorithms, 4e édition. Upper Saddle River, NJ : Addison-Wesley.
18. Schrijver, A. (2012). "On the History of the Shortest Path Problem." Documenta Mathematica, Extra Volume ISMP, 155 à 167.
19. Bernstein, A., Nanongkai, D. et Wulff-Nilsen, C. (2022). "Negative-Weight Single-Source Shortest Paths in Near-linear Time." Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science, 600 à 611.
20. Haeupler, B., Hladík, R., Rozhoň, V., Tarjan, R. E. et Tětek, J. (2024). "Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps." Proceedings of the 65th IEEE Symposium on Foundations of Computer Science, 2099 à 2130.
21. Duan, R., Mao, J., Mao, X., Shu, X. et Yin, L. (2025). "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths." Proceedings of the 57th ACM Symposium on Theory of Computing, 36 à 44.