Grafos Ponderados y No Ponderados Explicados

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Un peso es una función, no parte del grafo

Un grafo es un par de conjuntos, G = (V, E), y nada en esa definición menciona números. Las distancias, los costes, las capacidades y las duraciones llegan desde fuera, como una función aparte asociada al mismo conjunto de aristas:

G = (V, E)                    el grafo: qué pares están unidos
w: E → ℝ                    la función de peso: cuánto cuesta cada unión

Los textos de referencia son deliberados con esta separación. Bondy y Murty definen un grafo ponderado como un grafo junto con una asignación de un número real a cada arista, y después definen el peso de un subgrafo como la suma de los pesos de sus aristas, que es exactamente lo que minimiza un camino más corto o un árbol de expansión mínima. Diestel trata los pesos del mismo modo, como datos extra sobre un objeto combinatorio que no cambia.

Mantener w fuera del grafo no es pedantería; aporta tres cosas:

• Un mismo grafo puede llevar varios modelos de coste. Una red de carreteras es un único G con tres funciones encima: kilómetros, minutos y litros de combustible. Cambiar de función cambia todas las respuestas sin tocar un vértice ni una arista.
• Las condiciones se aplican a la función, no a la estructura. «Dijkstra necesita pesos no negativos» es una afirmación sobre w. Al grafo le da igual.
• Los resultados estructurales se mantienen. La conexidad, la planaridad, la bipartición, las secuencias de grados y el lema del apretón de manos son propiedades de (V, E) por sí solo, así que añadir pesos no puede cambiar ninguna de ellas.

Un grafo no ponderado es entonces simplemente un grafo sin tal función, y la siguiente sección muestra que eso equivale a darle la función más aburrida que existe.

2. No ponderado significa que cada peso es 1

La forma más limpia de tener ambos casos en la cabeza es dejar de tratar «no ponderado» como la ausencia de pesos y empezar a tratarlo como una elección concreta de pesos:

Un grafo no ponderado es un grafo ponderado con w(e) = 1 para cada arista. El peso de un camino es entonces su número de aristas, así que «camino más corto» significa «menos aristas».

Todo se deriva de esa única sustitución. La búsqueda en anchura, que encuentra el camino con menos aristas, es exactamente aquello en lo que degenera el algoritmo de Dijkstra cuando todos los pesos valen 1: la cola de prioridad nunca necesita reordenar nada, porque las distancias salen de ella en orden entero no decreciente de todos modos, y una simple cola FIFO hace el mismo trabajo en O(n + m). El artículo de Edward Moore de 1959, «The shortest path through a maze», planteó y resolvió precisamente este problema de pesos unitarios, y suele considerarse el origen del algoritmo.

La sustitución también funciona en sentido contrario, y ahí aparece el coste de los pesos. Da al mismo grafo pesos positivos arbitrarios y la cola FIFO deja de funcionar, porque un camino con más aristas puede ser ahora más barato. Necesitas una cola de prioridad, y el tiempo de ejecución pasa de O(n + m) a O(m log n) con un montículo binario, o O(m + n log n) con el montículo de Fibonacci de Fredman y Tarjan (1987).

3. El camino más corto no es el camino más corto

Aquí está toda la distinción en una sola imagen. Los mismos cinco vértices, las mismas cinco aristas y la misma pregunta dan dos respuestas distintas según haya o no números.

Escrito completo, el grafo es

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

y las dos preguntas tienen estas respuestas:

Fíjate en que la respuesta ponderada usa más aristas en ambas filas. Es el caso normal, no uno forzado: un desvío por autopista tiene más cruces y menos minutos. Ejecutar BFS en un grafo ponderado no da una respuesta aproximada, da la respuesta a otra pregunta, y la diferencia entre ambas no tiene cota. Sube el peso de {A, D} a un millón y BFS la seguirá devolviendo.

4. Qué significa un peso: tres formas de combinarlos

«Grafo ponderado» es un contenedor, no un significado. Antes de elegir un algoritmo tienes que responder una pregunta previa: ¿cómo se combinan los pesos a lo largo de un camino en el valor que te interesa? Hay tres respuestas habituales, y llevan a tres problemas distintos.

El truco multiplicativo merece explicarse porque aparece en todas partes, desde el enrutamiento hasta la decodificación del lenguaje natural. Maximizar un producto de probabilidades a lo largo de un camino es lo mismo que minimizar la suma de sus logaritmos negativos, ya que -log es monótona decreciente y convierte productos en sumas. Como cada probabilidad es como mucho 1, cada -log w es no negativo, así que Dijkstra se aplica directamente y no hace falta ningún algoritmo especial.

