Maîtriser les Algorithmes de Plus Court Chemin :
Dijkstra, Bellman-Ford et Floyd-Warshall

1. Introduction au Problème du Plus Court Chemin

Dans le vaste domaine de l'informatique, très peu de problèmes ont une applicabilité aussi universelle que le "Problème du Plus Court Chemin". Qu'il s'agisse de Google Maps calculant l'itinéraire le plus rapide pour rentrer chez soi dans les embouteillages, ou d'un routeur internet déterminant comment acheminer un paquet de données, les mathématiques sous-jacentes sont identiques.

Fondamentalement, le problème demande : Étant donné un graphe composé de nœuds (emplacements) et d'arêtes (chemins de connexion) où chaque arête se voit attribuer un "poids" (distance, temps ou coût), quel est le chemin d'un nœud de départ à un nœud de destination qui minimise le poids total ?

Bien que ce problème puisse paraître simple, la nature du graphe (s'il est orienté, s'il contient des poids négatifs ou s'il comporte des cycles) change radicalement la donne, nécessitant des approches algorithmiques complètement différentes. Dans ce guide, nous décomposerons les trois piliers des algorithmes de plus court chemin : Dijkstra, Bellman-Ford et Floyd-Warshall.

2. Algorithme de Dijkstra : Le Bourreau de Travail Glouton

Conçu par le légendaire informaticien néerlandais Edsger W. Dijkstra en 1956, cet algorithme est le roi incontesté du routage dans les réseaux informatiques et la navigation cartographique.

La Stratégie : L'algorithme de Dijkstra utilise une approche "gloutonne" (greedy). Il choisit toujours le nœud non visité qui est le plus proche de la source, explore ses voisins et met à jour leurs distances. Une fois qu'un nœud est traité, il est considéré comme terminé de manière permanente.

La Mécanique

Afin de trouver efficacement le nœud avec la plus petite distance connue actuellement, Dijkstra s'appuie fortement sur une File de Priorité (Priority Queue) (souvent implémentée comme un Min-Heap).

1. Attribuez à chaque nœud une valeur de distance initiale : 0 pour le nœud de départ, et Infini pour tous les autres.
2. Insérez le nœud de départ dans la file de priorité.
3. Tant que la file n'est pas vide, extrayez le nœud avec la plus petite distance.
4. Examinez tous les voisins non visités de ce nœud.
5. Calculez la distance de la source à chaque voisin en passant par le nœud actuel.
6. Si cette distance nouvellement calculée est inférieure à la distance connue du voisin, mettez à jour la distance du voisin et poussez-le dans la file de priorité.

Implémentation en Python

import heapq

def dijkstra(graph, start):
    # Initialise les distances à l'infini
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    
    # La file de priorité stocke des tuples de (distance, nœud)
    pq = [(0, start)]
    
    while pq:
        # Extraire le nœud avec la plus petite distance
        current_distance, current_vertex = heapq.heappop(pq)

        # Ignorer si nous avons déjà trouvé un meilleur chemin
        if current_distance > distances[current_vertex]:
            continue

        # Vérifier les voisins
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Si un chemin plus court est trouvé, mettre à jour
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

Le Défaut Fatal : Les Poids Négatifs

La nature gloutonne de Dijkstra est ce qui le rend incroyablement rapide (O((V + E) log V)). Cependant, cette avarice a un défaut fatal : elle suppose que l'ajout d'une arête à un chemin ne peut jamais rendre ce chemin plus court. Par conséquent, Dijkstra échoue lamentablement si le graphe contient des arêtes avec des poids négatifs, car une fois qu'un nœud est "terminé", il n'est jamais reconsidéré, même si une arête négative cachée devait le rendre moins coûteux plus tard.

3. Algorithme de Bellman-Ford : Gérer le Négatif

Lorsque vous ne pouvez pas garantir que les poids des arêtes sont tous positifs (par exemple, modéliser des transactions financières où certaines transactions génèrent des bénéfices au lieu de coûts), Bellman-Ford entre en scène. Alors que Dijkstra est un algorithme glouton, Bellman-Ford utilise une approche de Programmation Dynamique (Dynamic Programming).

La Stratégie : Au lieu de choisir intelligemment le nœud le plus proche, Bellman-Ford adopte une approche de marteau-piqueur : il "relâche" (met à jour les distances pour) simplement chaque arête du graphe. Et il fait cela V - 1 fois.

Pourquoi V - 1 Itérations ?

Le plus long chemin possible dans un graphe sans cycle peut comporter au maximum V - 1 arêtes (où V est le nombre de nœuds). En relâchant toutes les arêtes V - 1 fois, l'algorithme garantit que les distances se stabiliseront à leurs valeurs absolument les plus courtes, même si le chemin devait traverser un labyrinthe d'arêtes négatives.

Détection de Cycles Négatifs

Le plus grand super-pouvoir de Bellman-Ford est sa capacité à détecter les cycles de poids négatif. Si après V - 1 itérations, vous relâchez les arêtes une fois de plus et qu'une distance diminue encore, cela signifie que le graphe a un cycle négatif (une boucle infinie qui diminue le coût pour toujours, comme un arbitrage d'argent infini). Le "plus court chemin" est mathématiquement indéfini dans de tels cas.

Implémentation en Python

def bellman_ford(graph, V, start):
    # Initialiser les distances
    distances = {vertex: float('infinity') for vertex in range(V)}
    distances[start] = 0

    # Relâcher toutes les arêtes V - 1 fois
    for _ in range(V - 1):
        for u, v, w in graph:
            if distances[u] != float('infinity') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # Exécuter une V-ème fois pour vérifier les cycles négatifs
    for u, v, w in graph:
        if distances[u] != float('infinity') and distances[u] + w < distances[v]:
            print("Le graphe contient un cycle de poids négatif !")
            return None

    return distances

4. Algorithme de Floyd-Warshall : La Solution "Toutes Paires"

Dijkstra et Bellman-Ford sont tous deux des algorithmes de plus court chemin à source unique (ils trouvent le chemin d'un point de départ vers tous les autres points). Et si vous aviez besoin de connaître le plus court chemin de chaque nœud à chaque autre nœud simultanément ?

L'algorithme de Floyd-Warshall offre une alternative incroyablement élégante. C'est une autre approche de Programmation Dynamique, mais elle opère sur l'ensemble de la matrice d'adjacence du graphe.

La Stratégie : Floyd-Warshall vérifie systématiquement si prendre la route via un nœud intermédiaire k est plus court que la route actuellement connue du nœud i au nœud j.

L'élégance de cet algorithme réside dans ses trois boucles imbriquées remarquablement simples. Il est extrêmement facile à implémenter et est excellent pour les graphes denses.

Implémentation en Python

def floyd_warshall(graph_matrix, V):
    # Créer une copie de la matrice du graphe pour stocker les distances
    dist = [[float('infinity') for _ in range(V)] for _ in range(V)]
    
    # Établir les cas de base
    for i in range(V):
        dist[i][i] = 0
    for u in range(V):
        for v in range(V):
            if graph_matrix[u][v] != 0:
                dist[u][v] = graph_matrix[u][v]

    # L'algorithme principal
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # Si le chemin via 'k' est plus court, mettre à jour le chemin
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                
    return dist

5. Comparaison Complète