L'algorithme de Bellman-Ford est un algorithme de calcul des plus courts chemins depuis une source unique dans un graphe pondéré. Développé par Richard Bellman et Lester Ford dans les années 1950, il constitue une alternative plus robuste mais moins efficace que l'algorithme de Dijkstra.

Problème traitéÉtant donné un graphe orienté ou non orienté \(G = (S, A)\) avec une fonction de pondération \(w : A \to \mathbb{R}\), et un sommet source \(s \in S\), l'algorithme détermine :

la distance minimale \(d(v)\) de \(s\) à chaque sommet \(v\),
le chemin correspondant (via les prédécesseurs \(\pi(v)\)).

Pourquoi Bellman-Ford ?

L'algorithme de Dijkstra est très efficace (\(O(|A| \log |S|)\) avec une file de priorité) mais il présente une limitation fondamentale :

Limite de Dijkstra Dijkstra ne fonctionne correctement qu'avec des poids positifs ou nuls. Sa logique gloutonne repose sur l'hypothèse qu'une fois qu'un sommet est traité, sa distance est définitive, ce qui n'est pas garanti en présence de poids négatifs.

Bellman-Ford lève cette limitation en acceptant des poids négatifs, ce qui le rend indispensable dans certains contextes :

Réseaux avec coûts variables (certaines liaisons peuvent générer des bénéfices)
Change de devises (recherche d'arbitrages rentables)
Détection de cycles absorbants (circuits dont le coût total est négatif)

Inconvénient majeur

Cette robustesse a un coût : Bellman-Ford est moins efficace que Dijkstra avec une complexité en \(O(|S| \times |A|)\).

Principe de l'algorithme

Bellman-Ford repose sur une idée simple mais puissante : le relâchement itératif de toutes les arêtes.

Intuition Dans un graphe sans cycle négatif, le plus court chemin entre deux sommets contient au plus \(|S| - 1\) arêtes. En répétant \(|S| - 1\) fois l'opération de relâchement sur toutes les arêtes, on propage progressivement les informations de distance à travers le graphe.

Structures de données maintenues

\(d[v]\) : distance provisoire de la source \(s\) au sommet \(v\) (initialisée à \(+\infty\), sauf \(d[s] = 0\)).
\(\pi[v]\) : prédécesseur de \(v\) dans le chemin courant (pour reconstruire le chemin).

L'opération fondamentale : le relâchement

Relâchement d'une arête Pour une arête \((u, v)\) de poids \(w(u, v)\), on vérifie si passer par \(u\) améliore la distance vers \(v\) : \[ \text{si } d(v) > d(u) + w(u, v) \quad \Rightarrow \quad \begin{cases} d(v) \leftarrow d(u) + w(u, v) \\ \pi[v] \leftarrow u \end{cases} \]

Déroulement de l'algorithme

Étapes principales

Initialisation : \(d[s] = 0\), \(d[v] = +\infty\) pour \(v \neq s\), \(\pi[v] = \text{None}\).
Relâchements itératifs: répéter \(|S| - 1\) fois :
- Pour chaque arête \((u, v) \in A\), relâcher \((u, v)\).
Détection de cycles négatifs : une dernière passe sur toutes les arêtes pour vérifier si un relâchement est encore possible. Si oui, un cycle absorbant existe.

Algorithme en pseudo-code

Bellman-Ford Pseudo-code

Entrée : Graphe G = (S, A), source s
Sortie : distances d, prédécesseurs π, indicateur de cycle négatif

// Initialisation
Pour tout v ∈ S :
    d[v] ← +∞
    π[v] ← None
d[s] ← 0

// Relâchements itératifs
Pour i de 1 à |S| - 1 :
    Pour toute arête (u, v) ∈ A :
        Si d[u] + w(u,v) < d[v] :
            d[v] ← d[u] + w(u,v)
            π[v] ← u

// Détection de cycle négatif
Pour toute arête (u, v) ∈ A :
    Si d[u] + w(u,v) < d[v] :
        Retourner "Cycle négatif détecté"

Retourner d, π

Exemple détaillé

Considérons le graphe orienté suivant avec des poids pouvant être négatifs, et appliquons Bellman-Ford à partir du sommet \(A\).

Arêtes et poids :

A → B : 4
A → C : 5
B → D : 3
C → E : 6
D → E : -3
E → F : 2
F → C : 1

Étape 0 : Initialisation

Sommet	A	B	C	D	E	F
d	0	∞	∞	∞	∞	∞
π	None	None	None	None	None	None

Itération 1 (i = 1)

On relâche toutes les arêtes dans l'ordre :

Arête	Condition	Mise à jour
A→B (4)	d[A] + 4 = 4 < ∞	d[B] = 4, π[B] = A
A→C (5)	d[A] + 5 = 5 < ∞	d[C] = 5, π[C] = A
B→D (3)	d[B] + 3 = 7 < ∞	d[D] = 7, π[D] = B
C→E (6)	d[C] + 6 = 11 < ∞	d[E] = 11, π[E] = C
D→E (-3)	d[D] + (-3) = 4 < 11	d[E] = 4, π[E] = D
E→F (2)	d[E] + 2 = 6 < ∞	d[F] = 6, π[F] = E
F→C (1)	d[F] + 1 = 7 < 5 ?	Non (7 > 5)

État après itération 1 :

Sommet	A	B	C	D	E	F
d	0	4	5	7	4	6
π	None	A	A	B	D	E

Itération 2 (i = 2)

On relâche toutes les arêtes à nouveau :

Arête	Condition	Mise à jour
A→B (4)	0+4 = 4 ≮ 4	Non
A→C (5)	0+5 = 5 ≮ 5	Non
B→D (3)	4+3 = 7 ≮ 7	Non
C→E (6)	5+6 = 11 ≮ 4	Non
D→E (-3)	7-3 = 4 ≮ 4	Non
E→F (2)	4+2 = 6 ≮ 6	Non
F→C (1)	6+1 = 7 > 5	Non

Aucune mise à jour lors de l'itération 2. L'algorithme pourrait s'arrêter plus tôt (optimisation possible).

Itération 3 à 5

Aucune modification supplémentaire. Les distances sont stables.

Détection de cycle négatif

On vérifie une dernière fois toutes les arêtes : aucune amélioration possible → pas de cycle négatif.

Résultats finaux

Sommet	Distance depuis A	Chemin
A	0	A
B	4	A → B
C	5	A → C
D	7	A → B → D
E	4	A → B → D → E
F	6	A → B → D → E → F

Détection des cycles absorbants

L'un des atouts majeurs de Bellman-Ford est sa capacité à détecter la présence de cycles négatifs (cycles dont la somme des poids est négative).

Cycle négatif (absorbant) Un cycle \(C = (v_0, v_1, \dots, v_k = v_0)\) est dit négatif si : \[ \sum_{i=0}^{k-1} w(v_i, v_{i+1}) < 0 \] Dans un tel cycle, on peut tourner indéfiniment pour diminuer le coût, rendant la notion de "plus court chemin" non définie.

Exemple de cycle négatif

Cycle A → C → B → A : \(5 + (-10) + 3 = -2\) → cycle négatif.

Si un tel cycle est accessible depuis la source, les distances peuvent devenir arbitrairement petites (−∞).

Implémentations

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define INF INT_MAX

// Structure pour représenter une arête
typedef struct {
    int u;      // sommet source
    int v;      // sommet destination
    int poids;
} Arete;

// Structure pour représenter un graphe
typedef struct {
    int n;              // nombre de sommets
    int m;              // nombre d'arêtes
    Arete* aretes;      // tableau d'arêtes
} Graphe;

// Créer un graphe avec n sommets et m arêtes
Graphe* creerGraphe(int n, int m) {
    Graphe* graphe = (Graphe*)malloc(sizeof(Graphe));
    graphe->n = n;
    graphe->m = m;
    graphe->aretes = (Arete*)malloc(m * sizeof(Arete));
    return graphe;
}

// Algorithme de Bellman-Ford
bool bellmanFord(Graphe* graphe, int source, int dist[], int pred[]) {
    int n = graphe->n;
    int m = graphe->m;
    
    // Initialisation
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        pred[i] = -1;
    }
    dist[source] = 0;
    
    // Relâchements itératifs (n-1 fois)
    for (int i = 1; i <= n-1; i++) {
        bool misAJour = false;
        
        for (int j = 0; j < m; j++) {
            int u = graphe->aretes[j].u;
            int v = graphe->aretes[j].v;
            int poids = graphe->aretes[j].poids;
            
            if (dist[u] != INF && dist[u] + poids < dist[v]) {
                dist[v] = dist[u] + poids;
                pred[v] = u;
                misAJour = true;
            }
        }
        
        // Optimisation : si aucune mise à jour, on peut s'arrêter
        if (!misAJour) break;
    }
    
    // Détection de cycle négatif
    for (int j = 0; j < m; j++) {
        int u = graphe->aretes[j].u;
        int v = graphe->aretes[j].v;
        int poids = graphe->aretes[j].poids;
        
        if (dist[u] != INF && dist[u] + poids < dist[v]) {
            return false; // Cycle négatif détecté
        }
    }
    
    return true; // Pas de cycle négatif
}

