Problema del camino más corto

Problema computacional de la teoría de grafos.

Camino más corto (A, C, E, D, F) entre los vértices A y F en el gráfico dirigido ponderado

En teoría de grafos , el problema del camino más corto es el problema de encontrar un camino entre dos vértices (o nodos) en un gráfico tal que se minimice la suma de los pesos de sus aristas constituyentes.

El problema de encontrar el camino más corto entre dos intersecciones en un mapa de carreteras puede modelarse como un caso especial del problema del camino más corto en gráficos, donde los vértices corresponden a intersecciones y los bordes corresponden a segmentos de carretera, cada uno ponderado por la longitud de la carretera. segmento.

Definición

El problema del camino más corto se puede definir para grafos ya sean no dirigidos , dirigidos o mixtos . Se define aquí para gráficos no dirigidos; para gráficos dirigidos, la definición de camino requiere que los vértices consecutivos estén conectados por un borde dirigido apropiado.

Dos vértices son adyacentes cuando ambos inciden en una arista común. Una ruta en un gráfico no dirigido es una secuencia de vértices tal que es adyacente a for . Tal camino se llama camino de longitud desde hasta . ( Son variables; su numeración aquí se relaciona con su posición en la secuencia y no necesita relacionarse con ningún etiquetado canónico de los vértices). ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$ ${\displaystyle 1\leq i<n}$ ${\displaystyle P}$ ${\displaystyle n-1}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{n}}$ ${\displaystyle v_{i}}$

