Graphes Pondérés et Non Pondérés Expliqués

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Un poids est une fonction, pas une partie du graphe

Un graphe est un couple d'ensembles, G = (V, E), et rien dans cette définition ne mentionne de nombres. Distances, coûts, capacités et durées viennent de l'extérieur, sous la forme d'une fonction distincte attachée au même ensemble d'arêtes :

G = (V, E)                    le graphe : quelles paires sont reliées
w: E → ℝ                    la fonction de poids : ce que coûte chaque liaison

Les ouvrages de référence insistent sur cette séparation. Bondy et Murty définissent un graphe pondéré comme un graphe muni d'une affectation d'un nombre réel à chaque arête, puis définissent le poids d'un sous-graphe comme la somme des poids de ses arêtes, ce qui est exactement ce que minimisent un plus court chemin ou un arbre couvrant de poids minimum. Diestel traite les poids de la même façon, comme des données supplémentaires posées sur un objet combinatoire inchangé.

Garder w hors du graphe n'est pas de la pédanterie, cela apporte trois choses :

• Un même graphe peut porter plusieurs modèles de coût. Un réseau routier est un seul graphe G muni de trois fonctions : kilomètres, minutes, litres de carburant. Changer de fonction change chaque réponse sans toucher à un sommet ni à une arête.
• Les conditions portent sur la fonction, pas sur la structure. « Dijkstra exige des poids positifs ou nuls » est un énoncé sur w. Le graphe, lui, est indifférent.
• Les résultats structurels subsistent. La connexité, la planarité, la bipartition, les suites de degrés et le lemme des poignées de main sont des propriétés de (V, E) seul, donc ajouter des poids ne peut en changer aucune.

Un graphe non pondéré est alors simplement un graphe sans une telle fonction, et la section suivante montre que cela revient à fournir la fonction la plus banale qui soit.

2. Non pondéré signifie que chaque poids vaut 1

La façon la plus claire de penser les deux cas ensemble est de ne plus voir « non pondéré » comme une absence de poids, mais comme un choix particulier de poids :

Un graphe non pondéré est un graphe pondéré avec w(e) = 1 pour chaque arête. Le poids d'un chemin est alors son nombre d'arêtes, donc « plus court chemin » signifie « le moins d'arêtes ».

Tout découle de cette unique substitution. Le parcours en largeur, qui trouve le chemin ayant le moins d'arêtes, est exactement ce en quoi dégénère l'algorithme de Dijkstra quand chaque poids vaut 1 : la file de priorité n'a jamais rien à réordonner, puisque les distances en sortent de toute façon dans un ordre entier croissant au sens large, et une simple file FIFO fait le même travail en O(n + m). L'article d'Edward Moore de 1959, « The shortest path through a maze », a posé et résolu précisément ce problème à poids unitaires, et l'on y fait généralement remonter l'algorithme.

La substitution fonctionne aussi dans l'autre sens, et c'est là que le coût des poids apparaît. Donnez au même graphe des poids positifs quelconques et la file FIFO ne fonctionne plus, car un chemin comportant plus d'arêtes peut désormais coûter moins cher. Il faut une file de priorité, et le temps d'exécution passe de O(n + m) à O(m log n) avec un tas binaire, ou O(m + n log n) avec le tas de Fibonacci de Fredman et Tarjan (1987).

3. Le plus court chemin n'est pas le plus court chemin

Voici toute la distinction en une image. Les mêmes cinq sommets, les mêmes cinq arêtes et la même question donnent deux réponses différentes selon que les nombres sont présents ou non.

Écrit en entier, le graphe est

V = {A, B, C, D, E}
E = { {A,B}, {B,C}, {C,D}, {A,D}, {D,E} }
w =    1       1       1       7       2

et les deux questions ont ces réponses :