// Fonction pour reconstruire et afficher le chemin
void afficherChemin(int pred[], int source, int dest) {
    if (dest == source) {
        printf("%d", source);
        return;
    }
    
    if (pred[dest] == -1) {
        printf("Pas de chemin");
        return;
    }
    
    afficherChemin(pred, source, pred[dest]);
    printf(" -> %d", dest);
}

int main() {
    // Création du graphe exemple
    int n = 6; // A=0, B=1, C=2, D=3, E=4, F=5
    int m = 7;
    
    Graphe* graphe = creerGraphe(n, m);
    
    // Définition des arêtes
    graphe->aretes[0] = (Arete){0, 1, 4};   // A->B
    graphe->aretes[1] = (Arete){0, 2, 5};   // A->C
    graphe->aretes[2] = (Arete){1, 3, 3};   // B->D
    graphe->aretes[3] = (Arete){2, 4, 6};   // C->E
    graphe->aretes[4] = (Arete){3, 4, -3};  // D->E (-3)
    graphe->aretes[5] = (Arete){4, 5, 2};   // E->F
    graphe->aretes[6] = (Arete){5, 2, 1};   // F->C
    
    int dist[n];
    int pred[n];
    
    printf("Bellman-Ford depuis le sommet 0 (A) :\n\n");
    
    if (bellmanFord(graphe, 0, dist, pred)) {
        printf("Distances minimales :\n");
        for (int i = 0; i < n; i++) {
            printf("  Vers %d : %d\t", i, dist[i]);
            printf("Chemin : ");
            afficherChemin(pred, 0, i);
            printf("\n");
        }
    } else {
        printf("Cycle négatif détecté !\n");
    }
    
    // Test avec un cycle négatif
    printf("\n--- Test avec cycle négatif ---\n");
    graphe->aretes[4] = (Arete){3, 4, -10}; // D->E (-10) pour créer un cycle négatif
    
    if (bellmanFord(graphe, 0, dist, pred)) {
        printf("Distances minimales :\n");
        for (int i = 0; i < n; i++) {
            printf("  Vers %d : %d\n", i, dist[i]);
        }
    } else {
        printf("Cycle négatif détecté !\n");
    }
    
    return 0;
}

