Les graphes : ce que les parcours calculent

Le module précédent a montré comment visiter tous les sommets. Celui-ci ne visite rien de nouveau : il change ce qu'on fait pendant la visite, et c'est de là que sortent la détection de cycle, le tri des tâches, les composantes — puis, quand les arcs portent des poids, les deux algorithmes de plus court chemin que le cours exige.

Du parcours à l'algorithme

Le module Les graphes : représenter et parcourir s'est terminé sur un patron unique, dont les deux parcours ne sont que deux réglages. Ce module s'ouvre en le reprenant, parce que les quatre premiers algorithmes qui suivent en sont des variantes — et qu'il vaut mieux voir la variante que réapprendre un code.

marquer(depart);
attente.ajouter(depart);

while (!attente.vide()) {
    u = attente.retirer();       // file -> largeur ; pile -> profondeur
    traiter(u);                  // <-- TOUT CE MODULE TIENT ICI

    for (int v : voisins[u]) {
        if (!marque(v)) { marquer(v); attente.ajouter(v); }
    }
}

Un mot sur le graphe qui servira d'exemple : c'est celui du module précédent, six sommets A à F et sept arcs — A→B, A→D, B→C, B→E, C→F, D→E, E→F. On le retrouvera pondéré dans la seconde moitié, et augmenté de deux arcs de retour pour la section sur les composantes. Reprendre la même topologie évite d'avoir à la réapprendre à chaque section.

Détecter un cycle

Première variante, et la plus subtile des quatre, parce qu'elle repose sur une distinction que le tableau visite ne sait pas faire à lui seul.

Reprends l'explorateur de grottes. Tu avances, et tu débouches sur une salle où tu es déjà passé. Deux situations complètement différentes se cachent derrière ce « déjà passé ». Ou bien cette salle est sur ton chemin actuel — tu peux revenir à ton point de départ sans faire demi-tour, donc tu as bouclé. Ou bien tu l'as explorée et quittée plus tôt : tu viens seulement de retomber dessus par un autre couloir, et ce n'est pas une boucle, c'est un raccourci.

Un booléen ne distingue pas les deux. Il en faut un second, qui ne dit pas « visité » mais « actuellement sur la pile » — donc mis à vrai en entrant et remis à faux en sortant.

// Deux tableaux, deux questions différentes :
//   visite[u]  — « u a-t-il DÉJÀ été exploré ? »   (ne redevient jamais faux)
//   surPile[u] — « u est-il SUR le chemin actuel ? » (redevient faux en sortant)
bool aUnCircuit(int u, const vector<vector<int>>& voisins,
                vector<bool>& visite, vector<bool>& surPile) {
    visite[u]  = true;
    surPile[u] = true;              // on ENTRE dans u

    for (int v : voisins[u]) {
        if (!visite[v]) {
            if (aUnCircuit(v, voisins, visite, surPile)) return true;
        } else if (surPile[v]) {
            return true;            // v est sur le chemin courant : circuit
        }
        // sinon : v est visité mais SORTI. Simple raccourci, on l'ignore.
    }

    surPile[u] = false;             // on SORT de u : il quitte le chemin
    return false;
}

Les deux lignes qui comptent sont surPile[u] = true en entrée et surPile[u] = false juste avant le return : elles encadrent exactement la durée pendant laquelle u est sur la pile d'appels.

Sur le graphe d'exemple, l'algorithme répond faux : le parcours descend A→B→C→F, ressort de F, ressort de C, essaie E depuis B, y trouve F déjà visité — mais surPile[F] est redevenu faux quand on est sorti de F. C'est le cas « raccourci », et sans le second tableau on aurait annoncé un circuit qui n'existe pas.

Le tri topologique

Deuxième variante, et celle qui rapporte le plus par rapport à ce qu'elle coûte : une ligne déplacée.

Ce graphe sans circuit a un nom qu'il faut connaître, parce que les énoncés l'emploient sans le développer : un DAG, pour directed acyclic graph — graphe orienté acyclique. Le graphe d'exemple en est un, et c'est ce que la section précédente vient de vérifier.

L'algorithme tient dans une observation, et elle vient tout droit du dernier exercice du module précédent. Quand un parcours en profondeur sort d'un sommet, tous les sommets qu'il pouvait atteindre sont déjà sortis. Dans un graphe de préalables, cela veut dire : tout ce qui dépend de lui est déjà traité. Il faut donc le placer avant eux — c'est-à-dire prendre l'ordre de sortie, et le renverser.