Hay una distinción más que causa más errores de modelado que todo lo anterior, y no tiene nada que ver con la aritmética:

¿Un número mayor significa más cerca o más lejos? En un grafo de distancias, un peso grande es malo y se minimiza. En un grafo de similitud, un peso grande es bueno y se maximiza. Son opuestos, y el formato del archivo no te dice cuál tienes.

Las redes de correlación, los grafos de compras conjuntas y los grafos de similitud de embeddings están todos ponderados por similitud, así que pasarlos a una rutina de camino más corto calcula el camino a través de los enlaces menos similares. Si necesitas una distancia a partir de una similitud, conviértela de forma deliberada: d = 1 - s para una similitud acotada en [0, 1], o d = 1/s, o d = -log s. Cada elección cambia el orden de los caminos, así que es una decisión de modelado y no una formalidad.

5. Qué algoritmo eligen los pesos por ti

Una vez que la regla de combinación es aditiva, la forma de la función de peso decide por sí sola el algoritmo. Este es el núcleo práctico de la distinción entre ponderado y no ponderado.

Dos entradas de esa tabla merecen un comentario. BFS 0-1 es la ingeniosa observación de que, si los pesos solo son 0 o 1, nunca necesitas un montículo: una cola doble mantiene la frontera ordenada gratis, lo que recupera el tiempo lineal. El algoritmo de Johnson, de su artículo de 1977 en el Journal of the ACM, es la forma estándar de conservar la velocidad de Dijkstra en grafos con aristas negativas: añade una función de potencial que hace no negativa cada arista reponderada sin cambiar qué caminos son los más cortos.

También hay un resultado llamativo en la frontera del caso no ponderado. Thorup demostró en 1999 que los caminos más cortos desde un origen en un grafo no dirigido con pesos enteros positivos pueden calcularse en tiempo lineal, igualando a BFS, aprovechando la estructura de los pesos enteros en lugar de comparar distancias. No se conoce un resultado comparable en tiempo lineal para pesos reales arbitrarios en el modelo de comparación y suma, lo que recuerda que «ponderado» no es un único problema, sino una familia cuya dificultad depende de cómo sean los pesos.

6. Pesos negativos, y por qué falla Dijkstra

La nota de Dijkstra de 1959 suponía pesos no negativos, y esa suposición es estructural, no decorativa. El algoritmo es voraz: en cuanto saca un vértice de la cola lo declara fijado y no vuelve a revisarlo. Eso solo es correcto si ningún camino descubierto después puede ser más barato, que es exactamente lo que garantiza la no negatividad, ya que alargar un camino solo puede aumentar su coste.

Introduce una sola arista negativa y la garantía se rompe. Aquí tienes un contraejemplo lo bastante pequeño para seguirlo a mano y sin empates, de modo que el orden de extracción queda forzado:

Síguelo paso a paso: la cola extrae S en 0 y relaja A a 1 y C a 3. Extrae A en 1 y relaja B a 2. Extrae B en 2 y lo marca como fijado. Solo entonces extrae C en 3 y encuentra el arco C → B de peso -5, que daría a B una distancia de -2. Como B ya está fijado, la mejora se descarta y el algoritmo informa de 2 en lugar de -2.

Dos aclaraciones que importan más que el propio contraejemplo:

• Los pesos negativos no son lo mismo que los ciclos negativos. Un grafo puede tener aristas negativas y aun así caminos más cortos bien definidos, que es exactamente el caso que Bellman-Ford resuelve en O(nm). Lo que rompe el problema por completo es un ciclo de peso total negativo, porque puedes recorrerlo una y otra vez y llevar el coste a menos infinito. Bellman-Ford detecta esa situación en lugar de devolver en silencio un disparate.
• En un grafo no dirigido, una sola arista negativa ya es un ciclo negativo. Recórrela de ida y vuelta y habrás pagado 2w < 0. Así que los pesos negativos son, en la práctica, un tema de grafos dirigidos; en grafos no dirigidos el problema del recorrido más corto no está acotado y el del camino simple más corto es NP-difícil. La guía complementaria sobre grafos dirigidos y no dirigidos trata esa frontera.

Los pesos negativos no son exóticos. Las cadenas de arbitraje valoran las conversiones de divisas como productos, que se convierten en sumas de logaritmos negativos, y un ciclo rentable aparece en el modelo como un ciclo negativo. Es la aplicación de libro de texto de la detección de pesos negativos, y es la razón por la que Bellman-Ford compensa su factor extra de n.

7. Problemas que solo existen con pesos

Algunas preguntas no son más difíciles sin pesos: están vacías. El caso más claro es el árbol de expansión mínima.