def bellman_ford(graphe, source):
    """
    Implémentation de l'algorithme de Bellman-Ford.
    
    Paramètres:
    graphe : liste des arêtes sous forme (u, v, poids)
    source : sommet de départ
    
    Retourne:
    (dist, pred, cycle) où dist est le tableau des distances,
    pred le tableau des prédécesseurs, et cycle un booléen
    indiquant la présence d'un cycle négatif.
    """
    n = len(graphe)  # Nombre de sommets (supposé correct)
    m = len(graphe)  # Nombre d'arêtes
    
    # 1. Initialisation
    dist = [float('inf')] * n
    pred = [None] * n
    dist[source] = 0
    
    # 2. Relâchements itératifs (n-1 fois)
    for i in range(n-1):
        mis_a_jour = False
        for u, v, poids in graphe:
            if dist[u] != float('inf') and dist[u] + poids < dist[v]:
                dist[v] = dist[u] + poids
                pred[v] = u
                mis_a_jour = True
        
        # Optimisation : si aucune mise à jour, on peut s'arrêter
        if not mis_a_jour:
            break
    
    # 3. Détection de cycle négatif
    for u, v, poids in graphe:
        if dist[u] != float('inf') and dist[u] + poids < dist[v]:
            return dist, pred, True  # Cycle négatif détecté
    
    return dist, pred, False  # Pas de cycle négatif


def reconstruire_chemin(pred, source, dest):
    """Reconstruit le chemin de source à destination."""
    chemin = []
    courant = dest
    
    while courant is not None:
        chemin.insert(0, courant)
        courant = pred[courant]
    
    return chemin if chemin[0] == source else None


# Exemple d'utilisation
graphe = [
    (0, 1, 4),   # A -> B : 4
    (0, 2, 5),   # A -> C : 5
    (1, 3, 3),   # B -> D : 3
    (2, 4, 6),   # C -> E : 6
    (3, 4, -3),  # D -> E : -3
    (4, 5, 2),   # E -> F : 2
    (5, 2, 1),   # F -> C : 1
]

print("=== Bellman-Ford depuis A (0) ===")
dist, pred, cycle = bellman_ford(graphe, 0)

if cycle:
    print("⚠Cycle négatif détecté !")