Remarquez que la réponse pondérée utilise plus d'arêtes dans les deux lignes. C'est le cas normal, pas un cas artificiel : un détour par l'autoroute compte plus d'échangeurs et moins de minutes. Lancer un BFS sur un graphe pondéré ne donne pas une réponse approchée, cela donne la réponse à une autre question, et l'écart entre les deux n'est pas borné. Portez le poids de {A, D} à un million et le BFS la renvoie toujours.

4. Ce que signifie un poids : trois façons de les combiner

« Graphe pondéré » est un contenant, pas une signification. Avant de choisir un algorithme, il faut répondre à une question préalable : comment les poids le long d'un chemin se combinent-ils pour donner la valeur qui vous intéresse ? Il y a trois réponses courantes, et elles mènent à trois problèmes différents.

L'astuce multiplicative mérite d'être détaillée, car elle revient partout, du routage au décodage en langage naturel. Maximiser un produit de probabilités le long d'un chemin revient à minimiser la somme de leurs logarithmes négatifs, puisque -log est décroissante et transforme les produits en sommes. Comme chaque probabilité vaut au plus 1, chaque -log w est positif ou nul, donc Dijkstra s'applique directement et aucun algorithme spécial n'est nécessaire.

Il reste une distinction qui cause plus d'erreurs de modélisation que tout ce qui précède, et elle n'a rien d'arithmétique :

Un nombre plus grand signifie-t-il plus proche ou plus loin ? Dans un graphe de distances, un grand poids est mauvais et l'on minimise. Dans un graphe de similarité, un grand poids est bon et l'on maximise. Les deux sont opposés, et le format du fichier ne vous dit pas lequel vous avez.

Les réseaux de corrélation, les graphes d'achats conjoints et les graphes de similarité d'embeddings sont tous pondérés par similarité : les confier à une routine de plus court chemin calcule le chemin passant par les liens les moins similaires. Si vous avez besoin d'une distance à partir d'une similarité, convertissez délibérément : d = 1 - s pour une similarité bornée dans [0, 1], ou d = 1/s, ou d = -log s. Chaque choix modifie le classement des chemins : c'est une décision de modélisation, pas une formalité.

5. L'algorithme que les poids choisissent pour vous

Dès que la règle de combinaison est additive, la forme de la fonction de poids suffit à décider de l'algorithme. C'est le cœur pratique de la distinction entre pondéré et non pondéré.

Deux entrées de ce tableau méritent une remarque. Le BFS 0-1 repose sur l'observation astucieuse que, si les poids valent seulement 0 ou 1, un tas est inutile : une file à double entrée garde la frontière triée gratuitement, ce qui rend le temps linéaire. L'algorithme de Johnson, issu de son article de 1977 dans le Journal of the ACM, est la méthode standard pour garder la vitesse de Dijkstra sur des graphes à arêtes négatives : il ajoute une fonction potentiel qui rend chaque arête repondérée positive ou nulle tout en préservant les plus courts chemins.

Il existe aussi un résultat frappant à la frontière du cas non pondéré. Thorup a montré en 1999 que les plus courts chemins depuis une source dans un graphe non orienté à poids entiers positifs peuvent se calculer en temps linéaire, comme le BFS, en exploitant la structure des poids entiers plutôt qu'en comparant des distances. Aucun résultat comparable en temps linéaire n'est connu pour des poids réels quelconques dans le modèle comparaison-addition, ce qui rappelle que « pondéré » n'est pas un problème unique mais une famille dont la difficulté dépend de l'allure des poids.

6. Poids négatifs, et pourquoi Dijkstra échoue

La note de Dijkstra de 1959 supposait des poids positifs ou nuls, et cette hypothèse est porteuse, pas décorative. L'algorithme est glouton : dès qu'il retire un sommet de la file, il le déclare fixé et n'y revient jamais. Ce n'est correct que si aucun chemin découvert plus tard ne peut être moins cher, ce que garantit exactement la non-négativité, puisque prolonger un chemin ne peut qu'augmenter son coût.

Introduisez une seule arête négative et la garantie tombe. Voici un contre-exemple assez petit pour être suivi à la main, et sans égalités, de sorte que l'ordre de sortie est imposé :

