6.3: Camino más corto

Última actualización
Guardar como PDF

Page ID: 110632

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Cuando visitas un sitio web como Google Maps o usas tu Smartphone para pedir indicaciones desde tu casa hasta la casa de tu tía en Pasadena, generalmente estás buscando un camino más corto entre las dos ubicaciones. Estas aplicaciones informáticas utilizan representaciones de los mapas de calles como gráficas, con tiempos de manejo estimados como pesos de borde.

Si bien a menudo es posible encontrar un camino más corto en una pequeña gráfica por conjetura y verificación, nuestro objetivo en este capítulo es desarrollar métodos para resolver problemas complejos de manera sistemática siguiendo algoritmos. Un algoritmo es un procedimiento paso a paso para resolver un problema. El algoritmo de Dijkstra (pronunciado dike-stra) encontrará el camino más corto entre dos vértices.

Algoritmo de Dijkstra

Marque el vértice final con una distancia de cero. Designar este vértice como actual.
Encuentra todos los vértices que conducen al vértice actual. Calcular sus distancias hasta el final. Dado que ya sabemos la distancia que está el vértice actual desde el final, esto solo requerirá agregar el borde más reciente. No registre esta distancia si es mayor que una distancia previamente registrada.
Marcar el vértice actual como visitado. Nunca volveremos a mirar este vértice.
Marque el vértice con la distancia más pequeña como corriente y repita desde el paso 2.

Ejemplo 3

Supongamos que necesita viajar de Tacoma, WA (vértice T) a Yakima, WA (vértice Y). Al mirar un mapa, parece que conducir por Auburn (A) y luego Mount Rainier (MR) podría ser el más corto, pero no está del todo claro ya que esa carretera es probablemente más lenta que tomar la carretera principal por North Bend (NB). A continuación se muestra una gráfica con los tiempos de viaje en minutos. También se muestra una ruta alternativa a través de Eatonville (E) y Packwood (P).

$gt12.svg$

Solución

$gt13.svg$ Paso 1: Marcar el vértice final con una distancia de cero. Las distancias se registrarán en [corchetes] después del nombre del vértice.

$gt14.svg$ Paso 2: Por cada vértice que conduce a Y, calculamos la distancia hasta el final. Por ejemplo, NB es una distancia de 104 desde el extremo, y MR es 96 desde el extremo. Recuerda que las distancias en este caso se refieren al tiempo de viaje en minutos.

Paso 3 y 4: Marcamos Y como visitada, y marcamos el vértice con la menor distancia registrada como actual. En este punto, P será designado actual. Volver al paso 2.

