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 grafo tal que la suma de los pesos de sus aristas constituyentes se minimice. ^[1]

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 las intersecciones y los bordes corresponden a los segmentos de la carretera, cada uno ponderado por la longitud o la distancia de cada segmento.

Definición

El problema de la ruta más corta se puede definir para grafos no dirigidos , dirigidos o mixtos . Aquí se define para grafos no dirigidos; para grafos dirigidos, la definición de ruta requiere que los vértices consecutivos estén conectados por una arista dirigida apropiada. ^[2]

Dos vértices son adyacentes cuando ambos inciden sobre una arista común. Un camino en un grafo no dirigido es una secuencia de vértices tal que es adyacente a para . Este tipo de camino se denomina camino de longitud de a . (Las 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 es la arista incidente tanto a como . Dada una función de peso de valor real y un grafo no dirigido (simple) , la ruta más corta desde hasta es la ruta (donde y ) que, en general, minimiza la suma Cuando cada arista en el grafo tiene peso unitario o , esto es equivalente a encontrar la ruta 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 fuente v a todos los demás vértices del gráfico.
• Problema de la ruta más corta con un único destino , en el que tenemos que encontrar las rutas más cortas desde todos los vértices del grafo dirigido hasta un único vértice de destino v . Esto se puede reducir al problema de la ruta más corta con un único origen invirtiendo los arcos en el grafo 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 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 solo pesos de aristas no negativos.
• El algoritmo Bellman-Ford resuelve el problema de fuente única si los pesos de los bordes pueden ser negativos.
• Un algoritmo de búsqueda A* resuelve la ruta más corta de un solo par utilizando heurística para intentar acelerar la búsqueda.
• El algoritmo Floyd-Warshall resuelve todos los pares de caminos más cortos.
• 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 una sola fuente

Grafos no dirigidos

Gráficos no ponderados

Grafos acíclicos dirigidos

Un algoritmo que utiliza ordenamiento topológico puede resolver el problema de la ruta más corta de una sola fuente en el tiempo Θ( E + V ) en gráficos acíclicos dirigidos ponderados arbitrariamente. ^[3]

Grafos dirigidos con pesos no negativos

La siguiente tabla se ha extraído de Schrijver (2004), con algunas correcciones y añadidos. El fondo verde indica un límite asintóticamente óptimo en la tabla; L es la longitud (o peso) máxima entre todas las aristas, suponiendo que los pesos de las aristas son enteros.

Grafos dirigidos con pesos arbitrarios sin ciclos negativos

Grafos dirigidos con pesos arbitrarios con ciclos negativos

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

Gráficos planares con pesos no negativos

Aplicaciones

Los flujos de red ^[6] son ​​un concepto fundamental en la teoría de grafos y la investigación de operaciones, que se utilizan a menudo para modelar problemas que involucran el transporte de bienes, líquidos o información a través de una red. Un problema de flujo de red generalmente involucra un grafo dirigido donde cada borde representa una tubería, un cable o una carretera, y cada borde tiene una capacidad, que es la cantidad máxima que puede fluir a través de él. El objetivo es encontrar un flujo factible que maximice el flujo desde un nodo de origen a un nodo de destino.

Los problemas de ruta más corta se pueden utilizar para resolver ciertos problemas de flujo de red, en particular cuando se trata de redes de una sola fuente y un solo receptor. En estos casos, podemos transformar el problema de flujo de red en una serie de problemas de ruta más corta.

Pasos de transformación

^[7]

1. Crear un gráfico de residuos:
   • Para cada borde (u, v) en el gráfico original, crea dos bordes en el gráfico residual:
     • (u, v) con capacidad c(u, v)
     • (v, u) con capacidad 0
   • El gráfico residual representa la capacidad restante disponible en la red.
2. Encuentra el camino más corto:
   • Utilice un algoritmo de ruta más corta (por ejemplo, el algoritmo de Dijkstra, el algoritmo Bellman-Ford) para encontrar la ruta más corta desde el nodo de origen hasta el nodo sumidero en el gráfico residual.
3. Aumentar el flujo:
   • Encuentra la capacidad mínima a lo largo del camino más corto.
   • Aumente el flujo en los bordes del camino más corto en esta capacidad mínima.
   • Disminuya la capacidad de los bordes en la dirección hacia adelante y aumente la capacidad de los bordes en la dirección hacia atrás.
4. Actualizar el gráfico de residuos:
   • Actualice el gráfico residual en función del flujo aumentado.
5. Repetir:
   • Repita los pasos 2 a 4 hasta que no se puedan encontrar más rutas desde la fuente hasta el receptor.

Caminos más cortos de todos los pares

El problema de la ruta más corta de todos los pares encuentra las rutas más cortas entre cada par de vértices v , v' en el grafo. El problema de las rutas más cortas de todos los pares para grafos dirigidos no ponderados fue introducido por Shimbel (1953), quien observó que se podía resolver mediante un número lineal de multiplicaciones de matrices que toma un tiempo total de O ( V ⁴ ) .

Grafo no dirigido

Grafo dirigido

Aplicaciones

Los algoritmos de ruta más corta se aplican para encontrar automáticamente direcciones entre ubicaciones físicas, como las indicaciones para llegar en coche en sitios web de mapas web como MapQuest o Google Maps . Para esta aplicación, hay algoritmos rápidos especializados disponibles. ^[10]

Si se representa una máquina abstracta no determinista como un gráfico en el que los vértices describen estados y las aristas describen posibles transiciones, se pueden utilizar algoritmos de ruta más corta para encontrar una secuencia óptima de opciones para alcanzar un determinado estado objetivo, o para establecer límites inferiores al tiempo necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un rompecabezas como el cubo de Rubik y cada arista dirigida corresponde a un único movimiento o giro, se pueden utilizar 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 está relacionado con un problema de ruta más ancha . Por ejemplo, el algoritmo puede buscar la ruta más corta (retardo mínimo) y más ancha, o la ruta más corta (retardo mínimo) y más ancha.

Una aplicación más desenfadada son los juegos de " seis grados de separación " que tratan de encontrar el camino más corto en grafos como estrellas de cine que aparecen en una misma película.

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

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. Usando bordes dirigidos también es posible modelar calles de un solo sentido. Dichos 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 autopista. ^[12] Hay una gran cantidad de algoritmos que explotan esta propiedad y, por lo tanto, pueden calcular la ruta más corta 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, se preprocesa el gráfico sin conocer el nodo de origen o destino. La segunda fase es la fase de consulta. En esta fase, se conocen los nodos de origen y destino. La idea es que la red de carreteras sea estática, por lo que la fase de preprocesamiento se puede realizar una sola vez y utilizar para una gran cantidad de consultas sobre 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. ^[13] Otras técnicas que se han utilizado son:

• ALT ( Búsqueda A* , puntos de referencia y desigualdad triangular )
• Banderas de arco
• Jerarquías de contracción
• Enrutamiento de nodos de tránsito
• Poda basada en el alcance
• Etiquetado
• Etiquetas de hub

Problemas relacionados

Para problemas de ruta más corta en geometría computacional , consulte Ruta más corta euclidiana .

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

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

Caminos con restricciones

A diferencia del problema de la ruta más corta, que se puede resolver en tiempo polinomial en grafos sin ciclos negativos, los problemas de la ruta más corta que incluyen restricciones adicionales en la ruta de solución deseada se denominan " primero la ruta más corta restringida" y son más difíciles de resolver. Un ejemplo es el problema de la ruta más corta restringida ^[15] , que intenta minimizar el costo total de la ruta mientras que al mismo tiempo mantiene otra métrica por debajo de un umbral dado. 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 el problema P = NP ). Otro ejemplo NP-completo requiere que se incluya un conjunto específico de vértices en la ruta ^[16], lo que hace que el problema sea similar al problema del viajante de comercio (TSP). El TSP es el problema de encontrar la ruta más corta que pase por cada vértice exactamente una vez y regrese al inicio. El problema de encontrar la ruta más larga en un grafo también es NP-completo.