void visiterPourTri(int u, const vector<vector<int>>& voisins,
                    vector<bool>& visite, stack<int>& ordre) {
    visite[u] = true;
    for (int v : voisins[u])
        if (!visite[v]) visiterPourTri(v, voisins, visite, ordre);

    ordre.push(u);        // EN SORTANT, pas en entrant : tout ce que u
}                         // peut atteindre est déjà dans la pile.

C'est le parcours en profondeur du module précédent, avec l'empilement déplacé après la boucle. Rien d'autre ne change.

Une pile rendant ses éléments dans l'ordre inverse de leur arrivée, le renversement est gratuit : il suffit de dépiler.

vector<int> triTopologique(const vector<vector<int>>& voisins) {
    int n = voisins.size();
    vector<bool> visite(n, false);
    stack<int> ordre;

    // On lance depuis CHAQUE sommet non visité : un DAG n'a pas forcément
    // un sommet d'où tout est atteignable, et un seul départ en oublierait.
    for (int u = 0; u < n; u++)
        if (!visite[u]) visiterPourTri(u, voisins, visite, ordre);

    vector<int> resultat;
    while (!ordre.empty()) { resultat.push_back(ordre.top()); ordre.pop(); }
    return resultat;
}

Complexité : Θ(V + E), celle d'un parcours. Empiler et dépiler n fois ne change pas l'ordre de grandeur.

void visiterPourTri(int u, ...) {
    visite[u] = true;
    ordre.push(u);                       // <-- remonté AVANT la boucle
    for (int v : voisins[u])
        if (!visite[v]) visiterPourTri(v, ...);
}

Connexité et composantes

Un parcours ne visite que ce qui est atteignable depuis son départ. Si le graphe est en plusieurs morceaux, un seul appel en manque — et c'est exactement ce qui permet de compter les morceaux.

Le vocabulaire, d'abord. Un graphe non orienté est connexe s'il existe un chemin entre n'importe quelle paire de sommets — autrement dit, s'il est d'un seul tenant. Une composante connexe est un morceau maximal qui l'est : on ne peut pas y ajouter un sommet de plus sans casser la propriété.

int nombreDeComposantes(const vector<vector<int>>& voisins) {
    int n = voisins.size();
    vector<bool> visite(n, false);
    int nb = 0;

    for (int u = 0; u < n; u++) {
        if (!visite[u]) {
            nb++;                  // u n'a été atteint par AUCUN parcours
            parcoursProfondeur(u, voisins, visite);   // avale tout son morceau
        }
    }
    return nb;
}

Le compteur s'incrémente une fois par appel de départ, pas une fois par sommet. Chaque appel consomme une composante entière. Coût total : Θ(V + E), chaque sommet et chaque arête n'étant traités qu'une fois.

Fortement connexe, et Kosaraju

Une composante fortement connexe — CFC — est un ensemble maximal de sommets tel que, pour toute paire u, v qu'on y prend, il existe un chemin orienté de u vers v et un de v vers u. En exigeant les deux sens, on retrouve une relation symétrique, donc une vraie partition : chaque sommet appartient à exactement une CFC.

Le graphe d'exemple est un DAG : on ne peut jamais revenir sur ses pas, donc chacun de ses six sommets est sa propre CFC — six composantes d'un élément. C'est un résultat général et il vaut d'être retenu : dans un DAG, chaque sommet est sa propre CFC, et réciproquement, une CFC de deux sommets ou plus contient forcément un circuit.

Pour avoir quelque chose d'intéressant à calculer, ajoutons-lui donc deux arcs de retour : C→B et F→D. Le graphe compte maintenant neuf arcs, et il n'est plus acyclique.

Trois composantes, et {B, C} ne fusionne pas avec {D, E, F} bien que B atteigne D en passant par E et F : pour fusionner, il faudrait aussi un chemin de D vers B, et aucun arc ne remonte de la seconde rangée vers la première.

L'algorithme qui les trouve s'appelle Kosaraju, et c'est le plus simple à expliquer parce qu'il n'est rien d'autre que deux parcours en profondeur. Entre les deux, une opération qu'il faut voir avant de lire le code : le graphe transposé, celui où tous les arcs sont retournés.