En un grafo conexo no ponderado, todo árbol de expansión tiene exactamente n - 1 aristas, así que todo árbol de expansión es mínimo y cualquier recorrido resuelve el problema: el árbol de BFS o DFS ya es una respuesta. Añade pesos y la pregunta se vuelve real, porque los árboles de expansión tienen ahora costes totales distintos, y encontrar el más barato es lo que resolvieron Borůvka en 1926, Kruskal en 1956 y Prim en 1957.

En el ejemplo recurrente, el árbol de expansión mínima toma {A,B}, {B,C}, {C,D} y {D,E} con un total de 5, y descarta la arista cara {A,D} de 7. Sin pesos, los cuatro árboles de expansión de ese grafo serían igual de buenos.

El flujo máximo es la imagen especular del caso del árbol de expansión. Las capacidades son la función de peso, así que una red de flujo no ponderada significa capacidades unitarias, el caso particular en el que el flujo máximo se reduce a contar caminos disjuntos en aristas por el teorema de Menger. El libro Network Flows de Ahuja, Magnanti y Orlin es la referencia estándar para el tratamiento ponderado general, donde cada arco suele llevar a la vez una capacidad y un coste, dos funciones de peso sobre un mismo grafo.

8. Almacenar pesos, y la trampa del cero frente al infinito

Las dos representaciones estándar se extienden de la forma obvia, y ambas tienen un modo de fallo que conviene nombrar.

Matriz de adyacencia. En lugar de 0 y 1, la entrada (u, v) guarda el peso de esa arista. La trampa es inmediata: ¿qué va en las celdas sin arista? El cero es el valor por defecto tentador y es un error, porque el cero es un peso perfectamente legal y los dos casos se vuelven indistinguibles. Usa ∞ para «sin arista» en contextos de camino más corto, ya que es el elemento neutro de la minimización, y deja 0 en la diagonal. En una matriz no ponderada la misma celda significa «sin arista» con el valor 0, y precisamente por eso el código portado de no ponderado a ponderado se rompe aquí.

no ponderado      A[u][v] = 1 si están unidos, si no 0
ponderado         A[u][v] = w(u,v) si están unidos, si no ∞      (0 en la diagonal)

error centinela   A[u][v] = 0 para «sin arista» hace invisible una arista
                  de peso cero, y todas las distancias colapsan a 0

Lista de adyacencia. Cada entrada pasa a ser un par en lugar de un vértice suelto, así que la lista guarda (vecino, peso). Nada más cambia, y por eso la lista de adyacencia es la opción por defecto para el trabajo ponderado: el coste de memoria es un número por arista almacenada y el bucle de recorrido es idéntico.

Un tercer formato importa especialmente para grafos ponderados. La lista de aristas de ternas (u, v, w) es la entrada natural del algoritmo de Kruskal, que ordena toda la lista por peso, y de Bellman-Ford, que relaja cada arista por turno. Ninguno necesita consultar vecinos, así que ninguno necesita una estructura de adyacencia.

9. El grado se convierte en fuerza

Los pesos cambian las estadísticas descriptivas además de los algoritmos. El análogo ponderado del grado de un vértice es su fuerza, la suma de los pesos de sus aristas incidentes:

deg(v)  =  número de aristas incidentes             el conteo no ponderado
s(v)    =  ∑ w(e)  sobre las aristas incidentes a v   el total ponderado

Barrat, Barthélemy, Pastor-Satorras y Vespignani introdujeron el término en su artículo de 2004 en PNAS sobre redes ponderadas, y la razón por la que importa es que las dos magnitudes pueden ordenar los vértices de forma completamente distinta. Un aeropuerto con muchas rutas regionales diminutas tiene grado alto y fuerza baja; un hub con cuatro enormes rutas de largo recorrido tiene grado bajo y fuerza alta. Preguntar «cuál es el aeropuerto más importante» da una respuesta distinta según cuál calcules, y ninguna es incorrecta.

La misma división recorre el resto del análisis de redes. El artículo de Newman de 2004, «Analysis of weighted networks», muestra cómo el coeficiente de agrupamiento, la modularidad y la centralidad adquieren versiones ponderadas, y que las versiones ponderada y no ponderada de una medida a menudo discrepan sobre los mismos datos. Cuando informes de una estadística de red, decir si usó los pesos no es una nota al pie: forma parte de la definición.

10. Cuándo añadir pesos, y cuándo no

Los pesos no son gratis. Te cuestan los algoritmos de tiempo lineal, añaden una decisión de modelado en cada paso e introducen una sensibilidad a la escala que un grafo no ponderado simplemente no tiene. Recurre a ellos cuando la respuesta dependa de verdad de la magnitud:

