6. Grafos ponderados

6.1 Introducción

Saber que dos vértices están conectados no siempre es suficiente. Dos ciudades pueden estar unidas por varias rutas, pero cada trayecto puede requerir una distancia, un tiempo o un costo diferente.

Los grafos ponderados incorporan un valor numérico a cada arista. Ese valor se denomina peso y permite comparar conexiones y optimizar recorridos.

6.2 ¿Qué es un peso?

Un peso es un valor asociado a una arista. Su significado depende del sistema representado.

La expresión indica que la arista entre A y B tiene peso 7. Ese número podría representar kilómetros, minutos, dinero, consumo de energía o nivel de dificultad.

6.3 Función de peso

Formalmente, podemos pensar el peso como una función w que asigna un número a cada arista del grafo.

El grafo ponderado puede expresarse como G = (V, E, w), donde V es el conjunto de vértices, E el conjunto de aristas y w la función de peso.

6.4 ¿Qué pueden representar los pesos?

6.5 Simulación interactiva: compara rutas y pesos

Selecciona una ruta entre A y E para ver su costo total. Pulsa una arista en el gráfico y modifica su peso con el control deslizante; la mejor ruta se recalculará automáticamente.

La ruta resaltada en color rosa es la seleccionada. La ruta óptima se indica en el panel. Cambia los pesos hasta lograr que otra alternativa resulte más económica.

6.6 Peso de un camino

El peso de un camino se obtiene sumando los pesos de todas las aristas que lo forman.

Esta suma permite comparar rutas completas. En otros problemas, la combinación podría seguir una regla diferente, pero la suma es el caso más habitual.

6.7 Menos aristas no significa menor costo

En un grafo sin pesos, solemos medir una ruta por la cantidad de aristas. En un grafo ponderado debemos considerar la suma de sus valores.

Esta diferencia explica por qué el recorrido en anchura no siempre resuelve caminos mínimos ponderados y necesitamos algoritmos como Dijkstra.

6.8 Pesos positivos, cero y negativos

Dijkstra presupone pesos no negativos. Cuando existen pesos negativos puede utilizarse Bellman-Ford. Los ciclos de peso negativo requieren atención porque permiten disminuir el costo indefinidamente.

6.9 Representar un grafo ponderado en JavaScript

Cada arista puede almacenarse como un objeto con sus extremos y su peso.

const aristas = [
  { origen: "A", destino: "B", peso: 3 },
  { origen: "A", destino: "C", peso: 2 },
  { origen: "B", destino: "D", peso: 4 }
];

for (const arista of aristas) {
  console.log(`${arista.origen}—${arista.destino}: ${arista.peso}`);
}

6.10 Calcular el costo de una ruta

Si la ruta se expresa como una secuencia de vértices, podemos buscar cada arista y acumular su peso.

const pesos = {
  "A-B": 3,
  "B-D": 4,
  "D-E": 2
};

function costoRuta(ruta) {
  let total = 0;
  for (let i = 0; i < ruta.length - 1; i++) {
    total += pesos[`${ruta[i]}-${ruta[i + 1]}`];
  }
  return total;
}

console.log(costoRuta(["A", "B", "D", "E"]));

6.11 Elegir correctamente el peso

El peso debe representar aquello que realmente queremos optimizar. La ruta más corta en kilómetros puede no ser la más rápida, económica o segura.

6.12 Errores comunes

• Confundir el peso de una arista con la cantidad de aristas del camino.
• Comparar rutas sin sumar todos sus pesos.
• Mezclar unidades, por ejemplo minutos y kilómetros, en la misma suma.
• Usar Dijkstra cuando existen pesos negativos.
• Elegir distancia como peso cuando el objetivo real es minimizar el tiempo.
• Suponer que el peso de ida y vuelta debe ser idéntico en un grafo dirigido.

6.13 Qué debes recordar de este tema

• Un grafo ponderado asigna un valor a cada arista.
• El peso puede representar distancia, tiempo, costo, capacidad o riesgo.
• El costo de un camino suele ser la suma de los pesos de sus aristas.
• La ruta con menos aristas no siempre tiene el menor costo.
• El significado y la unidad de los pesos deben ser consistentes.
• La presencia de pesos negativos condiciona el algoritmo que podemos utilizar.

6.14 Conclusión

Los pesos convierten las conexiones de un grafo en decisiones cuantificables. Gracias a ellos podemos comparar alternativas y buscar recorridos que minimicen distancia, tiempo, dinero u otros recursos.

En el próximo tema estudiaremos los grafos completos, donde cada par de vértices diferentes está conectado.