Pourquoi Dijkstra ne fonctionne-t-il pas avec des poids négatifs ?

L'algorithme de Dijkstra est glouton : une fois qu'un sommet est marqué comme 'visité', sa distance est considérée comme définitive. Si une arête de poids négatif apparaît plus tard, elle pourrait créer un chemin plus court vers un sommet déjà visité, invalident l'hypothèse de l'algorithme. Pour les graphes avec poids négatifs, il faut utiliser l'algorithme de Bellman-Ford.

Quelle est la différence entre BFS (parcours en largeur) et Dijkstra ?

Le BFS trouve le chemin avec le moins d'étapes (ou arêtes) dans un graphe non pondéré (où toutes les arêtes ont le même poids, souvent 1). Dijkstra, lui, trouve le chemin de poids minimal dans un graphe pondéré avec des poids positifs. En quelque sorte, Dijkstra est une généralisation de BFS pour des poids variables.

Comment faire pour retrouver le chemin et pas seulement la distance ?

Il faut ajouter un dictionnaire 'predecessors' (prédécesseurs). Chaque fois que tu mets à jour la distance d'un voisin ( distances[neighbor] = distance ), tu enregistres aussi son prédécesseur : predecessors[neighbor] = current_node . À la fin, pour reconstruire le chemin d'un sommet à la source, il suffit de remonter la chaîne des prédécesseurs.

Quelle est la complexité de l'implémentation avec le tas (heap) ?

Avec une file de priorité implémentée par un tas binaire (comme dans heapq ), la complexité est en O((V + E) log V), où V est le nombre de sommets et E le nombre d'arêtes. C'est bien plus efficace qu'avec un tableau simple (O(V²)), surtout pour les graphes peu denses (où E est bien inférieur à V²).

Algorithme de Dijkstra : trouver le plus court chemin

Qu'est-ce que l'algorithme de Dijkstra ?

Imagine que tu dois te rendre d'un point A à un point B dans une ville. Tu as plusieurs routes possibles, certaines plus rapides que d'autres. Comment trouver le trajet le plus court ? C'est exactement le problème que résout l'algorithme de Dijkstra, conçu par l'informaticien néerlandais Edsger Dijkstra en 1956. C'est un algorithme glouton qui calcule les plus courts chemins depuis un sommet source vers tous les autres sommets dans un graphe pondéré dont les arêtes ont des poids positifs ou nuls.

En NSI, tu étudieras cet algorithme comme un classique de la théorie des graphes. Il est utilisé partout : dans les systèmes de navigation GPS (comme Google Maps), pour le routage sur Internet, ou même dans la planification de réseaux. Comprendre Dijkstra, c'est comprendre une brique fondamentale de l'informatique.

Le principe pas à pas

L'algorithme fonctionne de manière itérative. Voici son déroulement en langage naturel :

Initialisation : On part d'un sommet de départ (la source). On lui attribue une distance de 0. À tous les autres sommets, on attribue une distance infinie (ou une très grande valeur). On marque tous les sommets comme "non visités".
Sélection : Parmi les sommets non visités, on choisit celui qui a la plus petite distance actuellement estimée.
Exploration : Pour chaque voisin de ce sommet sélectionné, on calcule la distance depuis la source en passant par ce sommet. Si cette nouvelle distance est plus petite que celle déjà enregistrée pour le voisin, on met à jour sa distance.
Marquage : On marque le sommet sélectionné comme "visité". Un sommet visité a sa distance minimale définitivement connue.
Répétition : On répète les étapes de sélection, exploration et marquage jusqu'à ce que tous les sommets soient visités (ou jusqu'à ce que le sommet d'arrivée soit visité si on ne cherche qu'un seul chemin).

L'idée clé est que l'algorithme "étend" progressivement la zone pour laquelle le plus court chemin est connu, en partant de la source. C'est un algorithme glouton car à chaque étape, il fait le choix localement optimal (prendre le sommet non visité le plus proche) en espérant que cela mène à la solution globale optimale.

Implémentation en Python