Suivez-le : la file sort S à 0 et relâche A à 1 et C à 3. Elle sort A à 1 et relâche B à 2. Elle sort B à 2 et le marque comme fixé. Ce n'est qu'ensuite qu'elle sort C à 3 et trouve l'arc C → B de poids -5, qui donnerait à B une distance de -2. Comme B est déjà fixé, l'amélioration est ignorée et l'algorithme renvoie 2 au lieu de -2.

Deux précisions qui comptent plus que le contre-exemple lui-même :

• Poids négatifs ne veut pas dire cycles négatifs. Un graphe peut avoir des arêtes négatives et des plus courts chemins bien définis, et c'est exactement le cas que traite Bellman-Ford en O(nm). Ce qui ruine complètement le problème, c'est un cycle de poids total négatif, car on peut le parcourir encore et encore et faire tendre le coût vers moins l'infini. Bellman-Ford détecte cette situation au lieu de renvoyer silencieusement une absurdité.
• Dans un graphe non orienté, une seule arête négative est déjà un cycle négatif. Parcourez-la à l'aller et au retour et vous avez payé 2w < 0. Les poids négatifs sont donc en pratique un sujet de graphes orientés ; dans les graphes non orientés, le problème de la plus courte marche n'est pas borné et celui du plus court chemin élémentaire devient NP-difficile. Le guide sur les graphes orientés et non orientés traite cette frontière.

Les poids négatifs n'ont rien d'exotique. Les chaînes d'arbitrage évaluent les conversions de devises comme des produits, qui deviennent des sommes de logarithmes négatifs, et un cycle rentable apparaît dans le modèle comme un cycle négatif. C'est l'application classique de la détection de poids négatifs, et c'est pourquoi Bellman-Ford vaut bien son facteur supplémentaire de n.

7. Des problèmes qui n'existent qu'avec des poids

Certaines questions ne sont pas plus difficiles sans poids, elles sont vides. Le cas le plus net est l'arbre couvrant de poids minimum.

Dans un graphe connexe non pondéré, tout arbre couvrant a exactement n - 1 arêtes, donc tout arbre couvrant est minimum et n'importe quel parcours résout le problème : l'arbre du BFS ou du DFS est déjà une réponse. Ajoutez des poids et la question devient réelle, car les arbres couvrants ont désormais des coûts totaux différents, et trouver le moins cher est ce qu'ont résolu Borůvka en 1926, Kruskal en 1956 et Prim en 1957.

Sur l'exemple récurrent, l'arbre couvrant de poids minimum prend {A,B}, {B,C}, {C,D} et {D,E} pour un total de 5, et rejette l'arête coûteuse {A,D} à 7. Sans poids, les quatre arbres couvrants de ce graphe seraient aussi bons les uns que les autres.

Le flot maximum est le miroir du cas de l'arbre couvrant. Les capacités sont la fonction de poids, donc un réseau de flot non pondéré signifie des capacités unitaires, cas particulier où le flot maximum se ramène au dénombrement de chemins arête-disjoints par le théorème de Menger. L'ouvrage Network Flows d'Ahuja, Magnanti et Orlin est la référence standard du traitement pondéré général, où chaque arc porte généralement à la fois une capacité et un coût, deux fonctions de poids sur un même graphe.

8. Stocker les poids, et le piège du zéro contre l'infini

Les deux représentations standard s'étendent de façon évidente, et chacune a un mode de défaillance qu'il vaut la peine de nommer.

Matrice d'adjacence. Au lieu de 0 et 1, le coefficient (u, v) contient le poids de cette arête. Le piège est immédiat : que mettre dans les cases sans arête ? Zéro est la valeur par défaut tentante, et c'est une erreur, car zéro est un poids parfaitement légal et les deux cas deviennent indiscernables. Utilisez ∞ pour « pas d'arête » dans les problèmes de plus court chemin, puisque c'est l'élément neutre de la minimisation, et gardez 0 sur la diagonale. Dans une matrice non pondérée, la même case signifie « pas d'arête » avec la valeur 0, et c'est précisément pourquoi le code porté du non pondéré au pondéré casse à cet endroit.