$gt15.svg$ Paso 2 (#2): Por cada vértice que conduce a P (y no conduce a un vértice visitado) encontramos la distancia desde el final. Dado que E está a 96 minutos de P, y ya calculamos P es 76 minutos de Y, podemos calcular que E es 96+76 = 172 minutos de Y.

Si hacemos el mismo cálculo para MR, calcularíamos 76+27 = 103. Dado que esta es mayor que la distancia previamente registrada de Y a MR, no la reemplazaremos.

Paso 3 y 4 (#2): Marcamos P como visitado, y designamos el vértice con la menor distancia registrada como actual: MR Volver al paso 2.

$gt16.svg$ Paso 2 (#3): Por cada vértice que conduce a MR (y que no conduce a un vértice visitado) encontramos la distancia hasta el final. El único vértice a considerar es A, ya que ya visitamos Y y P. Añadiendo la distancia de MR 96 a la longitud de A a MR da la distancia 96+79 = 175 minutos de A a Y.

Paso 3 y 4 (#3): Marcamos MR como visitado, y designamos el vértice con menor distancia registrada como actual: NB. Volver al paso 2.

$gt17.svg$ Paso 2 (#4): Por cada vértice que conduce a NB, encontramos la distancia hasta el final. Sabemos que la distancia más corta de NB a Y es 104 y la distancia de A a NB es 36, por lo que la distancia de A a Y a través de NB es 104+36 = 140. Dado que esta distancia es más corta que la distancia calculada previamente de Y a A a través de MR, la reemplazamos.

Paso 3 y 4 (#4): Marcamos NB como visitado, y designamos A como actual, ya que ahora tiene la distancia más corta.

$gt18.svg$ Paso 2 (#5): T es el único vértice no visitado que conduce a A, así calculamos la distancia de T a Y a través de A: 20+140 = 160 minutos.

Paso 3 y 4 (#5): Marcamos A como visitada, y designamos E como actual.

Paso 2 (#6): El único vértice no visitado que conduce a E es T. Calculando la distancia de T a Y a través de E, calculamos$172+57 = 229$ minutos. Dado que este es más largo que el tiempo marcado existente, no lo reemplazamos.

Paso 3 (#6): Marcamos E como visitada. Ya que todos los vértices han sido visitados, ya hemos terminado.

De esto, sabemos que el camino más corto de Tacoma a Yakima tomará 160 minutos. Rastreando qué secuencia de aristas rindió 160 minutos, vemos que el camino más corto es T-A-NB-Y.

El algoritmo de Dijkstra es un algoritmo óptimo, lo que significa que siempre produce el camino más corto real, no solo un camino que es bastante corto, siempre que exista uno. Este algoritmo también es eficiente, lo que significa que se puede implementar en un tiempo razonable. El algoritmo de Dijkstra toma alrededor de V ² cálculos, donde V es el número de vértices en una gráfica [1]. Una gráfica con 100 vértices tomaría alrededor de 10 mil cálculos. Si bien eso sería mucho que hacer a mano, no es mucho que pueda manejar la computadora. Es por esta eficiencia que la unidad GPS de su automóvil puede calcular las direcciones de manejo en solo unos segundos.

Por el contrario, un algoritmo ineficiente podría intentar enumerar todas las rutas posibles y luego calcular la longitud de cada ruta. Intentar enumerar todas las rutas posibles podría tomar fácilmente 10 ²⁵ cálculos para calcular la ruta más corta con solo 25 vértices; ¡eso es un 1 con 25 ceros después de él! Para poner eso en perspectiva, la computadora más rápida del mundo aún pasaría más de 1000 años analizando todos esos caminos.

Ejemplo 4

Una compañía naviera necesita enrutar un paquete de Washington, D.C. a San Diego, CA. Para minimizar los costos, el paquete primero se enviará a su centro de procesamiento en Baltimore, MD y luego se enviará como parte de envíos masivos entre sus diversos centros de procesamiento, terminando en su centro de procesamiento en Bakersfield, CA. De ahí se entregará en una camioneta pequeña a San Diego.

Los tiempos de viaje, en horas, entre sus centros de procesamiento se muestran en la siguiente tabla. Se han agregado tres horas a cada tiempo de viaje para su procesamiento. Encuentra el camino más corto de Baltimore a Bakersfield. $clipboard_e41f1a50ddf89a90a45a6f95a35f9da9f.png$

Solución

Si bien podríamos dibujar una gráfica, también podemos trabajar directamente desde la mesa.

Paso 1: El vértice final, Bakersfield, está marcado como actual.

Paso 2: Todas las ciudades conectadas a Bakersfield, en este caso Denver y Dallas, tienen calculadas sus distancias; marcaremos esas distancias en los encabezados de columna.

Paso 3 y 4: Mark Bakersfield como visitado. Aquí, lo estamos haciendo sombreando la fila y columna correspondientes de la tabla. Marcamos Denver como actual, se muestra en negrita, ya que es el vértice con la distancia más corta.

$clipboard_e759bf79d3d787956ad0bf4fcda7511b5.png$

Paso 2 (#2): Para las ciudades conectadas a Denver, calcule la distancia hasta el final. Por ejemplo, Chicago está a 18 horas de Denver, y Denver está a 19 horas del final, la distancia para Chicago hasta el final es de 18+19 = 37 (Chicago a Denver a Bakersfield). Atlanta está a 24 horas de Denver, por lo que la distancia hasta el final es de 24+19 = 43 (Atlanta a Denver a Bakersfield).

Paso 3 y 4 (#2): Marcamos Denver como visitada y marcamos a Dallas como actual.

$clipboard_e712dc3c5e7835dfab45640e51dea54f0.png$

Paso 2 (#3): Para ciudades conectadas a Dallas, calcule la distancia hasta el final. Para Chicago, la distancia de Chicago a Dallas es de 18 y de Dallas al final es de 25, por lo que la distancia de Chicago al final por Dallas sería de 18+25 = 43. Dado que esta es más larga que la distancia actualmente marcada para Chicago, no la reemplazamos. Para Atlanta, calculamos 15+25 = 40. Dado que esta es más corta que la distancia actualmente marcada para Atlanta, reemplazamos la distancia existente.

Paso 3 y 4 (#3): Marcamos Dallas como visitado, y marcamos Chicago como actual.

$clipboard_ebf2973d1d12fecdccbec6fd90a959810.png$

Paso 2 (#4): Baltimore y Atlanta son las únicas ciudades no visitadas conectadas con Chicago. Para Baltimore, calculamos 15+37 = 52 y marcamos esa distancia. Para Atlanta, calculamos 14+37 = 51. Dado que esta es más larga que la distancia existente de 40 para Atlanta, no reemplazamos esa distancia.

Paso 3 y 4 (#4): Marcar Chicago como visitada y Atlanta como actual.

$clipboard_e51f52531779084f400b21d9aeade2271.png$

Paso 2 (#5): La distancia de Atlanta a Baltimore es de 14. Añadiendo que a la distancia ya calculada para Atlanta da una distancia total de 14+40 = 54 horas de Baltimore a Bakersfield pasando por Atlanta. Dado que esta es mayor que la distancia actualmente calculada, no reemplazamos la distancia por Baltimore.

Paso 3 y 4 (#5): Marcamos Atlanta como visitada. Todas las ciudades han sido visitadas y ya terminamos.

La ruta más corta de Baltimore a Bakersfield tomará 52 horas, y recorrerá Chicago y Denver.

Pruébalo ahora 2

Encuentra el camino más corto entre los vértices A y G en la gráfica a continuación.

$gt19.svg$

Contestar: El camino más corto es ABDEG, con longitud 13

[1] Se puede hacer que se ejecute más rápido a través de diversas optimizaciones a la implementación.