// Le transposé se construit en une double boucle : pour chaque arc u -> v
// du graphe d'origine, on inscrit u dans la liste de v.
vector<vector<int>> transposer(const vector<vector<int>>& voisins) {
    vector<vector<int>> inverse(voisins.size());
    for (int u = 0; u < (int)voisins.size(); u++)
        for (int v : voisins[u]) inverse[v].push_back(u);
    return inverse;
}

Chaque arc est lu une fois et écrit une fois : Θ(V + E). Retourner un graphe ne coûte pas plus cher que le parcourir.

L'algorithme complet tient alors en trois gestes, et le second parcours est celui qui produit le résultat.

1. Un premier parcours en profondeur sur le graphe d'origine, en empilant chaque sommet en sortant — exactement l'empilement du tri topologique.
2. Construire le transposé.
3. Un second parcours sur le transposé, en prenant les départs dans l'ordre où la pile les rend. Chaque appel de départ délimite une CFC : tous les sommets qu'il atteint en forment une.

int nb = 0;
for (int u = 0; u < n; u++) {
    if (!visite[u]) { nb++; parcoursProfondeur(u, voisins, visite); }
}

Le relâchement, l'opération atomique

Deuxième moitié du module. Jusqu'ici, tous les arcs se valaient et la longueur d'un chemin était son nombre d'arcs. Donnons maintenant un poids à chaque arc — une durée, un prix, une distance —, et le coût d'un chemin devient la somme des poids qu'il traverse.

Ce changement fait tomber la propriété du parcours en largeur. Un chemin de trois arcs légers peut coûter moins qu'un arc lourd, si bien qu'arriver le premier ne veut plus dire arriver au meilleur prix. Il faut calculer.

Avant d'aller plus loin, une précision de vocabulaire que les énoncés supposent connue : « le problème du plus court chemin » en recouvre trois, selon ce qu'on demande.

• Source unique : les plus courts chemins depuis un sommet vers tous les autres. C'est celui que résolvent Dijkstra et Bellman-Ford, et le seul que ce cours traite — le travail pratique parle d'ailleurs d'algorithmes « à origine unique ».
• Paire unique : d'un sommet vers un seul autre. On n'a pas mieux que la source unique ; on s'arrête simplement dès que la destination est traitée.
• Toutes les paires : entre chaque couple de sommets. On peut relancer n fois un algorithme à source unique, ou employer un algorithme dédié — Floyd-Warshall — qui sort du programme.

Commençons par la structure. Un voisin ne suffit plus : il faut aussi le poids de l'arc qui y mène, donc un couple.

// pair<int,int>                 — un COUPLE d'entiers. Ses deux membres
//                                  s'appellent `.first` et `.second`.
// vector<pair<int,int>>         — la liste des voisins d'UN sommet, chacun
//                                  accompagné du poids de son arc.
// vector<vector<pair<int,int>>> — une de ces listes par sommet. C'est la
//                                  liste d'adjacence du module précédent,
//                                  dont chaque entrée porte un poids en plus.
vector<vector<pair<int,int>>> voisins(N);

voisins[0].push_back({1, 4});    // A -> B, poids 4
voisins[0].push_back({3, 2});    // A -> D, poids 2

Le graphe pondéré de ce module est celui des sections précédentes, avec ces sept poids : A→B 4, A→D 2, B→C 3, B→E 1, C→F 2, D→E 4, E→F 5.

Vient ensuite l'opération que les deux algorithmes de ce module partagent, et qui est leur seule brique commune. On tient, pour chaque sommet, la meilleure distance connue jusqu'ici depuis la source — une estimation, pas une vérité —, et on la corrige chaque fois qu'on découvre mieux.

// Relâcher l'arc u -> v, de poids `poids`.
if (dist[u] + poids < dist[v]) {
    dist[v] = dist[u] + poids;   // on a trouvé mieux pour aller en v
    pred[v] = u;                 // et c'est en passant par u
}

Le tableau pred se lit à l'envers. Pour reconstruire le chemin vers un sommet, on part de lui et on remonte : pred[F], puis pred[pred[F]], jusqu'à la source. On obtient le chemin en ordre inverse, qu'on retourne — exactement comme un tri topologique retourne sa pile.