Voyons maintenant comment coder cet algorithme en Python. Nous allons utiliser une représentation du graphe par liste d'adjacence avec des dictionnaires. Pour sélectionner efficacement le sommet non visité le plus proche, nous utiliserons un tas (heap) via le module heapq. Cela améliore grandement la complexité.

Représentation du graphe

Nous représenterons le graphe comme un dictionnaire où les clés sont les sommets, et les valeurs sont des listes de tuples (voisin, poids).

Exemple : graph['A'] = [('B', 4), ('C', 2)] signifie qu'il y a une arête de A vers B de poids 4, et de A vers C de poids 2.

Code de l'algorithme

Voici une implémentation complète et commentée :

import heapq
def dijkstra(graph, start):
    """
    Calcule les distances minimales du sommet `start` à tous les autres.
    Retourne un dictionnaire {sommet: distance}.
    """
    # Initialisation : distances infinies sauf pour le départ
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # File de priorité (tas) : (distance, sommet)
    priority_queue = [(0, start)]
    
    while priority_queue:
        # On extrait le sommet avec la plus petite distance actuelle
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # Si la distance extraite est supérieure à celle enregistrée,
        # c'est une entrée obsolète, on l'ignore.
        if current_distance > distances[current_node]:
            continue
        
        # On explore les voisins du sommet courant
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            # Si on trouve un chemin plus court, on met à jour
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

Cette fonction retourne un dictionnaire des distances minimales. Pour reconstruire les chemins eux-mêmes (et pas seulement leur longueur), il faudrait aussi mémoriser le prédécesseur de chaque sommet lors de la mise à jour.

Complexité et limites

La complexité de l'algorithme dépend de la structure de données utilisée pour la file de priorité :

Avec un tableau simple pour chercher le minimum : O(V²) où V est le nombre de sommets. C'est simple mais lent pour les grands graphes.
Avec un tas binaire (comme dans notre code) : O((V+E) log V) où E est le nombre d'arêtes. C'est bien plus efficace !

Attention à une limite importante : l'algorithme de Dijkstra ne fonctionne pas avec des poids négatifs sur les arêtes. Pourquoi ? Parce que l'algorithme, étant glouton, considère qu'une distance minimale est définitive une fois le sommet visité. Un poids négatif plus loin dans le graphe pourrait invalider ce choix. Pour les graphes avec poids négatifs, il faut utiliser l'algorithme de Bellman-Ford.

Un exemple concret avec Python

Appliquons notre code à un graphe simple. Imaginons un petit réseau routier :

# Définition du graphe
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('B', 1), ('D', 8), ('E', 10)],
    'D': [('E', 2)],
    'E': []
}

# Calcul des distances depuis 'A'
distances = dijkstra(graph, 'A')
print("Distances depuis A :", distances)
# Résultat attendu : {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}

Déroulons l'algorithme mentalement : depuis A (0), on peut aller en C (2) et en B (4). Le plus proche est C. Depuis C, on met à jour B (2+1=3, ce qui est mieux que 4) et D (2+8=10) et E (2+10=12). Ensuite, le plus proche non visité est B (3). Depuis B, on met à jour D (3+5=8, ce qui est mieux que 10). Et ainsi de suite.

Tu peux tester ce code sur Python Tutor pour visualiser son exécution pas à pas !

Pour aller plus loin en NSI

Maîtriser Dijkstra ouvre la porte à d'autres concepts :

L'algorithme A* (A-star) : une extension de Dijkstra qui utilise une heuristique pour se diriger plus vite vers la cible, très utilisée en intelligence artificielle pour les jeux vidéo.
Les arbres couvrants de poids minimum avec l'algorithme de Prim, qui a une structure similaire.
La différence fondamentale avec l'algorithme de Bellman-Ford qui gère les poids négatifs.

Pour t'entraîner, cherche des problèmes sur France-ioi ou sur des plateformes comme CodinGame qui impliquent des plus courts chemins. Tu peux aussi essayer de modifier le code pour qu'il retourne non seulement les distances, mais aussi les chemins complets.