Camino mínimo

Objetivos

• Sumar los pesos de un camino, no contar aristas.
• Comparar todos los caminos simples de A a D.
• Elegir el mínimo y explicar por qué un atajo visual puede ser más largo.

El peso manda, no el número de saltos

En un grafo ponderado cada arista lleva un número: minutos, euros o kilómetros. La longitud de un camino es la suma de esos pesos. El camino mínimo entre dos vértices es el de menor suma. No tiene por qué ser el que tiene menos aristas.

peso = número de la arista · longitud de un camino = suma de pesos · camino simple = no repite vértices · en el dibujo el trazo ámbar es A-C-B-D y el gris son las aristas que no entran en ese mínimo

De A a D hay tres caminos simples. A-B-D suma 4+3 = 7. A-C-D suma 2+5 = 7. A-C-B-D suma 2+1+3 = 6. El tercero usa tres aristas y aun así es más corto que los de dos, porque C-B pesa solo 1 y evita la arista C-D, que pesa 5.

No hace falta un algoritmo con nombre para un grafo de cuatro vértices: se enumeran los caminos simples y se comparan. En un grafo grande esa enumeración se sustituye por un método ordenado (como el de Dijkstra si los pesos son positivos). La idea no cambia: no te detienes en el primer camino que llega.

Gráfico del ejemplo

La figura no es decoración: los trazos corresponden a los números del ejemplo 1.

Ejemplo resuelto 1 — Las tres sumas

Con los pesos del gráfico, calcula la longitud de A-B-D, de A-C-D y de A-C-B-D.

1. A-B-D usa las aristas de peso 4 y 3. Longitud 4+3 = 7.Glosa: no cuentes «dos aristas» como longitud 2; 2 sería un recuento, no una suma de pesos.
2. A-C-D usa 2 y 5. Longitud 2+5 = 7. Llega en dos saltos, igual que el anterior, y cuesta lo mismo.Glosa: empate en 7 no significa que sean el mismo camino; solo que la suma coincide.
3. A-C-B-D usa 2, 1 y 3. Longitud 2+1+3 = 6. Es el trazo ámbar del SVG.Glosa: tres aristas pueden sumar menos que dos si una de las cortas evita un peso grande.
4. El mínimo de 7, 7 y 6 es 6. Cualquier otro recorrido que repita un vértice solo añadiría peso positivo y no mejoraría.Glosa: con pesos positivos, un rodeo no acorta. Por eso basta mirar caminos simples.

Ejemplo resuelto 2 — Por qué C-D no es un atajo

Explica, con la resta de los números, por qué ir de C a D directo es peor que C-B-D.

1. De C a D directo: peso 5.Glosa: es la arista gris inferior derecha.
2. De C a D por B: C-B pesa 1 y B-D pesa 3, suma 4.Glosa: 1+3 = 4, que ya es menor que 5 antes de mirar el resto del viaje.
3. Diferencia: 5 − 4 = 1. El rodeo por B ahorra 1 respecto del directo.Glosa: por eso el camino completo que usa C-D queda en 7 y el que usa C-B-D queda en 6.
4. Conclusión local: entre C y D, con estos pesos, el mínimo no es la arista directa. Hay que comprobar los desvíos.Glosa: «directo» en el dibujo no es «mínimo» en la suma.

Ejemplo resuelto 3 — Cambia un peso

Si el peso de C-B pasa de 1 a 4 y el resto no cambia, ¿cuál es el nuevo mínimo de A a D?

1. A-B-D no usa C-B: sigue en 4+3 = 7.Glosa: un peso que no está en el camino no lo altera.
2. A-C-D tampoco usa C-B: sigue en 2+5 = 7.Glosa: el empate anterior se mantiene.
3. A-C-B-D pasa a 2+4+3 = 9, que ya es peor que 7.Glosa: el antiguo mínimo se rompe porque su arista barata ha dejado de serlo.
4. El nuevo mínimo es 7, compartido por A-B-D y A-C-D. Ya no hay un único camino mínimo.Glosa: di los dos. Quedarte con el ámbar del gráfico, sin rehacer la suma, es el error.

Ejercicios

Escribe el razonamiento completo en el editor, no solo la cifra. Si el enunciado pide figura, dibújala en el lienzo de esta misma página.

Dibuja en el lienzo

Reproduce a mano el gráfico del ejemplo: ejes o nodos, los datos numéricos y una frase con la conclusión. El botón borra el lienzo sin salir de la lección.

Comprueba

Tres preguntas. Responde mentalmente antes de abrir el porqué.