non pondéré       A[u][v] = 1 si reliés, sinon 0
pondéré           A[u][v] = w(u,v) si reliés, sinon ∞      (0 sur la diagonale)

bug sentinelle    A[u][v] = 0 pour « pas d'arête » rend invisible une arête
                  de poids nul, et toutes les distances s'effondrent à 0

Liste d'adjacence. Chaque entrée devient un couple au lieu d'un simple sommet, donc la liste contient (voisin, poids). Rien d'autre ne change, et c'est pourquoi la liste d'adjacence est le choix par défaut pour les graphes pondérés : le surcoût mémoire est d'un nombre par arête stockée, et la boucle de parcours est identique.

Un troisième format compte spécifiquement pour les graphes pondérés. La liste d'arêtes sous forme de triplets (u, v, w) est l'entrée naturelle de l'algorithme de Kruskal, qui trie toute la liste par poids, et de Bellman-Ford, qui relâche chaque arête à tour de rôle. Aucun des deux n'a besoin de chercher des voisins, donc aucun n'a besoin d'une structure d'adjacence.

9. Le degré devient la force

Les poids changent les statistiques descriptives autant que les algorithmes. L'analogue pondéré du degré d'un sommet est sa force, la somme des poids de ses arêtes incidentes :

deg(v)  =  nombre d'arêtes incidentes            le compte non pondéré
s(v)    =  ∑ w(e)  sur les arêtes incidentes à v   le total pondéré

Barrat, Barthélemy, Pastor-Satorras et Vespignani ont introduit le terme dans leur article de 2004 dans PNAS sur les réseaux pondérés, et son intérêt tient à ce que les deux quantités peuvent classer les sommets de façon complètement différente. Un aéroport doté de nombreuses petites lignes régionales a un degré élevé et une force faible ; un hub doté de quatre énormes lignes long-courrier a un degré faible et une force élevée. Demander « quel est l'aéroport le plus important » donne une réponse différente selon ce que l'on calcule, et aucune n'est fausse.

Le même clivage traverse le reste de l'analyse des réseaux. L'article de Newman de 2004, « Analysis of weighted networks », montre comment le coefficient de clustering, la modularité et la centralité acquièrent chacun une version pondérée, et que les versions pondérée et non pondérée d'une mesure sont souvent en désaccord sur les mêmes données. Quand vous rapportez une statistique de réseau, préciser si elle utilise les poids n'est pas une note de bas de page, cela fait partie de la définition.

10. Quand ajouter des poids, et quand s'en passer

Les poids ne sont pas gratuits. Ils vous coûtent les algorithmes en temps linéaire, ajoutent une décision de modélisation à chaque étape et introduisent une sensibilité à l'échelle qu'un graphe non pondéré n'a tout simplement pas. Utilisez-les quand la réponse dépend vraiment des grandeurs :