Observabilidad parcial

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

Caminos estratégicos más cortos

A veces, los bordes de un grafo tienen personalidades: cada borde tiene su propio interés egoísta. Un ejemplo es una red de comunicación, en la que cada borde es un ordenador que posiblemente pertenece a una persona diferente. Diferentes ordenadores tienen diferentes velocidades de transmisión, por lo que cada borde de la red tiene un peso numérico igual al número de milisegundos que tarda en 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 ordenador (el peso de cada borde), podemos utilizar un algoritmo estándar de caminos más cortos. Si no conocemos los tiempos de transmisión, tenemos que pedir a cada ordenador que nos diga su tiempo de transmisión. Pero los ordenadores pueden ser egoístas: un ordenador puede decirnos que su tiempo de transmisión es muy largo, para que no lo molestemos con nuestros mensajes. Una posible solución a este problema es utilizar una variante del mecanismo VCG , que da a los ordenadores un incentivo para revelar sus pesos verdaderos.

Detección de ciclo negativo

En algunos casos, el objetivo principal no es encontrar el camino más corto, sino solo detectar si el gráfico contiene un ciclo negativo. Se pueden utilizar algunos algoritmos de caminos más cortos para este propósito:

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

Marco algebraico general sobre semianillos: el problema de la trayectoria algebraica