• Añade pesos cuando las aristas sean mediblemente desiguales de un modo que cambie la decisión: longitudes de carreteras, capacidades de enlaces, importes de transacciones, fuerzas de correlación, puntuaciones de similitud.
• Mantente sin pesos cuando la relación sea binaria por naturaleza (vecindad entre países, existencia de una dependencia), cuando los números que tienes sean aproximaciones ruidosas que no defenderías, o cuando la pregunta sea puramente estructural, como la conexidad o la bipartición.
• Aplica un umbral en su lugar cuando existan pesos pero no sean fiables. Conservar las aristas por encima de un corte y descartar el resto convierte un grafo ponderado ruidoso en uno no ponderado defendible. Indica el corte, porque los resultados suelen depender de él.

Dos advertencias propias de los datos ponderados. Primero, la escala importa: multiplicar todos los pesos por una constante positiva deja sin cambios los caminos más cortos y los árboles de expansión mínima, ya que ambos minimizan una suma, pero cambia cualquier estadística que compare pesos con un umbral absoluto, y un multiplicador negativo invierte el problema por completo. Segundo, las unidades deben coincidir antes de sumar pesos. Mezclar minutos con kilómetros en una función de peso produce números que ningún algoritmo puede interpretar, y nada en el código se quejará.

11. Errores comunes

• Ejecutar BFS en un grafo ponderado. El más común de todos. Devuelve el camino con menos aristas, que es la respuesta correcta a otra pregunta, y el error no tiene cota, como muestra la sección 3 .
• Usar 0 como centinela de «sin arista». Funciona hasta que existe una arista de peso cero de verdad, y entonces falla en silencio. Usa infinito en los problemas de minimización.
• Pasar un grafo de similitud a una rutina de camino más corto. Encontrará fielmente la ruta por los enlaces más débiles. Convierte primero la similitud en distancia, y di cómo.
• Recurrir a Dijkstra con pesos negativos. No solo pierde garantías de optimalidad en algunas entradas: devuelve números concretamente erróneos, como en la sección 6. Usa Bellman-Ford, o Johnson para todos los pares.
• Suponer que una arista negativa rompe el problema. Solo un ciclo negativo hace que los caminos más cortos no estén definidos. Bellman-Ford resuelve el resto e informa del ciclo si existe.
• Sumar pesos de unidades distintas. Minutos más kilómetros no significa nada, y ningún algoritmo te lo dirá.
• Informar de una estadística de red ponderada sin decirlo. El grado y la fuerza, y las centralidades derivadas, ordenan con frecuencia los mismos vértices de forma distinta.
• Olvidar que la estructura no cambia. La conexidad, la bipartición y las secuencias de grados no dependen de w. Si un algoritmo ponderado da una respuesta que contradice alguna de ellas, el error está en la ponderación, no en la teoría.

12. Glosario

14. Referencias

Las definiciones, algoritmos y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Borůvka, O. (1926). "O jistém problému minimálním" (Sobre cierto problema de mínimo). Práce Moravské Přírodovědecké Společnosti 3, 37 a 58. El primer algoritmo de árbol de expansión mínima.
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 a 50.
3. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6), 1389 a 1401.
4. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 a 90. Caminos más cortos que toleran pesos negativos.
5. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1, 269 a 271. Aquí se enuncia la suposición de no negatividad.
6. Moore, E. F. (1959). "The Shortest Path Through a Maze." Proceedings of an International Symposium on the Theory of Switching, Parte II, 285 a 292. Harvard University Press. El caso de pesos unitarios, hoy conocido como BFS.
7. Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1), 1 a 13. Reponderación para eliminar aristas negativas.
8. Fredman, M. L. y Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM 34(3), 596 a 615. Dijkstra en O(m + n log n).
9. Ahuja, R. K., Magnanti, T. L. y Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs: Prentice Hall. La referencia estándar sobre capacidades y costes como pesos.
10. Thorup, M. (1999). "Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time." Journal of the ACM 46(3), 362 a 394.
11. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River: Prentice Hall.
12. Barrat, A., Barthélemy, M., Pastor-Satorras, R. y Vespignani, A. (2004). "The Architecture of Complex Weighted Networks." Proceedings of the National Academy of Sciences 101(11), 3747 a 3752. Origen de la fuerza de un vértice.
13. Newman, M. E. J. (2004). "Analysis of Weighted Networks." Physical Review E 70, 056131. Versiones ponderadas de las medidas de red estándar.
14. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres: Springer. Origen de la definición de grafo ponderado de la sección 1.
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Cambridge, Massachusetts: MIT Press.
16. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.