Présentation du problème

Ce type d'exercice est très fréquent à partir du niveau 4 sur France IOI. On vous donne un graphe non orienté non pondéré (ou une grille), et on vous demande de trouver la distance minimale (en nombre d'arêtes) entre deux sommets donnés.

Ce problème se résout élégamment avec le BFS (Breadth-First Search, ou parcours en largeur), qui est l'outil canonique pour les plus courts chemins sur graphes non pondérés.

Énoncé typique

On vous donne un graphe de N sommets et M arêtes, ainsi qu'un sommet source S et un sommet destination D. Trouvez la longueur du plus court chemin de S à D. Si aucun chemin n'existe, affichez -1.

Pourquoi le BFS et pas le DFS ?

Le DFS (parcours en profondeur) explore les chemins jusqu'au bout avant de revenir en arrière — il ne garantit pas de trouver le chemin le plus court. Le BFS, en revanche, explore les sommets couche par couche (d'abord tous les voisins à distance 1, puis à distance 2, etc.), ce qui garantit que le premier chemin trouvé vers la destination est le plus court.

Implémentation en Python


from collections import deque

def bfs(graphe, source, destination, n):
    distance = [-1] * (n + 1)  # -1 = non visité
    distance[source] = 0
    file = deque([source])

    while file:
        sommet = file.popleft()
        for voisin in graphe[sommet]:
            if distance[voisin] == -1:  # Non visité
                distance[voisin] = distance[sommet] + 1
                file.append(voisin)
                if voisin == destination:
                    return distance[voisin]
    return -1  # Destination inaccessible

# Lecture des entrées
n, m = map(int, input().split())
graphe = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graphe[u].append(v)
    graphe[v].append(u)  # Non orienté

s, d = map(int, input().split())
print(bfs(graphe, s, d, n))

Explication détaillée

  1. Tableau de distances : on initialise toutes les distances à -1 (non visité), sauf la source qui est à distance 0.
  2. File (deque) : on utilise une file double-ended pour enfiler/défiler efficacement en O(1).
  3. Exploration : pour chaque sommet extrait de la file, on examine ses voisins. Si un voisin n'a pas encore été visité, on lui assigne distance[sommet] + 1 et on l'ajoute à la file.
  4. Arrêt anticipé : dès qu'on atteint la destination, on retourne immédiatement — c'est forcément le chemin le plus court.

Implémentation en C++


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graphe(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graphe[u].push_back(v);
        graphe[v].push_back(u);
    }

    int s, d;
    cin >> s >> d;

    vector<int> dist(n + 1, -1);
    dist[s] = 0;
    queue<int> file;
    file.push(s);

    while (!file.empty()) {
        int sommet = file.front();
        file.pop();
        for (int voisin : graphe[sommet]) {
            if (dist[voisin] == -1) {
                dist[voisin] = dist[sommet] + 1;
                file.push(voisin);
            }
        }
    }

    cout << dist[d] << endl;
    return 0;
}

Cas particuliers à gérer

  • Source == Destination : la distance est 0, vérifiez avant de lancer le BFS.
  • Graphe non connexe : si la destination n'est jamais atteinte, dist[d] reste à -1.
  • Grilles 2D : le BFS s'applique aussi aux grilles en modélisant chaque case comme un sommet avec jusqu'à 4 voisins (haut, bas, gauche, droite).

Complexité

  • Temps : O(N + M) — chaque sommet et chaque arête est visitée au plus une fois.
  • Espace : O(N + M) — pour stocker le graphe et les distances.

Conclusion

Le BFS est un algorithme fondamental pour les graphes. Sa maîtrise vous permettra de résoudre une grande variété d'exercices sur France IOI et au-delà. Entraînez-vous sur des variantes : graphes dirigés, grilles avec obstacles, chemins avec contraintes.