El problema del camino mínimo busca una ruta entre vértices cuyo costo total sea el menor posible. La respuesta depende de cómo se valoran las aristas y de las propiedades de esos pesos.
Saber que un destino es alcanzable no siempre es suficiente. En una red vial queremos minimizar distancia o tiempo; en comunicaciones, latencia; en logística, costo; y en un juego, cantidad de movimientos.
El problema del camino mínimo consiste en encontrar, entre todos los caminos que conectan un origen con un destino, aquel cuya suma de costos sea menor.
Un camino es una secuencia de vértices conectados por aristas. Debemos distinguir dos medidas:
| Medida | Definición |
|---|---|
| Longitud | Cantidad de aristas utilizadas |
| Costo o peso | Suma de los valores asociados a las aristas |
En un grafo sin pesos, cada arista puede considerarse de costo 1 y ambas medidas coinciden. En un grafo ponderado, el camino con menos aristas no tiene por qué ser el más barato.
Si P = (v₀, v₁, ..., vₖ) es un camino y w(u, v) representa el peso de una arista, su costo es:
La distancia mínima δ(s, t) es el menor costo entre todos los caminos desde s hasta t. Si t no es alcanzable desde s, se utiliza el valor infinito.
Los pesos modelan el criterio que deseamos optimizar:
Una misma red puede producir rutas óptimas diferentes según la métrica elegida.
| Variante | Pregunta |
|---|---|
| Un origen, un destino | ¿Cuál es la mejor ruta de s hasta t? |
| Un origen, todos los destinos | ¿Cuáles son las distancias desde s? |
| Todos los pares | ¿Cuál es la distancia entre cada par de vértices? |
| Varios orígenes | ¿Cuál fuente llega con menor costo a cada vértice? |
Explora las rutas simples de A hasta F. Cada paso resalta un camino y suma sus pesos. Observa que utilizar menos aristas no garantiza obtener el costo mínimo.
Ruta actual
Suma de pesos
Evaluación
Verde marca la ruta evaluada. El botón Menos aristas elige A → D → F, pero su costo es mayor que el de la ruta óptima.
Los caminos mínimos poseen una propiedad esencial: cualquier subcamino de un camino mínimo también debe ser mínimo entre sus propios extremos.
Si existiera un subcamino más barato, podríamos reemplazar el original y obtener una ruta total de menor costo, contradiciendo que era óptima.
Los algoritmos suelen mantener una estimación distancia[v] del mejor costo conocido desde el origen hasta v.
El infinito indica que todavía no conocemos ningún camino. A medida que se examinan aristas, las estimaciones pueden disminuir.
Relajar la arista u → v consiste en comprobar si llegar a v pasando por u mejora la distancia conocida.
La relajación es la operación central de Dijkstra, Bellman-Ford y otros algoritmos. Lo que cambia entre ellos es el orden y la cantidad de veces que relajan las aristas.
Supongamos que conocemos distancia[A] = 4, la arista A → B pesa 3 y la mejor estimación actual para B es 10.
Si la estimación de B fuera 6, pasar por A no produciría una mejora y no se modificaría ningún valor.
Las distancias indican el costo, pero no describen la ruta. Cada vez que una relajación mejora a v guardamos el vértice u como su predecesor.
La cadena se construye en sentido inverso y después se invierte:
function reconstruirCamino(predecesor, origen, destino) {
const camino = [];
for (let actual = destino; actual != null;
actual = predecesor[actual]) {
camino.push(actual);
}
camino.reverse();
return camino[0] === origen ? camino : null;
}Cuando todas las aristas valen lo mismo, BFS encuentra el camino mínimo en cantidad de aristas. Los vértices se descubren por niveles de distancia creciente.
Usar un algoritmo ponderado en este caso puede funcionar, pero agrega complejidad innecesaria.
| Pesos | Algoritmo habitual | Observación |
|---|---|---|
| Todos iguales | BFS | Minimiza cantidad de aristas |
| No negativos | Dijkstra | Puede fijar distancias de forma voraz |
| Puede haber negativos | Bellman-Ford | También detecta ciclos negativos alcanzables |
| Todos los pares | Floyd-Warshall | Trabaja con una matriz de distancias |
Elegir el algoritmo incorrecto puede producir resultados falsos. Dijkstra, por ejemplo, no es válido en general cuando existen pesos negativos.
Un ciclo negativo tiene una suma de pesos menor que cero. Si es alcanzable desde el origen y permite continuar hacia el destino, podemos recorrerlo repetidamente y reducir el costo sin límite.
En ese caso no se trata simplemente de encontrar una ruta muy barata: el valor óptimo tiende a −∞.
Los algoritmos de camino mínimo pueden aplicarse a ambos tipos. Una arista no dirigida {u, v} suele representarse como dos aristas dirigidas u → v y v → u con el mismo peso.
Un peso negativo en un grafo no dirigido crea inmediatamente un ciclo negativo: podemos ir por la arista y regresar por ella, acumulando dos veces ese valor negativo.
Cuando calculamos las mejores rutas desde un origen hacia todos los vértices, las relaciones de predecesor forman habitualmente un árbol dirigido con raíz en el origen.
Este árbol permite reconstruir una ruta mínima hacia cada destino alcanzable. No debe confundirse con un árbol generador mínimo: uno optimiza rutas desde una raíz y el otro minimiza el peso total usado para conectar toda la red.
| Estructura | Objetivo |
|---|---|
| Árbol de caminos mínimos | Minimizar la distancia desde un origen |
| Árbol generador mínimo | Minimizar el peso total de las aristas elegidas |
El problema del camino mínimo combina modelado y algoritmo: primero debemos decidir qué representa el costo y después elegir un método compatible con los pesos. Distancias, relajaciones y predecesores forman el lenguaje común de sus principales soluciones.
En el próximo tema estudiaremos Dijkstra, un algoritmo voraz para caminos mínimos cuando todas las aristas tienen pesos no negativos.