vector<int> dist(n, 0);      // au lieu de : vector<int> dist(n, INFINI);
dist[source] = 0;
// ... puis les relâchements habituels

Dijkstra : explorer par le moins cher

Reste à décider dans quel ordre relâcher les arcs. Dijkstra répond par une idée simple : traiter toujours le sommet dont l'estimation courante est la plus basse parmi ceux qu'on n'a pas encore traités. On le déclare alors définitif, et on relâche ses arcs sortants.

Cette idée repose sur une hypothèse qu'il faut énoncer tout de suite, parce que c'est elle qui décidera du choix entre les deux algorithmes : tous les poids sont positifs ou nuls. On verra plus bas ce qui casse sans elle.

Le type C++ correspondant est le plus long du cours. Nommons-le d'abord, on le lira mieux ensuite.

// priority_queue<T, C, Cmp> prend TROIS paramètres, et c'est ce qui la rend
// illisible d'un coup :
//   T   — ce qu'on y range. Ici un couple (distance, sommet), et la
//         distance vient EN PREMIER : une file avec priorité de couples
//         compare sur `.first`, donc c'est lui qui doit porter le critère.
//   C   — le conteneur qui la porte en interne. Toujours un vector.
//   Cmp — la comparaison. Par défaut elle rend le PLUS GRAND ; `greater<>`
//         renverse l'ordre pour qu'on obtienne le plus petit.
using FilePrioritaire = priority_queue<pair<int,int>,
                                       vector<pair<int,int>>,
                                       greater<>>;

using donne un nom à un type, comme typedef le faisait autrefois. Rien n'est créé : c'est une abréviation, et elle ne coûte rien à l'exécution.

const int INFINI = INT_MAX;      // « pas encore atteint », depuis <climits>

void dijkstra(int source, const vector<vector<pair<int,int>>>& voisins,
              vector<int>& dist, vector<int>& pred) {
    int n = voisins.size();
    dist.assign(n, INFINI);
    pred.assign(n, -1);          // -1 = « aucun prédécesseur »
    dist[source] = 0;

    FilePrioritaire aVoir;
    aVoir.push({0, source});

    while (!aVoir.empty()) {
        // auto [d, u] = ... — une LIAISON STRUCTURÉE : le couple rendu par
        //                     top() est ouvert en DEUX variables d'un coup.
        //                     Équivaut à `int d = p.first, u = p.second;`.
        auto [d, u] = aVoir.top();
        aVoir.pop();

        // On n'efface pas les entrées périmées de la file : on les IGNORE
        // en sortant. Si d est pire que la meilleure distance connue pour u,
        // c'est qu'on a déjà relâché u depuis, et cette entrée ne vaut rien.
        if (d > dist[u]) continue;

        for (auto [v, poids] : voisins[u]) {
            if (dist[u] + poids < dist[v]) {
                dist[v] = dist[u] + poids;      // le relâchement
                pred[v] = u;
                aVoir.push({dist[v], v});
            }
        }
    }
}

Complexité : Θ((V + E) log V) avec une file avec priorité. Chaque arc peut provoquer une insertion, chaque insertion et chaque extraction coûtent un logarithme.

Lisons maintenant ce que ce code produit. La forme du tableau ci-dessous est celle que le cours attend : deux structures parallèles, l'évolution des coûts et, en dessous, le sommet qui a permis chaque relâchement. Source : A.

Deux lignes méritent qu'on s'y arrête, et ce sont celles où une estimation déjà écrite est corrigée. Au tour de B, E passe de 6 à 5 : la route par D coûtait 2 + 4, celle par B coûte 4 + 1. Au tour de C, F passe de 10 à 9. Une estimation n'est donc pas un résultat tant que son sommet n'a pas été extrait.

Résultat : F est à 9, et le chemin se reconstruit en remontant les prédécesseurs — F vient de C, C vient de B, B vient de A, soit A → B → C → F. Vérifie : 4 + 3 + 2 = 9, contre 10 par A→B→E→F et 11 par A→D→E→F.

Note enfin l'ordre d'extraction : A, D, B, E, C, F. Ce n'est ni l'ordre du parcours en largeur ni celui du parcours en profondeur du module précédent. Dijkstra a son propre ordre — celui du coût croissant —, et c'est ce qui en fait un algorithme et non un parcours.

auto [d, u] = aVoir.top();
aVoir.pop();
if (d > dist[u]) continue;       // <-- on la retire