Muchos problemas pueden formularse como una forma de la ruta más corta para algunas nociones de adición adecuadamente sustituidas a lo largo de una ruta y tomando el mínimo. El enfoque general para estos es considerar las dos operaciones como las de un semianillo . La multiplicación del semianillo se realiza a lo largo de la ruta y la adición se realiza entre rutas. Este marco general se conoce como el problema de la ruta algebraica . ^{[20] [21] [22]}

La mayoría de los algoritmos clásicos de ruta más corta (y otros nuevos) pueden formularse como solución de sistemas lineales sobre dichas estructuras algebraicas. ^[23]

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

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

En la vida real, una red de transporte suele ser estocástica y dependiente del tiempo. La duración del viaje en un segmento de carretera depende de muchos factores, como la cantidad de tráfico (matriz origen-destino), las obras en la carretera, el clima, los accidentes y las averías de los vehículos. Un modelo más realista de este tipo de red vial es una red estocástica dependiente del tiempo (STD). ^{[25] [26]}

No existe una definición aceptada de la ruta óptima en condiciones de incertidumbre (es decir, en redes viales estocásticas). Es un tema controvertido, a pesar de los considerables avances que se han logrado durante la última década. Una definición común es la de una ruta con el mínimo tiempo de viaje esperado. La principal ventaja de este enfoque es que puede utilizar algoritmos eficientes de ruta más corta para redes deterministas. Sin embargo, la ruta óptima resultante 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 de la duración del viaje en lugar de su valor esperado. Por lo tanto, encuentran la distribución de probabilidad de la duración total del viaje utilizando diferentes métodos de optimización, como la programación dinámica y el algoritmo de Dijkstra . ^[27] Estos métodos utilizan la optimización estocástica , específicamente la programación dinámica estocástica para encontrar el camino más corto en redes con longitud de arco probabilística. ^[28] Los términos confiabilidad del tiempo de viaje y variabilidad del tiempo de viaje se utilizan como opuestos en la literatura de investigación del transporte: cuanto mayor es la variabilidad, menor es la confiabilidad de las predicciones.

Para tener en cuenta la variabilidad, los investigadores han sugerido dos definiciones alternativas de una ruta óptima en condiciones de incertidumbre. La ruta más confiable es aquella que maximiza la probabilidad de llegar a tiempo dado un presupuesto de tiempo de viaje. Una ruta α-confiable es aquella que minimiza el presupuesto de tiempo de viaje necesario para llegar a tiempo con una probabilidad dada.

Véase también

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

Referencias

Notas