Sea donde está el borde incidente para ambos y . Dada una función de peso de valor real y un gráfico no dirigido (simple) , el camino más corto desde a es el camino (donde y ) que minimiza la suma en todos los casos posibles. Cuando cada borde del gráfico tiene un peso unitario o , esto equivale a encontrar el camino con menos aristas. ${\displaystyle E=\{e_{i,j}\}}$ ${\displaystyle e_{i,j}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle f:E\rightarrow \mathbb {R} }$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle v'}$ ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$ ${\displaystyle v_{1}=v}$ ${\displaystyle v_{n}=v'}$ ${\displaystyle n}$ ${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$ ${\displaystyle f:E\rightarrow \{1\}}$

El problema también se denomina a veces problema del camino más corto de un solo par , para distinguirlo de las siguientes variaciones:

• El problema de la ruta más corta de una sola fuente , en el que tenemos que encontrar las rutas más cortas desde un vértice de origen v hasta todos los demás vértices del gráfico.
• El problema del camino más corto de destino único , en el que tenemos que encontrar los caminos más cortos desde todos los vértices del gráfico dirigido hasta un vértice de destino único v . Esto se puede reducir al problema del camino más corto de una sola fuente invirtiendo los arcos en el gráfico dirigido.
• El problema del camino más corto de todos los pares , en el que tenemos que encontrar los caminos más cortos entre cada par de vértices v , v' en el gráfico.

Estas generalizaciones tienen algoritmos significativamente más eficientes que el enfoque simplista de ejecutar un algoritmo de ruta más corta de un solo par en todos los pares de vértices relevantes.

Algoritmos

Existen varios algoritmos bien conocidos para resolver este problema y sus variantes.

• El algoritmo de Dijkstra resuelve el problema de la ruta más corta de una sola fuente con un peso de borde no negativo.
• El algoritmo de Bellman-Ford resuelve el problema de fuente única si los pesos de los bordes pueden ser negativos.
• Un algoritmo de búsqueda* resuelve la ruta más corta de un solo par utilizando heurísticas para intentar acelerar la búsqueda.
• El algoritmo Floyd-Warshall resuelve los caminos más cortos de todos los pares.
• El algoritmo de Johnson resuelve todos los pares de caminos más cortos y puede ser más rápido que Floyd-Warshall en gráficos dispersos .
• El algoritmo de Viterbi resuelve el problema de la ruta estocástica más corta con un peso probabilístico adicional en cada nodo.

Se pueden encontrar algoritmos adicionales y evaluaciones asociadas en Cherkassky, Goldberg y Radzik (1996).

Rutas más cortas de fuente única

Gráficos no dirigidos

Gráficos no ponderados

Gráficos acíclicos dirigidos (DAG)

Un algoritmo que utiliza clasificación topológica puede resolver el problema de la ruta más corta de una sola fuente en el tiempo Θ ( E + V ) en DAG ponderados arbitrariamente. ^[1]

Gráficos dirigidos con pesos no negativos.

La siguiente tabla está tomada de Schrijver (2004), con algunas correcciones y adiciones. Un fondo verde indica un límite asintóticamente mejor en la tabla; L es la longitud (o peso) máxima entre todos los bordes, asumiendo pesos de borde enteros.

Gráficos dirigidos con pesos arbitrarios sin ciclos negativos.

Gráficos dirigidos con pesos arbitrarios con ciclos negativos.

Encuentra un ciclo negativo o calcula distancias a todos los vértices.

Gráficos planos con pesos no negativos.

Caminos más cortos de todos los pares

El problema del camino más corto de todos los pares encuentra los caminos más cortos entre cada par de vértices v , v' en el gráfico. El problema de los caminos más cortos de todos los pares para gráficos dirigidos no ponderados fue introducido por Shimbel (1953), quien observó que podía resolverse mediante un número lineal de multiplicaciones de matrices que toma un tiempo total de O ( V ⁴ ) .

Gráfico no dirigido

Gráfico dirigido

Aplicaciones

Los algoritmos de ruta más corta se aplican para buscar automáticamente direcciones entre ubicaciones físicas, como direcciones de manejo en sitios web de mapas web como MapQuest o Google Maps . Para esta aplicación se encuentran disponibles algoritmos rápidos especializados. ^[6]

Si uno representa una máquina abstracta no determinista como un gráfico donde los vértices describen estados y las aristas describen posibles transiciones, se pueden usar algoritmos de camino más corto para encontrar una secuencia óptima de elecciones para alcanzar un cierto estado objetivo, o para establecer límites inferiores en el tiempo necesario para lograrlo. llegar a un estado determinado. Por ejemplo, si los vértices representan los estados de un rompecabezas como el cubo de Rubik y cada borde dirigido corresponde a un solo movimiento o giro, se pueden usar algoritmos de ruta más corta para encontrar una solución que utilice el mínimo número posible de movimientos.

En una mentalidad de redes o telecomunicaciones , este problema de ruta más corta a veces se denomina problema de ruta de retardo mínimo y generalmente se relaciona con un problema de ruta más amplia . Por ejemplo, el algoritmo puede buscar el camino más corto (retardo mínimo) más ancho, o el camino más corto (retardo mínimo) más ancho.

Una aplicación más alegre son los juegos de los " seis grados de separación " que intentan encontrar el camino más corto en gráficos como las estrellas de cine que aparecen en una misma película.

Otras aplicaciones, a menudo estudiadas en la investigación de operaciones , incluyen el diseño de plantas e instalaciones, la robótica , el transporte y el diseño VLSI . ^[7]

Redes de carreteras

Una red de carreteras puede considerarse como un gráfico con pesos positivos. Los nodos representan cruces de carreteras y cada borde del gráfico está asociado con un segmento de carretera entre dos cruces. El peso de un borde puede corresponder a la longitud del segmento de carretera asociado, el tiempo necesario para atravesar el segmento o el costo de atravesar el segmento. Utilizando aristas dirigidas también es posible modelar calles de un solo sentido. Estos gráficos son especiales en el sentido de que algunos bordes son más importantes que otros para viajes de larga distancia (por ejemplo, autopistas). Esta propiedad se ha formalizado utilizando la noción de dimensión de la carretera. ^[8] Existe una gran cantidad de algoritmos que explotan esta propiedad y, por lo tanto, pueden calcular el camino más corto mucho más rápido de lo que sería posible en gráficos generales.

Todos estos algoritmos funcionan en dos fases. En la primera fase, el gráfico se preprocesa sin conocer el nodo de origen o de destino. La segunda fase es la fase de consulta. En esta fase se conocen los nodos de origen y de destino. La idea es que la red de carreteras sea estática, por lo que la fase de preprocesamiento se puede realizar una vez y utilizar para una gran cantidad de consultas en la misma red de carreteras.

El algoritmo con el tiempo de consulta más rápido conocido se llama etiquetado de hub y es capaz de calcular la ruta más corta en las redes de carreteras de Europa o Estados Unidos en una fracción de microsegundo. ^[9] Otras técnicas que se han utilizado son:

• ALT ( búsqueda A* , puntos de referencia y desigualdad de triángulos )
• Banderas de arco
• Jerarquías de contracción
• Enrutamiento del nodo de tránsito
• Poda basada en alcance
• Etiquetado
• Etiquetas de cubo

Problemas relacionados

Para problemas de camino más corto en geometría computacional , consulte el camino más corto euclidiano .

El camino múltiple desconectado más corto ^[10] es una representación de la red de caminos primitivos en el marco de la teoría de Reptation . El problema del camino más ancho busca un camino para que la etiqueta mínima de cualquier borde sea lo más grande posible.

Otros problemas relacionados pueden clasificarse en las siguientes categorías.

Caminos con restricciones

A diferencia del problema del camino más corto, que se puede resolver en tiempo polinomial en gráficos sin ciclos negativos, los problemas del camino más corto que incluyen restricciones adicionales en el camino de la solución deseada se llaman Primero el camino más corto restringido y son más difíciles de resolver. Un ejemplo es el problema del camino más corto restringido, ^[11] que intenta minimizar el costo total del camino y al mismo tiempo mantener otra métrica por debajo de un umbral determinado. Esto hace que el problema sea NP completo (no se cree que tales problemas se puedan resolver de manera eficiente para grandes conjuntos de datos, consulte P = problema NP ). Otro ejemplo de NP completo requiere que se incluya un conjunto específico de vértices en la ruta, ^[12] lo que hace que el problema sea similar al problema del viajante (TSP). El TSP es el problema de encontrar el camino más corto que pase por cada vértice exactamente una vez y regrese al inicio. El problema de encontrar el camino más largo en un gráfico también es NP-completo.

Observabilidad parcial

El problema del viajero canadiense y el problema estocástico del camino más corto son generalizaciones en las que el transportista no conoce completamente el gráfico, cambia con el tiempo o donde las acciones (recorridos) son probabilísticas. ^{[13] [14]}

Caminos estratégicos más cortos

A veces, las aristas de un gráfico tienen personalidad: cada arista tiene su propio interés egoísta. Un ejemplo es una red de comunicación, en la que cada borde es una computadora que posiblemente pertenece a una persona diferente. Diferentes computadoras tienen diferentes velocidades de transmisión, por lo que cada borde de la red tiene un peso numérico igual a la cantidad de milisegundos que se necesitan para transmitir un mensaje. Nuestro objetivo es enviar un mensaje entre dos puntos de la red en el menor tiempo posible. Si conocemos el tiempo de transmisión de cada computadora (el peso de cada borde), entonces podemos usar un algoritmo estándar de rutas más cortas. Si no conocemos los tiempos de transmisión, entonces tenemos que pedirle a cada computadora que nos diga su tiempo de transmisión. Pero los ordenadores pueden ser egoístas: un ordenador podría decirnos que su tiempo de transmisión es muy largo, para que no le molestemos con nuestros mensajes. Una posible solución a este problema es utilizar una variante del mecanismo VCG , que da a las computadoras un incentivo para revelar sus pesos reales.

Detección de ciclo negativo

En algunos casos, el objetivo principal no es encontrar el camino más corto, sino sólo detectar si el gráfico contiene un ciclo negativo. Para este propósito se pueden utilizar algunos algoritmos de rutas más cortas:

• El algoritmo de Bellman-Ford se puede utilizar para detectar un ciclo negativo en el tiempo . ${\displaystyle O(|V||E|)}$
• Cherkassky y Goldberg ^[15] examinan varios otros algoritmos para la detección de ciclos negativos.

Marco algebraico general sobre semirings: el problema del camino algebraico

Muchos problemas pueden plantearse como una forma del camino más corto para algunas nociones adecuadamente sustituidas de suma a lo largo de un camino y toma del mínimo. El enfoque general es considerar las dos operaciones como las de un semirredondo . La multiplicación de semirings se realiza a lo largo del camino y la suma se realiza entre caminos. Este marco general se conoce como problema de camino algebraico . ^{[16] [17] [18]}

La mayoría de los algoritmos clásicos del camino más corto (y los nuevos) pueden formularse resolviendo sistemas lineales sobre estructuras algebraicas de este tipo. ^[19]

Más recientemente, se ha desarrollado un marco aún más general para resolver estos problemas (y muchos menos obviamente relacionados) bajo el nombre de álgebras de valoración . ^[20]

Camino más corto en redes estocásticas dependientes del tiempo

En situaciones de la vida real, la red de transporte suele ser estocástica y dependiente del tiempo. De hecho, un viajero que recorre diariamente un enlace puede experimentar diferentes tiempos de viaje en ese enlace debido no sólo a las fluctuaciones en la demanda de viajes (matriz origen-destino) sino también a incidentes tales como zonas de trabajo, malas condiciones climáticas, accidentes y averías de vehículos. . Como resultado, una red estocástica dependiente del tiempo (STD) es una representación más realista de una red de carreteras real en comparación con una determinista. ^{[21] [22]}

A pesar de los considerables avances durante la última década, sigue siendo una cuestión controvertida cómo se debe definir e identificar una ruta óptima en las redes de carreteras estocásticas. En otras palabras, no existe una definición única de una ruta óptima en condiciones de incertidumbre. Una respuesta posible y común a esta pregunta es encontrar un camino con el tiempo de viaje mínimo esperado. La principal ventaja de utilizar este enfoque es que los algoritmos eficientes de ruta más corta introducidos para las redes deterministas se pueden emplear fácilmente para identificar la ruta con el tiempo de viaje mínimo esperado en una red estocástica. Sin embargo, la ruta óptima resultante identificada por este enfoque puede no ser confiable, porque este enfoque no aborda la variabilidad del tiempo de viaje. Para abordar este problema, algunos investigadores utilizan la distribución del tiempo de viaje en lugar del valor esperado, por lo que encuentran la distribución de probabilidad del tiempo total de viaje utilizando diferentes métodos de optimización, como la programación dinámica y el algoritmo de Dijkstra . ^[23] Estos métodos utilizan optimización estocástica , específicamente programación dinámica estocástica para encontrar el camino más corto en redes con longitud de arco probabilística. ^[24] El concepto de confiabilidad del tiempo de viaje se usa indistintamente con variabilidad del tiempo de viaje en la literatura de investigación sobre transporte, de modo que, en general, se puede decir que cuanto mayor sea la variabilidad en el tiempo de viaje, menor será la confiabilidad, y viceversa. .

Para tener en cuenta la confiabilidad del tiempo de viaje con mayor precisión, se han sugerido dos definiciones alternativas comunes para una ruta óptima en condiciones de incertidumbre. Algunos han introducido el concepto de ruta más confiable, con el objetivo de maximizar la probabilidad de llegar a tiempo o antes de un presupuesto de tiempo de viaje determinado. Otros, alternativamente, han propuesto el concepto de una ruta α-confiable basándose en el cual pretendían minimizar el presupuesto de tiempo de viaje requerido para asegurar una probabilidad de llegada a tiempo preespecificada.

Ver también

• Búsqueda bidireccional , un algoritmo que encuentra el camino más corto entre dos vértices en un gráfico dirigido
• Camino más corto euclidiano
• Red de flujo
• K ruta de ruta más corta
• Multiplicación de matrices min-plus
• Encontrar caminos
• Puente del camino más corto
• Árbol del camino más corto
• TRILL (Interconexión transparente de muchos enlaces)

Referencias

Notas

1. Cormen et al. 2001, pág. 655
2. Durr, Christoph; Heiligman, Mark; Hoyer, Peter; Mhalla, Mehdi (enero de 2006). "Complejidad de consultas cuánticas de algunos problemas de gráficos". Revista SIAM de Computación . 35 (6): 1310-1328. arXiv : quant-ph/0401091 . doi : 10.1137/050644719. ISSN  0097-5397. S2CID  14253494.
3. Dial, Robert B. (1969). "Algoritmo 360: bosque de camino más corto con ordenamiento topológico [H]". Comunicaciones de la ACM . 12 (11): 632–633. doi : 10.1145/363269.363610 . S2CID  6754003.
4. Durr, C.; Hoyer, P. (18 de julio de 1996). "Un algoritmo cuántico para encontrar el mínimo". arXiv : quant-ph/9607014 .
5. Nayebi, Arán; Williams, VV (22 de octubre de 2014). "Algoritmos cuánticos para problemas de caminos más cortos en instancias estructuradas". arXiv : 1410.6220 [cuántico-ph].
6. Sanders, Peter (23 de marzo de 2009). "Planificación rápida de rutas". Charla técnica de Google . Archivado desde el original el 11 de diciembre de 2021.
7. Chen, Danny Z. (diciembre de 1996). "Desarrollo de algoritmos y software para problemas de planificación de caminos geométricos". Encuestas de Computación ACM . 28 (4es). Artículo 18. doi :10.1145/242224.242246. S2CID  11761485.
8. Abraham, Ittai; Fiat, Amós; Goldberg, Andrew V .; Werneck, Renato F. "Dimensión de la carretera, caminos más cortos y algoritmos demostrablemente eficientes". Simposio ACM-SIAM sobre algoritmos discretos, páginas 782–793, 2010.
9. Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V .; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "Un algoritmo de etiquetado basado en centros para caminos más cortos en redes de carreteras". Simposio sobre algoritmos experimentales, páginas 230–241, 2011.
10. Kroger, Martín (2005). "El camino desconectado múltiple más corto para el análisis de entrelazamientos en sistemas poliméricos bidimensionales y tridimensionales". Comunicaciones de Física Informática . 168 (3): 209–232. Código Bib : 2005CoPhC.168..209K. doi :10.1016/j.cpc.2005.01.020.
11. Lozano, Leonardo; Medaglia, Andrés L (2013). "Sobre un método exacto para el problema del camino más corto restringido". Investigación de operaciones y computadoras . 40 (1): 378–384. doi :10.1016/j.cor.2012.07.008.
12. Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristán; Jacopin, Eric (2019). "Resolución óptima de problemas de planificación de rutas restringidas con redes convolucionales de gráficos y búsqueda de árbol optimizada". Conferencia internacional IEEE/RSJ 2019 sobre robots y sistemas inteligentes (IROS) . págs. 3519–3525. arXiv : 2108.01036 . doi :10.1109/IROS40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID  210706773.
13. Bar-Noy, Amotz; Schieber, Baruch (1991). "El problema del viajero canadiense". Actas del segundo simposio anual ACM-SIAM sobre algoritmos discretos : 261–270. CiteSeerX 10.1.1.1088.3015 . 
14. Nikolova, Evdokia; Karger, David R. "Planificación de rutas en condiciones de incertidumbre: el problema del viajero canadiense" (PDF) . Actas de la 23ª Conferencia Nacional sobre Inteligencia Artificial (AAAI) . págs. 969–974. Archivado (PDF) desde el original el 9 de octubre de 2022.
15. Cherkassky, Boris V.; Goldberg, Andrew V. (1 de junio de 1999). "Algoritmos de detección de ciclo negativo". Programación Matemática . 85 (2): 277–311. doi :10.1007/s101070050058. ISSN  1436-4646. S2CID  79739.
16. Pareja, Claude (1967). "Sur des algoritmos pour des problèmes de cheminement dans les graphes finis" [Sobre algoritmos para problemas de caminos en gráficos finitos]. En Rosentiehl, Pierre (ed.). Théorie des graphes (journées internationales d'études) [Teoría de los grafos (simposio internacional)] . Roma (Italia), julio de 1966. Dunod (París); Gordon y Breach (Nueva York). pag. 271. OCLC  901424694.
17. Derniame, Jean Claude; Par, Claude (1971). Problèmes de cheminement dans les graphes [ Problemas de trayectoria en gráficos ]. Dunod (París).
18. Baras, Juan; Theodorakopoulos, George (4 de abril de 2010). Problemas de ruta en redes. Editores Morgan y Claypool. págs.9–. ISBN 978-1-59829-924-3.
19. Gondrán, Michel; Minoux, Michel (2008). "Capítulo 4". Gráficos, dioides y semirings: nuevos modelos y algoritmos . Medios de ciencia y negocios de Springer. ISBN 978-0-387-75450-5.
20. Pouly, Marc; Kohlas, Jürg (2011). "Capítulo 6. Álgebras de valoración para problemas de trayectoria". Inferencia genérica: una teoría unificadora para el razonamiento automatizado . John Wiley e hijos. ISBN 978-1-118-01086-0.
21. Loui, RP, 1983. Rutas óptimas en gráficos con pesos estocásticos o multidimensionales. Comunicaciones de la ACM, 26(9), pp.670-676.
22. Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Búsqueda de rutas multiobjetivo en redes de carreteras estocásticas dependientes del tiempo utilizando un algoritmo genético de clasificación no dominado". Sistemas Expertos con Aplicaciones . 42 (12): 5056–5064. doi :10.1016/j.eswa.2015.02.046.
23. Olya, Mohammad Hessam (2014). "Encontrar el camino más corto en una longitud de arco de distribución de probabilidad gamma y exponencial combinada". Revista internacional de investigación operativa . 21 (1): 25–37. doi :10.1504/IJOR.2014.064020.
24. Olya, Mohammad Hessam (2014). "Aplicación del algoritmo de Dijkstra para el problema general del camino más corto con longitud de arco de distribución de probabilidad normal". Revista internacional de investigación operativa . 21 (2): 143-154. doi :10.1504/IJOR.2014.064541.

Bibliografía

• Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlín, James; Tarjan, Robert E. (abril de 1990). "Algoritmos más rápidos para el problema del camino más corto" (PDF) . Revista de la ACM . 37 (2). ACC: 213–223. doi :10.1145/77600.77615. hdl : 1721.1/47994 . S2CID  5499589. Archivado (PDF) desde el original el 9 de octubre de 2022.
• Bellman, Richard (1958). "Sobre un problema de enrutamiento". Trimestral de Matemática Aplicada . 16 : 87–90. doi : 10.1090/qam/102435 . SEÑOR  0102435.
• Bernstein, Aarón; Nanongkai, Danupon; Wulff-Nilsen, Christian (2022). "Rutas más cortas de fuente única de peso negativo en tiempo casi lineal". 2022 63.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS) . IEEE. págs. 600–611. arXiv : 2203.03456 . doi :10.1109/focs54457.2022.00063. ISBN 978-1-6654-5519-0. S2CID  247958461.
• Cherkassky, Boris V.; Goldberg, Andrew V .; Radzik, Tomasz (1996). "Algoritmos de caminos más cortos: teoría y evaluación experimental". Programación Matemática . Ser. R. 73 (2): 129-174. doi :10.1016/0025-5610(95)00021-6. SEÑOR  1392160.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "Rutas más cortas de fuente única y rutas más cortas de todos los pares". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 580–642. ISBN 0-262-03293-7.
• Dantzig, GB (enero de 1960). "En la ruta más corta a través de una red". Ciencias de la gestión . 6 (2): 187–190. doi :10.1287/mnsc.6.2.187.
• Dijkstra, EW (1959). "Una nota sobre dos problemas en relación con los gráficos". Matemática numérica . 1 : 269–271. doi :10.1007/BF01386390. S2CID  123284777.
• Ford, LR (1956). Teoría del flujo de redes (Informe). Santa Mónica, CA: RAND Corporation. P-923.
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes . 25º Simposio Anual sobre Fundamentos de la Informática. IEEE . págs. 338–346. doi :10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X.
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes". Revista de la Asociación de Maquinaria de Computación . 34 (3): 596–615. doi : 10.1145/28869.28874 . S2CID  7904683.
• Gabow, HN (1983). "Algoritmos de escalado para problemas de red" (PDF) . Actas del 24º Simposio anual sobre fundamentos de la informática (FOCS 1983) . págs. 248-258. doi :10.1109/SFCS.1983.68.
• Gabow, Harold N. (1985). "Algoritmos de escalado para problemas de red". Revista de Ciencias de la Computación y de Sistemas . 31 (2): 148–168. doi : 10.1016/0022-0000(85)90039-X . SEÑOR  0828519.
• Hagerup, Torben (2000). "Rutas más cortas mejoradas en Word RAM". En Montanari, Ugo; Rolim, José DP; Welzl, Emo (eds.). Actas del 27º Coloquio Internacional sobre Autómatas, Lenguajes y Programación . págs. 61–72. ISBN 978-3-540-67715-4.
• Henzinger, Mónica R.; Klein, Felipe; Rao, Satish; Subramanian, Sairam (1997). "Algoritmos de ruta más corta más rápidos para gráficos planos". Revista de Ciencias de la Computación y de Sistemas . 55 (1): 3–23. doi : 10.1006/jcss.1997.1493 .
• Johnson, Donald B. (1977). "Algoritmos eficientes para caminos más cortos en redes dispersas". Revista de la ACM . 24 (1): 1–13. doi : 10.1145/321992.321993 . S2CID  207678246.
• Johnson, Donald B. (diciembre de 1981). "Una cola de prioridad en la que las operaciones de inicialización y cola toman O (log log D ) tiempo". Teoría de Sistemas Matemáticos . 15 (1): 295–309. doi :10.1007/BF01786986. SEÑOR  0683047. S2CID  35703411.
• Karlsson, Rolf G.; Poblete, Patricio V. (1983). "Un algoritmo O (m log log D) para caminos más cortos". Matemática Aplicada Discreta . 6 (1): 91–93. doi : 10.1016/0166-218X(83)90104-X . SEÑOR  0700028.
• Leyzorek, M.; Gris, RS; Johnson, AA; Ladew, WC; Meaker, SR hijo; Petry, RM; Seitz, RN (1957). Investigación de técnicas modelo - Primer informe anual - 6 de junio de 1956 - 1 de julio de 1957 - Estudio de técnicas modelo para sistemas de comunicación . Cleveland, Ohio: Instituto Case de Tecnología.
• Moore, EF (1959). "El camino más corto a través de un laberinto". Actas de un simposio internacional sobre la teoría de la conmutación (Cambridge, Massachusetts, 2 a 5 de abril de 1957) . Cambridge: Prensa de la Universidad de Harvard. págs. 285–292.
• Pettie, Seth; Ramachandran, Vijaya (2002). "Calcular caminos más cortos con comparaciones y sumas". Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos . págs. 267–276. ISBN 978-0-89871-513-2.
• Pettie, Seth (26 de enero de 2004). "Un nuevo enfoque para los caminos más cortos de todos los pares en gráficos ponderados reales". Informática Teórica . 312 (1): 47–74. doi : 10.1016/s0304-3975(03)00402-x .
• Pollack, Mauricio; Wiebenson, Walter (marzo-abril de 1960). "Solución del problema de la ruta más corta: una revisión". Ópera. Res . 8 (2): 224–230. doi :10.1287/opre.8.2.224. Atribuye el algoritmo de Dijkstra a Minty ("comunicación privada") en la p. 225.
• Schrijver, Alejandro (2004). Optimización combinatoria: poliedros y eficiencia . Algoritmos y Combinatoria. vol. 24. Saltador. vol.A, sección 7.5b, pág. 103.ISBN​ 978-3-540-20456-5.
• Shimbel, Alfonso (1953). "Parámetros estructurales de las redes de comunicación". Boletín de Biofísica Matemática . 15 (4): 501–507. doi :10.1007/BF02476438.
• Shimbel, A. (1955). "Estructura en redes de comunicación". Actas del Simposio sobre Redes de Información . Nueva York, NY: Polytechnic Press del Instituto Politécnico de Brooklyn. págs. 199-203.
• Thorup, Mikkel (1999). "Rutas más cortas no dirigidas de una sola fuente con pesos enteros positivos en tiempo lineal". Revista de la ACM . 46 (3): 362–394. doi : 10.1145/316542.316548 . S2CID  207654795.
• Thorup, Mikkel (2004). "Colas de prioridad entera con clave de disminución en tiempo constante y el problema de los caminos más cortos de una sola fuente". Revista de Ciencias de la Computación y de Sistemas . 69 (3): 330–353. doi : 10.1016/j.jcss.2004.04.003 .
• Whiting, PD; Hillier, JA (marzo-junio de 1960). "Un método para encontrar la ruta más corta a través de una red de carreteras". Investigación operativa trimestral . 11 (1/2): 37–40. doi :10.1057/jors.1960.32.
• Williams, Ryan (2014). "Rutas más cortas de todos los pares más rápidas a través de la complejidad del circuito". Actas del 46º Simposio Anual ACM sobre Teoría de la Computación (STOC '14) . Nueva York: ACM. págs. 664–673. arXiv : 1312.6680 . doi :10.1145/2591796.2591811. SEÑOR  3238994.

Otras lecturas

• Altıntaş, Gökhan (2020). Soluciones exactas de problemas del camino más corto basadas en analogías mecánicas: en relación con los laberintos. Servicios digitales de Amazon LLC. ISBN 9798655831896.
• Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "Problema de ruta más corta de fuente única limitada de salida totalmente dinámica". Proc. Séptimo año. Síntoma ACM-SIAM. Algoritmos discretos . Atlanta, Georgia. págs. 212-221. CiteSeerX  10.1.1.32.9856 .
• Dreyfus, SE (octubre de 1967). Una evaluación de algunos algoritmos de ruta más corta (PDF) (Reporte). Proyecto Rand. Fuerza Aérea de los Estados Unidos. RM-5433-PR. Archivado (PDF) desde el original el 17 de noviembre de 2015.DTIC AD-661265.