Algorithme de Bellman-Ford

L'algorithme de Bellman-Ford calcule les plus courts chemins depuis une source unique dans un graphe pondéré, même avec des poids négatifs (ce que Dijkstra ne permet pas). Il détecte également les cycles négatifs.

Principe

L'algorithme procède par relaxation répétée de toutes les arêtes. Après $|V|-1$ itérations sur l'ensemble des arêtes, tous les plus courts chemins sont trouvés (si le graphe ne contient pas de cycle de poids négatif accessible depuis la source).

Une itération supplémentaire permet de détecter un cycle négatif : si une relaxation est encore possible, c'est qu'il y a un tel cycle.

Pseudocode

function BellmanFord(Graph, source):
    distance[v] = infinity for all v
    distance[source] = 0

    for i from 1 to |V|-1:
        for each edge (u, v) with weight w in Graph:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w

    # Vérification cycle négatif
    for each edge (u, v) with weight w:
        if distance[u] + w < distance[v]:
            return "Cycle négatif détecté"

    return distance

Complexité

Avec $|V|$ sommets et $|E|$ arêtes : $O(|V| \cdot |E|)$. Moins efficace que Dijkstra en $O((|V| + |E|) \log |V|)$ pour les graphes à poids positifs, mais plus général.

Applications

• Routage réseau (protocole RIP)
• Arbitrage sur marchés financiers (détection d'opportunités d'arbitrage via cycle négatif sur les logs de taux de change)
• Ordonnancement avec contraintes de précédence où certains poids sont négatifs

Démonstration de correction

Pourquoi $|V|-1$ itérations suffisent-elles ? C'est une conséquence de la propriété suivante :

Après $i$ itérations de relaxation sur toutes les arêtes, la distance calculée à chaque sommet $v$ est inférieure ou égale à la distance du plus court chemin depuis la source à $v$ utilisant au plus $i$ arêtes.

Comme un plus court chemin dans un graphe sans cycle négatif a au plus $|V| - 1$ arêtes, après $|V| - 1$ itérations toutes les distances correctes sont trouvées.

Détection de cycle négatif

Si à la $|V|$-ième itération on peut encore relaxer une arête, c'est qu'il existe un cycle de poids négatif accessible depuis la source. La démonstration est simple : sans cycle négatif, les distances seraient stables après $|V|-1$ itérations.

Pour retrouver le cycle lui-même, on note l'arête $(u, v)$ qui a permis la relaxation. En remontant les prédécesseurs depuis $v$, on trouve le cycle au bout d'au plus $|V|$ étapes.

Variantes : Floyd-Warshall

Bellman-Ford calcule les plus courts chemins depuis une source unique. Pour toutes les paires, on utilise Floyd-Warshall : complexité $O(|V|^3)$, également résistant aux poids négatifs (mais pas aux cycles négatifs).

Pour les très grands graphes, Johnson combine Bellman-Ford et Dijkstra pour descendre à $O(|V| |E| \log |V|)$ en toutes paires.

Une question ou une suggestion ? Écrivez-nous.