1. El problema del camino más corto. doi :10.1007/978-3-031-02574-7.
2. Deo, Narsingh (17 de agosto de 2016). Teoría de grafos con aplicaciones a la ingeniería y la informática. Courier Dover Publications. ISBN 978-0-486-80793-5.
3. Cormen y otros, 2001, pág. 655
4. Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Mhalla, Mehdi (enero de 2006). "Complejidad de consulta cuántica de algunos problemas de grafos". Revista SIAM de Computación . 35 (6): 1310–1328. arXiv : quant-ph/0401091 . doi :10.1137/050644719. ISSN  0097-5397. S2CID  14253494.
5. Dial, Robert B. (1969). "Algoritmo 360: Bosque de caminos más cortos con ordenamiento topológico [H]". Comunicaciones de la ACM . 12 (11): 632–633. doi : 10.1145/363269.363610 . S2CID  6754003.
6. Cormen, Thomas H. (31 de julio de 2009). Introducción a los algoritmos (3.ª ed.). MIT Press. ISBN 9780262533058.{{cite book}}: CS1 maint: date and year (link)
7. Kleinberg, Jon; Tardos, Éva (2005). Diseño de algoritmos (1ª ed.). Addison-Wesley. ISBN 978-0321295354.
8. Dürr, C.; Høyer, P. (18 de julio de 1996). "Un algoritmo cuántico para hallar el mínimo". arXiv : quant-ph/9607014 .
9. Nayebi, Aran; Williams, VV (22 de octubre de 2014). "Algoritmos cuánticos para problemas de caminos más cortos en instancias estructuradas". arXiv : 1410.6220 [quant-ph].
10. Sanders, Peter (23 de marzo de 2009). «Planificación rápida de rutas». Google Tech Talk . Archivado desde el original el 11 de diciembre de 2021.
11. Chen, Danny Z. (diciembre de 1996). "Desarrollo de algoritmos y software para problemas de planificación de trayectorias geométricas". ACM Computing Surveys . 28 (4es). Artículo 18. doi :10.1145/242224.242246. S2CID  11761485.
12. Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V .; Werneck, Renato F. "Dimensión de la autopista, caminos más cortos y algoritmos demostrablemente eficientes". Simposio ACM-SIAM sobre algoritmos discretos, páginas 782–793, 2010.
13. Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V .; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "Un algoritmo de etiquetado basado en concentradores para las rutas más cortas en redes viales". Simposio sobre algoritmos experimentales, páginas 230-241, 2011.
14. Kroger, Martin (2005). "Camino desconectado múltiple más corto para el análisis de entrelazamientos en sistemas poliméricos bidimensionales y tridimensionales". Computer Physics Communications . 168 (3): 209–232. Bibcode :2005CoPhC.168..209K. doi :10.1016/j.cpc.2005.01.020.
15. Lozano, Leonardo; Medaglia, Andrés L (2013). "Sobre un método exacto para el problema del camino más corto restringido". Computers & Operations Research . 40 (1): 378–384. doi :10.1016/j.cor.2012.07.008.
16. Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "Resolución óptima de problemas de planificación de rutas restringidas con redes convolucionales de grafos y búsqueda de árboles optimizada". Conferencia internacional IEEE/RSJ de 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.S2CID210706773  .​
17. 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 . 
18. 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.
19. Cherkassky, Boris V.; Goldberg, Andrew V. (1 de junio de 1999). "Algoritmos de detección de ciclos negativos". Programación matemática . 85 (2): 277–311. doi :10.1007/s101070050058. ISSN  1436-4646. S2CID  79739.
20. 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.
21. Derniame, Jean Claude; Par, Claude (1971). Problèmes de cheminement dans les graphes [ Problemas de trayectoria en gráficos ]. Dunod (París).
22. Baras, John; Theodorakopoulos, George (4 de abril de 2010). Problemas de trayectorias en redes. Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3.
23. Gondran, Michel; Minoux, Michel (2008). "capítulo 4". Grafos, dioides y semianillos: nuevos modelos y algoritmos . Springer Science & Business Media. ISBN 978-0-387-75450-5.
24. Pouly, Marc; Kohlas, Jürg (2011). "Capítulo 6. Álgebras de valoración para problemas de trayectorias". Inferencia genérica: una teoría unificadora para el razonamiento automatizado . John Wiley & Sons. ISBN 978-1-118-01086-0.
25. Loui, RP, 1983. Caminos óptimos en gráficos con pesos estocásticos o multidimensionales. Comunicaciones de la ACM, 26(9), pp.670-676.
26. Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Búsqueda de rutas multiobjetivo en redes viales estocásticas dependientes del tiempo utilizando un algoritmo genético de ordenación no dominada". Sistemas expertos con aplicaciones . 42 (12): 5056–5064. doi :10.1016/j.eswa.2015.02.046.
27. Olya, Mohammad Hessam (2014). "Encontrar el camino más corto en una distribución de probabilidad exponencial-gamma combinada". Revista Internacional de Investigación Operativa . 21 (1): 25–37. doi :10.1504/IJOR.2014.064020.
28. Olya, Mohammad Hessam (2014). "Aplicación del algoritmo de Dijkstra para el problema general de la ruta más corta con una 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; Orlin, James; Tarjan, Robert E. (abril de 1990). "Algoritmos más rápidos para el problema de la ruta más corta" (PDF) . Revista de la ACM . 37 (2). ACM: 213–223. doi :10.1145/77600.77615. hdl : 1721.1/47994 . S2CID  5499589. Archivado (PDF) desde el original el 2022-10-09.
• Bellman, Richard (1958). "Sobre un problema de enrutamiento". Quarterly of Applied Mathematics . 16 : 87–90. doi : 10.1090/qam/102435 . MR  0102435.
• Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian (2022). "Caminos más cortos de una sola fuente con peso negativo en tiempo casi lineal". 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. págs. 600–611. arXiv : 2203.03456 . doi :10.1109/focs54457.2022.00063. ISBN 978-1-6654-5519-0.S2CID247958461  .​
• 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. A. 73 (2): 129–174. doi :10.1016/0025-5610(95)00021-6. MR  1392160.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "Caminos más cortos de una sola fuente y caminos más cortos 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). "La ruta más corta a través de una red". Management Science . 6 (2): 187–190. doi :10.1287/mnsc.6.2.187.
• Dijkstra, EW (1959). "Una nota sobre dos problemas relacionados con los gráficos". Matemática numérica . 1 : 269–271. doi :10.1007/BF01386390. S2CID  123284777.
• Ford, LR (1956). Teoría del flujo en red (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 Computacional . 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 . MR  0828519.
• Hagerup, Torben (2000). "Caminos más cortos mejorados en la memoria RAM de palabras". En Montanari, Ugo; Rolim, José DP; Welzl, Emo (eds.). Actas del 27.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación . pp. 61–72. ISBN 978-3-540-67715-4.
• Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997). "Algoritmos de ruta más corta más rápidos para gráficos planares". 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 de cola toman tiempo O (log log D ) ". Teoría de sistemas matemáticos . 15 (1): 295–309. doi :10.1007/BF01786986. MR  0683047. S2CID  35703411.
• Karlsson, Rolf G.; Poblete, Patricio V. (1983). "Un algoritmo O(m log log D) para caminos más cortos". Matemáticas Aplicadas Discretas . 6 (1): 91–93. doi : 10.1016/0166-218X(83)90104-X . MR  0700028.
• Leyzorek, M.; Gray, RS; Johnson, AA; Ladew, WC; Meaker, SR Jr.; Petry, RM; Seitz, RN (1957). Investigación de técnicas modelo — Primer informe anual — 6 de junio de 1956 — 1 de julio de 1957 — Un estudio de técnicas modelo para sistemas de comunicación . Cleveland, Ohio: Case Institute of Technology.
• 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-5 de abril de 1957) . Cambridge: Harvard University Press. págs. 285-292.
• Pettie, Seth; Ramachandran, Vijaya (2002). "Cálculo de rutas más cortas con comparaciones y adiciones". Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos . pp. 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 grafos con ponderación real". Ciencias de la Computación Teórica . 312 (1): 47–74. doi : 10.1016/s0304-3975(03)00402-x .
• Pollack, Maurice; Wiebenson, Walter (marzo-abril de 1960). "Solución del problema de la ruta más corta: una revisión". Oper. 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, Alexander (2004). Optimización combinatoria: poliedros y eficiencia . Algoritmos y combinatoria. Vol. 24. Springer. vol. A, secc. 7.5b, p. 103. ISBN 978-3-540-20456-5.
• Shimbel, Alfonso (1953). "Parámetros estructurales de 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). "Caminos más cortos no dirigidos 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 de enteros con clave decreciente en tiempo constante y el problema de las rutas más cortas de una sola fuente". Journal of Computer and System Sciences . 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". Operational Research Quarterly . 11 (1/2): 37–40. doi :10.1057/jors.1960.32.
• Williams, Ryan (2014). "Caminos más cortos de todos los pares más rápidos a través de la complejidad del circuito". Actas del 46.º Simposio Anual de la 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. MR  3238994.

Lectura adicional

• Altıntaş, Gökhan (2020). Soluciones exactas de problemas de camino más corto basados ​​en analogías mecánicas: en conexión con laberintos. Amazon Digital Services LLC. ISBN 9798655831896.
• Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "Problema de ruta más corta de fuente única con límite de salida totalmente dinámico". Proc. Séptimo aniversario. Simposio ACM-SIAM. Algoritmos discretos . Atlanta, GA. 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) (informe). Proyecto Rand. Fuerza Aérea de los Estados Unidos. RM-5433-PR. Archivado (PDF) del original el 17 de noviembre de 2015.DTIC AD-661265.