else:
    print("\nDistances minimales :")
    sommets = ['A', 'B', 'C', 'D', 'E', 'F']
    for i in range(len(dist)):
        print(f"  Vers {sommets[i]} : {dist[i]}")
        
        chemin = reconstruire_chemin(pred, 0, i)
        if chemin:
            print(f"    Chemin : {' → '.join([sommets[s] for s in chemin])}")

print("\n=== Test avec cycle négatif ===")
graphe_cycle = graphe.copy()
graphe_cycle[4] = (3, 4, -10)  # D -> E : -10 (crée un cycle négatif)

dist, pred, cycle = bellman_ford(graphe_cycle, 0)
print("Cycle négatif détecté !" if cycle else "Pas de cycle négatif")

Sortie

=== Bellman-Ford depuis A (0) ===

Distances minimales :
  Vers A : 0
    Chemin : A
  Vers B : 4
    Chemin : A → B
  Vers C : 5
    Chemin : A → C
  Vers D : 7
    Chemin : A → B → D
  Vers E : 4
    Chemin : A → B → D → E
  Vers F : 6
    Chemin : A → B → D → E → F

=== Test avec cycle négatif ===
Cycle négatif détecté !

Analyse de complexité

Opération	Complexité	Explication
Initialisation	\(O(\|S\|)\)	Initialisation des tableaux de distance et prédécesseurs
Relâchements itératifs	\(O(\|S\| \times \|A\|)\)	\(\|S\|-1\) passes sur les \(\|A\|\) arêtes
Détection de cycle	\(O(\|A\|)\)	Une dernière passe sur toutes les arêtes
Complexité totale	\(O(\|S\| \times \|A\|)\)	Dans le pire cas
Complexité spatiale	\(O(\|S\|)\)	Stockage des distances et prédécesseurs

Comparaison avec l'algorithme de Dijkstra

Critère	Dijkstra	Bellman-Ford
Poids négatifs	Non supportés	Supportés
Détection cycles négatifs	Impossible	Possible
Complexité	\(O(\|A\| \log \|S\|)\) (avec tas)	\(O(\|S\| \times \|A\|)\)
Structure de données	File de priorité	Simple tableau
Paradigme	Glouton	Programmation dynamique

Quand utiliser Bellman-Ford ?

Bonnes pratiques

À utiliser quand :
- Le graphe contient des poids négatifs
- On doit détecter des cycles négatifs
- Le graphe est petit (complexité \(O(|S| \times |A|)\) acceptable)
À éviter quand :
- Tous les poids sont positifs (préférer Dijkstra)
- Le graphe est très grand (la complexité devient prohibitive)
- On a besoin de performances optimales

Variantes et optimisations

Arrêt précoce : Si une itération complète ne produit aucune mise à jour, on peut arrêter l'algorithme plus tôt.
File d'attente (SPFA - Shortest Path Faster Algorithm) : Une variante qui utilise une file pour ne relâcher que les sommets dont la distance a été modifiée, améliorant les performances en pratique.
Détection de cycles négatifs avec BFS : Pour identifier les sommets affectés par un cycle négatif.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Algorithme de chemin le plus court de Bellman-Ford

Algorithme de Bellman-Ford

Introduction et contexte

Pourquoi Bellman-Ford ?

Inconvénient majeur

Principe de l'algorithme

Structures de données maintenues

L'opération fondamentale : le relâchement

Déroulement de l'algorithme

Étapes principales

Algorithme en pseudo-code

Étape 0 : Initialisation

Itération 1 (i = 1)

Itération 2 (i = 2)

Itération 3 à 5

Détection de cycle négatif

Résultats finaux

Détection des cycles absorbants

Implémentations

Analyse de complexité

Comparaison avec l'algorithme de Dijkstra

Quand utiliser Bellman-Ford ?

Variantes et optimisations

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Algorithme de chemin le plus court de Bellman-Ford

Algorithme de Bellman-Ford

Introduction et contexte

Pourquoi Bellman-Ford ?

Inconvénient majeur

Principe de l'algorithme

Structures de données maintenues

L'opération fondamentale : le relâchement

Déroulement de l'algorithme

Étapes principales

Algorithme en pseudo-code

Étape 0 : Initialisation

Itération 1 (i = 1)

Itération 2 (i = 2)

Itération 3 à 5

Détection de cycle négatif

Résultats finaux

Détection des cycles absorbants

Implémentations

Analyse de complexité

Comparaison avec l'algorithme de Dijkstra

Quand utiliser Bellman-Ford ?

Variantes et optimisations

Discussion (0)

Laisser un commentaire