• Ajoutez des poids quand les arêtes sont inégales de façon mesurable et que cela change la décision : longueurs de routes, capacités de liens, montants de transactions, forces de corrélation, scores de similarité.
• Restez non pondéré quand la relation est binaire par nature (voisinage de pays, présence d'une dépendance), quand vos nombres sont des indicateurs bruités que vous ne défendriez pas, ou quand la question est purement structurelle, comme la connexité ou la bipartition.
• Appliquez plutôt un seuil quand les poids existent mais ne sont pas fiables. Garder les arêtes au-dessus d'un seuil et écarter le reste transforme un graphe pondéré bruité en un graphe non pondéré défendable. Indiquez le seuil, car les résultats en dépendent généralement.

Deux mises en garde propres aux données pondérées. D'abord, l'échelle compte : multiplier tous les poids par une constante positive laisse inchangés les plus courts chemins et les arbres couvrants de poids minimum, puisque tous deux minimisent une somme, mais change toute statistique qui compare les poids à un seuil absolu, et un multiplicateur négatif inverse complètement le problème. Ensuite, les unités doivent concorder avant d'additionner des poids. Mélanger minutes et kilomètres dans une même fonction de poids produit des nombres qu'aucun algorithme ne peut interpréter, et rien dans le code ne s'en plaindra.

11. Erreurs courantes

• Lancer un BFS sur un graphe pondéré. L'erreur la plus courante. Il renvoie le chemin ayant le moins d'arêtes, qui est la bonne réponse à une autre question, et l'erreur n'est pas bornée, comme le montre la section 3 .
• Utiliser 0 comme sentinelle « pas d'arête ». Cela marche jusqu'à ce qu'une vraie arête de poids nul existe, puis c'est faux sans le moindre signal. Utilisez l'infini pour les problèmes de minimisation.
• Confier un graphe de similarité à une routine de plus court chemin. Elle trouvera fidèlement la route passant par les liens les plus faibles. Convertissez d'abord la similarité en distance, et dites comment.
• Utiliser Dijkstra avec des poids négatifs. Il ne perd pas seulement ses garanties d'optimalité sur certaines entrées, il renvoie des nombres concrètement faux, comme dans la section 6. Utilisez Bellman-Ford, ou Johnson pour toutes les paires.
• Croire qu'une arête négative rend le problème insoluble. Seul un cycle négatif rend les plus courts chemins indéfinis. Bellman-Ford traite le reste et signale le cycle s'il en existe un.
• Additionner des poids d'unités différentes. Des minutes plus des kilomètres n'ont aucun sens, et aucun algorithme ne vous le dira.
• Rapporter une statistique de réseau pondérée sans le préciser. Le degré et la force, ainsi que les centralités qui en dérivent, classent régulièrement les mêmes sommets différemment.
• Oublier que la structure est inchangée. La connexité, la bipartition et les suites de degrés ne dépendent pas de w. Si un algorithme pondéré donne une réponse qui contredit l'une d'elles, le bug est dans la pondération, pas dans la théorie.

12. Glossaire

14. Références

Les définitions, algorithmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Borůvka, O. (1926). "O jistém problému minimálním" (Sur un certain problème de minimum). Práce Moravské Přírodovědecké Společnosti 3, 37 à 58. Le plus ancien algorithme d'arbre couvrant de poids minimum.
2. Kruskal, J. B. (1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1), 48 à 50.
3. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6), 1389 à 1401.
4. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 à 90. Des plus courts chemins qui tolèrent les poids négatifs.
5. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1, 269 à 271. L'hypothèse de non-négativité y est énoncée.
6. Moore, E. F. (1959). "The Shortest Path Through a Maze." Proceedings of an International Symposium on the Theory of Switching, Partie II, 285 à 292. Harvard University Press. Le cas à poids unitaires, aujourd'hui connu sous le nom de BFS.
7. Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1), 1 à 13. La repondération pour éliminer les arêtes négatives.
8. Fredman, M. L. et Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM 34(3), 596 à 615. Dijkstra en O(m + n log n).
9. Ahuja, R. K., Magnanti, T. L. et Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs : Prentice Hall. La référence standard sur les capacités et les coûts comme poids.
10. Thorup, M. (1999). "Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time." Journal of the ACM 46(3), 362 à 394.
11. West, D. B. (2001). Introduction to Graph Theory, 2e édition. Upper Saddle River : Prentice Hall.
12. Barrat, A., Barthélemy, M., Pastor-Satorras, R. et Vespignani, A. (2004). "The Architecture of Complex Weighted Networks." Proceedings of the National Academy of Sciences 101(11), 3747 à 3752. Source de la force d'un sommet.
13. Newman, M. E. J. (2004). "Analysis of Weighted Networks." Physical Review E 70, 056131. Versions pondérées des mesures de réseau standard.
14. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres : Springer. Source de la définition de graphe pondéré de la section 1.
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition. Cambridge, Massachusetts : MIT Press.
16. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.