Bellman-Ford, et les poids négatifs

Un poids négatif n'est pas une curiosité de manuel. Le travail pratique du cours en donne un cas concret : un réseau aérien dont les trajets portent un niveau de sécurité qui peut être négatif, et qu'on cherche à minimiser. Il faut donc un algorithme qui les accepte.

Bellman-Ford abandonne l'idée qui faisait la force et la fragilité de Dijkstra : il ne cherche plus à traiter les sommets dans le bon ordre. Il relâche simplement tous les arcs, encore et encore, jusqu'à ce que plus rien ne bouge.

// Bellman-Ford travaille sur une LISTE D'ARCS, pas sur des listes
// d'adjacence : il les relâche tous dans un ordre quelconque, sans jamais
// demander « quels sont les voisins de u ». Un tuple porte les trois
// informations d'un arc : départ, arrivée, poids.
bool bellmanFord(int source, int n, const vector<tuple<int,int,int>>& arcs,
                 vector<int>& dist, vector<int>& pred) {
    dist.assign(n, INFINI);
    pred.assign(n, -1);
    dist[source] = 0;

    for (int passe = 1; passe <= n - 1; passe++) {
        for (auto [u, v, poids] : arcs) {
            // Le test `dist[u] != INFINI` n'est pas décoratif : sans lui,
            // INT_MAX + un poids négatif déborde et devient très NÉGATIF,
            // ce qui ferait passer un sommet inatteignable pour le meilleur.
            if (dist[u] != INFINI && dist[u] + poids < dist[v]) {
                dist[v] = dist[u] + poids;
                pred[v] = u;
            }
        }
    }

    // La passe de trop : si quelque chose bouge encore, il y a un circuit
    // de poids négatif et les distances n'ont plus de sens.
    for (auto [u, v, poids] : arcs)
        if (dist[u] != INFINI && dist[u] + poids < dist[v]) return false;

    return true;
}

Complexité : Θ(V × E) — n − 1 passes sur les m arcs. Plus lent que Dijkstra, et sans logarithme parce qu'aucune structure ordonnée n'intervient.

Déroulons-le sur un petit graphe qui a un arc négatif. Quatre sommets — S, A, B, C — et cinq arcs, relâchés toujours dans le même ordre : (S,A,4), (S,B,2), (A,C,3), (B,A,−3), (B,C,6). Source : S.

La passe 1 illustre le mécanisme mieux qu'un paragraphe. L'arc (S,A,4) pose A à 4. Puis, dans la même passe, l'arc (B,A,−3) trouve B déjà à 2 et améliore A à 2 + (−3) = −1. Ces améliorations en cascade à l'intérieur d'une passe sont normales et bénéfiques : on utilise toujours la valeur courante de dist[u], jamais celle du début de la passe.

Et la passe 2 montre pourquoi une seule ne suffit pas. C valait 7, calculé avec l'ancienne estimation de A ; il faut repasser sur l'arc (A,C,3) pour que la nouvelle valeur de A se propage. Résultat : C est à 2, par S → B → A → C, soit 2 + (−3) + 3.

Choisir son algorithme

Trois façons de trouver un plus court chemin ont maintenant été vues, et le choix entre elles se fait sur une seule lecture de l'énoncé : les arcs portent-ils des poids, et ces poids peuvent-ils être négatifs ?

Une précision sur la ligne des complexités, parce qu'elle décide d'un choix de structure et qu'un énoncé peut le demander. Le Θ((V + E) log V) de Dijkstra suppose une file avec priorité. En cherchant le minimum à la main dans un simple tableau, on retombe à Θ(V²) — et sur un graphe dense, où m approche n², c'est en réalité le meilleur des deux : le logarithme se paie alors sur presque n² arcs, pour rien. Même arbitrage qu'au module précédent entre matrice et listes, et il se tranche sur le même critère.

La règle de décision tient en deux questions posées dans cet ordre. Y a-t-il des poids ? Si non, le parcours en largeur suffit, et il est le moins cher des trois — n'emploie jamais Dijkstra sur un graphe non pondéré, c'est un logarithme payé pour rien. Si oui, peuvent-ils être négatifs ? Si non, Dijkstra. Si oui, ou si l'énoncé demande de détecter un circuit négatif, Bellman-Ford.