Hispanopedia Wiki
Articulo de referencia

problema del camino más corto

Camino más corto (A, C, E, D, F), en azul, entre los vértices A y F en el grafo dirigido ponderado. En teoría de grafos , el problema del camino más corto es el problema de enco...

Hispanopedia WikiContenido en espanolLectura gratuita
Camino más corto (A, C, E, D, F), en azul, entre los vértices A y F en el grafo 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 sea mínima. [ 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 grafos, donde los vértices corresponden a intersecciones y las aristas corresponden a segmentos de carretera, cada uno ponderado por la longitud o distancia de cada segmento. [ 2 ]

Definición

El problema del camino más corto se puede definir para grafos, ya sean no dirigidos , dirigidos o mixtos . La definición para grafos no dirigidos establece que cada arista se puede recorrer en cualquier dirección. Los grafos dirigidos requieren que los vértices consecutivos estén conectados por una arista dirigida apropiada. [ 3 ]

Dos vértices son adyacentes cuando ambos son incidentes a una arista común. Un camino en un grafo no dirigido es una secuencia de vértices.PAG=(v1,v2,…,vnorte)∈V×V×⋯×V{\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V}de tal manera quevi{\displaystyle v_{i}}está adyacente avi+1{\displaystyle v_{i+1}}para1≤i<norte{\displaystyle 1\leq i<n}. Tal caminoPAG{\displaystyle P}se denomina camino de longitudnorte−1{\displaystyle n-1}dev1{\displaystyle v_{1}}avnorte{\displaystyle v_{n}}. (Elvi{\displaystyle v_{i}}son variables; su numeración se relaciona con su posición en la secuencia y no tiene por qué estar relacionada con una nomenclatura canónica.) [ 4 ]

Dejarmi={mii,j}{\displaystyle E=\{e_{i,j}\}}dóndemii,j{\displaystyle e_{i,j}}es el incidente de borde para ambosvi{\displaystyle v_{i}}yvj{\displaystyle v_{j}}Dada una función de ponderación de valor realF:mi→R{\displaystyle f:E\rightarrow \mathbb {R} }y un grafo no dirigido (simple)GRAMO{\displaystyle G}, el camino más corto desdev{\displaystyle v}av′{\displaystyle v'}es el caminoPAG=(v1,v2,…,vnorte){\displaystyle P=(v_{1},v_{2},\ldots,v_{n})}(dóndev1=v{\displaystyle v_{1}=v}yvnorte=v′{\displaystyle v_{n}=v'}) que sobre todas las posiblesnorte{\displaystyle n}minimiza la suma∑i=1norte−1F(mii,i+1).{\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}Cuando cada arista en el grafo tiene un peso unitario oF:mi→{1}{\displaystyle f:E\rightarrow \{1\}}Esto equivale a encontrar el camino con el menor número de aristas.

El problema también se denomina a veces problema de la ruta más corta de un solo par , para distinguirlo de las siguientes variaciones: [ 5 ]

  • El problema del camino más corto desde un único origen , en el que tenemos que encontrar los caminos más cortos desde un vértice de origen v a todos los demás vértices del grafo.
  • El problema del camino más corto a un único destino , en el que debemos encontrar los caminos más cortos desde todos los vértices del grafo dirigido hasta un único vértice de destino v . Este problema se puede reducir al problema del camino más corto a un único origen invirtiendo los arcos del grafo dirigido.
  • El problema del camino más corto entre todos los pares de vértices , en el que tenemos que encontrar los caminos más cortos entre cada par de vértices v , v' en el grafo.

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. [ 6 ]

Algoritmos

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

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

Rutas más cortas desde un único origen

Grafos no dirigidos

Gráficos no ponderados

Grafos acíclicos dirigidos

Un algoritmo que utiliza ordenación topológica puede resolver el problema del camino más corto desde un único origen en tiempo Θ( E + V ) en grafos dirigidos acíclicos con ponderación arbitraria. [ 7 ]

Grafos dirigidos con pesos no negativos

La siguiente tabla se ha tomado de Schrijver (2004) , con algunas correcciones y añadidos. El fondo verde indica la cota asintótica óptima en la tabla; L es la longitud (o peso) máxima entre todas las aristas, suponiendo pesos enteros en las aristas.

Grafos dirigidos con pesos arbitrarios sin ciclos negativos

Grafos dirigidos con pesos arbitrarios y ciclos negativos

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

Grafos planares con pesos no negativos

Aplicaciones

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

Los problemas de ruta más corta pueden utilizarse para resolver ciertos problemas de flujo de red, especialmente cuando se trata de redes con un único origen y un único destino. En estos casos, podemos transformar el problema de flujo de red en una serie de problemas de ruta más corta.

Pasos de la transformación

[ 13 ]

  1. Crear un gráfico residual:
    • Para cada arista (u, v) en el grafo original, cree dos aristas en el grafo 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 o el algoritmo de Bellman-Ford) para encontrar la ruta más corta desde el nodo de origen hasta el nodo de destino en el grafo residual.
  3. Aumentar el flujo:
    • Encuentra la capacidad mínima a lo largo del camino más corto.
    • Incremente el flujo en los bordes del camino más corto en esta capacidad mínima.
    • Disminuir la capacidad de las aristas en la dirección de avance y aumentar la capacidad de las aristas en la dirección de retroceso.
  4. Actualizar el gráfico residual:
    • Actualizar 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 el origen hasta el destino.

Caminos más cortos entre todos los pares de pares

El problema de los caminos más cortos entre todos los pares encuentra los caminos más cortos entre cada par de vértices v , v' en el grafo. El problema de los caminos más cortos entre todos los pares para grafos 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 ( V4 ) .

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 conducir en sitios web de mapas como MapQuest o Google Maps . Para esta aplicación, se dispone de algoritmos especializados rápidos. [ 16 ]

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

En el ámbito de las redes o las telecomunicaciones , este problema de la ruta más corta a veces se denomina problema de la ruta con retardo mínimo y suele estar vinculado al problema de la ruta más ancha . Por ejemplo, el algoritmo puede buscar la ruta más corta (con retardo mínimo) y más ancha, o la ruta más ancha y más corta (con retardo mínimo). [ 17 ]

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

Otras aplicaciones, frecuentemente estudiadas en la investigación operativa , incluyen el diseño de plantas e instalaciones, la robótica , el transporte y el diseño VLSI . [ 18 ]

Redes de carreteras

Una red vial puede considerarse como un grafo con pesos positivos. Los nodos representan intersecciones viales y cada arista del grafo está asociada a un segmento vial entre dos intersecciones. El peso de una arista puede corresponder a la longitud del segmento vial asociado, el tiempo necesario para recorrerlo o el costo de recorrerlo. Mediante aristas dirigidas, también es posible modelar calles de sentido único. Estos grafos son especiales en el sentido de que algunas aristas son más importantes que otras para viajes de larga distancia (por ejemplo, autopistas). Esta propiedad se ha formalizado utilizando la noción de dimensión de autopista. [ 19 ] Existe una gran cantidad de algoritmos que aprovechan esta propiedad y, por lo tanto, pueden calcular la ruta más corta mucho más rápido que en grafos generales.

Todos estos algoritmos funcionan en dos fases. En la primera, el grafo se preprocesa sin conocer el nodo de origen ni el de destino. La segunda fase es la de consulta. En esta fase, se conocen el nodo de origen y el de destino. La idea es que la red vial sea estática, por lo que la fase de preprocesamiento se puede realizar una sola vez y utilizarse para un gran número de consultas sobre la misma red vial.

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

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

El camino múltiple desconectado más corto [ 21 ] es una representación de la red de caminos primitivos dentro del marco de la teoría de Reptación . El problema del camino más ancho 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.

Rutas con restricciones

A diferencia del problema del camino más corto, que puede resolverse en tiempo polinomial en grafos sin ciclos negativos, los problemas del camino más corto que incluyen restricciones adicionales en el camino de solución deseado se denominan " Primero el camino más corto con restricciones " y son más difíciles de resolver. Un ejemplo es el problema del camino más corto con restricciones, [ 22 ] que intenta minimizar el costo total del camino mientras, 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 sean eficientemente resolubles para grandes conjuntos de datos, véase el problema P = NP ). Otro ejemplo NP-completo requiere que se incluya un conjunto específico de vértices en el camino, [ 23 ] 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 pasa por cada vértice exactamente una vez y regresa al inicio. El problema de encontrar el camino más largo 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 donde el grafo no es completamente conocido por el viajero, cambia con el tiempo o donde las acciones (recorridos) son probabilísticas. [ 24 ] [ 25 ]

Rutas estratégicas más cortas

A veces, las aristas de un grafo tienen personalidad: cada una tiene sus propios intereses. Un ejemplo es una red de comunicación, donde cada arista representa un ordenador que posiblemente pertenece a una persona diferente. Los distintos ordenadores tienen velocidades de transmisión diferentes, por lo que cada arista 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 arista), podemos usar un algoritmo estándar de ruta más corta. Si no conocemos los tiempos de transmisión, debemos solicitar a cada ordenador que nos indique el suyo. Sin embargo, los ordenadores pueden ser egoístas: uno podría decirnos que su tiempo de transmisión es muy largo para que no le enviemos mensajes. Una posible solución a este problema es usar una variante del mecanismo VCG , que incentiva a los ordenadores a revelar sus pesos reales.

detección de ciclo negativo

En algunos casos, el objetivo principal no es encontrar el camino más corto, sino simplemente detectar si el grafo contiene un ciclo negativo. Algunos algoritmos de búsqueda de caminos más cortos pueden utilizarse para este fin:

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

Marco algebraico general sobre semianillos: el problema del camino algebraico

Muchos problemas pueden plantearse como una forma del problema del camino más corto para algunas nociones de suma adecuadamente sustituidas a lo largo de un camino y la toma del mínimo. El enfoque general para estos problemas consiste en considerar las dos operaciones como las de un semianillo . La multiplicación de semianillos se realiza a lo largo del camino, y la suma se realiza entre caminos. Este marco general se conoce como el problema del camino algebraico. [ 27 ] [ 28 ] [ 29 ]

La mayoría de los algoritmos clásicos de camino más corto (y los nuevos) pueden formularse como la resolución de sistemas lineales sobre dichas estructuras algebraicas. [ 30 ]

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

Ruta más corta 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 viales, las condiciones climáticas, los accidentes y las averías de los vehículos. Un modelo más realista de dicha red vial es una red estocástica dependiente del tiempo (STD). [ 32 ] [ 33 ]

No existe una definición aceptada de ruta óptima en condiciones de incertidumbre (es decir, en redes viales estocásticas). Se trata de un tema controvertido, a pesar de los considerables avances logrados en 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 permite utilizar algoritmos eficientes de ruta más corta para redes deterministas. Sin embargo, la ruta óptima resultante puede no ser fiable, ya que este enfoque no tiene en cuenta 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. Así, 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 . [ 34 ] Estos métodos utilizan optimización estocástica , específicamente programación dinámica estocástica para encontrar la ruta más corta en redes con longitud de arco probabilística. [ 35 ] Los términos fiabilidad 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 fiabilidad de las predicciones.

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

Ruta más corta restringida

El problema del camino más corto restringido (RSP) es una variante del problema del camino más corto en la que existen dos criterios de optimización. Se nos da un grafo dirigido en el que cada arista e tiene un coste entero no negativo c e y un retardo entero no negativo d e , dos vértices designados s y t, y un presupuesto de retardo entero no negativo B. El objetivo es encontrar un camino s-t de coste total mínimo, entre los caminos cuyo retardo total sea como máximo B. El RSP es NP-difícil: aparece en el libro de Garey y Johnson como el problema ND30, "Shortest weight-constrained path" (Camino más corto con restricción de peso). Tiene un FPTAS debido a Hassin [ 36 ] , posteriormente simplificado y mejorado por Lorenz y Raz [ 37 ] .

Se conocen varias generalizaciones de este problema:

  • En el problema de la ruta más corta con restricciones de recursos (RCSP) , [ 38 ] cada arista puede consumir varios recursos (en lugar de solo tiempo). Cada recurso r tiene un presupuesto independiente B r . Cada arista e consume d e,r de cada recurso r . El objetivo es encontrar una ruta s-t de costo total mínimo, entre las rutas que satisfacen la restricción de recursos para cada recurso.
  • En el problema CSP múltiple compartido , [ 39 ] puede haber varios pares fuente-destino ( s j , t j ), para j=1,2,... Aquí, el objetivo es encontrar una ruta para cada par fuente-destino, con un costo total mínimo , sujeto a que el retraso total sea como máximo el presupuesto de retraso.
  • El RSP fraccional es una relajación de programación lineal del RSP. Handler y Zang [ 40 ] lo introdujeron y dieron un algoritmo combinatorio para resolverlo (en el caso de un recurso). Mehlhorn y Ziegelmann [ 38 ] demostraron que, en el caso de un recurso, el algoritmo combinatorio se ejecuta en tiempo polinomial, O(log( nCD )), donde n es el número de nodos, los costos son enteros en 0..C y los retrasos son enteros en 0..D . Para muchos recursos , el tiempo de ejecución del algoritmo combinatorio sigue abierto, pero el LP se puede resolver en tiempo débilmente polinomial usando el método del elipsoide.

Véase también

Referencias

Notas

  1. ↑ Ortega-Arranz, Héctor; Llanos, Diego R.; González-Escribano, Arturo (2015). El problema del camino más corto . Conferencias de síntesis sobre informática teórica. Cham: Springer. doi : 10.1007/978-3-031-02574-7 . ISBN 978-3-031-01446-8.
  2. ↑ Guenin, Bertrand (2014). Gentle Introduction to Optimization . Jochen Koenemann, Levent Tunçel (1.ª ed.). West Nyack: Cambridge University Press. p. 27. ISBN   978-1-107-05344-1.
  3. ↑ 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.
  4. ↑ "Paseos, senderos, caminos, ciclos y circuitos" . Éxito académico estudiantil . Consultado el 13 de julio de 2026 .
  5. ↑ "Tutorial del algoritmo de ruta más corta con problemas" . GeeksforGeeks . 2 de noviembre de 2023. Consultado el 13 de julio de 2026 .
  6. ↑ Brubaker, Ben (06-08-2025). "Nuevo método es la forma más rápida de encontrar las mejores rutas" . Quanta Magazine . Recuperado el 13-07-2026 .
  7. ^ Cormen et al. 2001 , pág. 655 
  8. ↑ Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Mhalla, Mehdi (enero de 2006). "Complejidad de consulta cuántica de algunos problemas de grafos". SIAM Journal on Computing . 35 (6): 1310– 1328. arXiv : quant-ph/0401091 . doi : 10.1137/050644719 . ISSN 0097-5397 . S2CID 14253494 .  
  9. ↑ Brubaker, Ben (6 de agosto de 2025). "Nuevo método es la forma más rápida de encontrar las mejores rutas" . Quanta Magazine . Consultado el 11 de agosto de 2025 .
  10. 1 2 Dial, Robert B. (1969). "Algoritmo 360: Bosque de caminos más cortos con ordenamiento topológico [ H ] " . Communications of the ACM . 12 (11): 632– 633. doi : 10.1145/363269.363610 . S2CID 6754003 . 
  11. ↑ Khanna, Sanjeev; Song, Junkai (18 de febrero de 2026). "Un algoritmo de tiempo n 2+ o (1) para rutas más cortas de peso negativo de una sola fuente". arXiv : 2602.16638 [ cs.DS ].
  12. ↑ Cormen, Thomas H. (31 de julio de 2009). Introducción a los algoritmos (3.ª ed.). MIT Press. ISBN  9780262533058.
  13. ^ Kleinberg, Jon; Tardos, Éva (2005). Diseño de algoritmos (1ª ed.). Addison-Wesley. ISBN  978-0321295354.
  14. ↑ Dürr, C.; Høyer, P. (1996-07-18). "Un algoritmo cuántico para encontrar el mínimo". arXiv : quant-ph/9607014 .
  15. ↑ Nayebi, Aran; Williams, VV (22-10-2014). "Algoritmos cuánticos para problemas de caminos más cortos en instancias estructuradas". arXiv : 1410.6220 [ quant-ph ].
  16. ↑ Sanders, Peter (23 de marzo de 2009). "Planificación rápida de rutas" . Charla técnica de Google . Archivado del original el 11 de diciembre de 2021.
  17. ↑ Hoceini, S.; A. Mellouk; Y. Amirat (2005). "Enrutamiento Q de rutas más cortas (K-Shortest Paths Q-Routing): Un nuevo algoritmo de enrutamiento QoS en redes de telecomunicaciones" . Networking - ICN 2005, Lecture Notes in Computer Science, Vol. 3421. Springer , Berlín, Heidelberg. pp. 164–172 . doi : 10.1007/978-3-540-31957-3_21 . ISBN   978-3-540-25338-9.
  18. ↑ Chen, Danny Z. (diciembre de 1996). "Desarrollo de algoritmos y software para problemas de planificación de rutas geométricas". ACM Computing Surveys . 28 (4es). Artículo 18. doi : 10.1145/242224.242246 . S2CID 11761485 . 
  19. ↑ Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V .; Werneck, Renato F. "Dimensión de autopista, rutas más cortas y algoritmos demostrablemente eficientes" . Simposio ACM-SIAM sobre algoritmos discretos, páginas 782–793, 2010.
  20. ↑ Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "Un algoritmo de etiquetado basado en hubs para rutas más cortas en redes viales" . Simposio sobre algoritmos experimentales, páginas 230–241, 2011.
  21. ↑ Kroger, Martin (2005). "Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems". Computer Physics Communications . 168 (3): 209– 232. Bibcode : 2005CoPhC.168..209K . doi : 10.1016/j.cpc.2005.01.020 .
  22. ↑ Lozano, Leonardo; Medaglia, Andrés L (2013). "Sobre un método exacto para el problema del camino más corto con restricciones". Computers & Operations Research . 40 (1): 378– 384. doi : 10.1016/j.cor.2012.07.008 .
  23. ↑ Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "Resolución óptima de problemas de planificación de rutas con restricciones mediante redes neuronales convolucionales gráficas y búsqueda optimizada en árboles". 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) . pp. 3519–3525 . arXiv : 2108.01036 . doi : 10.1109/IROS40897.2019.8968113 . ISBN  978-1-7281-4004-9. S2CID 210706773 . 
  24. ↑ 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 . 
  25. ↑ Nikolova, Evdokia; Karger, David R. "Planificación de rutas bajo incertidumbre: el problema del viajero canadiense" (PDF) . Actas de la 23.ª Conferencia Nacional sobre Inteligencia Artificial (AAAI) . págs. 969–974 . Archivado (PDF) del original el 9 de octubre de 2022. 
  26. ↑ Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). "Algoritmos de detección de ciclos negativos" . Mathematical Programming . 85 (2): 277– 311. doi : 10.1007/s101070050058 . ISSN 1436-4646 . S2CID 79739 .  
  27. ^ 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 .  
  28. ^ Derniame, Jean Claude; Par, Claude (1971). Problèmes de cheminement dans les graphes [ Problemas de trayectoria en gráficos ] . Dunod (París).
  29. ↑ Baras, John; Theodorakopoulos, George (4 de abril de 2010). Problemas de caminos en redes . Morgan & Claypool Publishers. págs. 9–. ISBN  978-1-59829-924-3.
  30. ↑ Gondran, Michel; Minoux, Michel (2008). «Capítulo 4». Grafos, diodos y semianillos: nuevos modelos y algoritmos . Springer Science & Business Media. ISBN 978-0-387-75450-5.
  31. ↑ Pouly, Marc; Kohlas, Jürg (2011). «Capítulo 6. Álgebras de valuación para problemas de caminos». Inferencia genérica: una teoría unificadora para el razonamiento automatizado . John Wiley & Sons. ISBN 978-1-118-01086-0.
  32. ↑ Loui, RP, 1983. Rutas óptimas en grafos con pesos estocásticos o multidimensionales. Communications of the ACM, 26(9), pp.670-676.
  33. ↑ 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 clasificación no dominada". Expert Systems with Applications . 42 (12): 5056– 5064. doi : 10.1016/j.eswa.2015.02.046 .
  34. ↑ Olya, Mohammad Hessam (2014). "Encontrar el camino más corto en una longitud de arco de distribución de probabilidad exponencial-gamma combinada". International Journal of Operational Research . 21 (1) 64020: 25– 37. doi : 10.1504/IJOR.2014.064020 .
  35. ↑ Olya, Mohammad Hessam (2014). "Aplicación del algoritmo de Dijkstra para el problema general de la ruta más corta con longitud de arco de distribución de probabilidad normal". International Journal of Operational Research . 21 (2) 64541: 143– 154. doi : 10.1504/IJOR.2014.064541 .
  36. ↑ Hassin, Refael (febrero de 1992). "Esquemas de aproximación para el problema del camino más corto restringido" . Matemáticas de la investigación operativa . 17 (1): 36– 42. doi : 10.1287/moor.17.1.36 . ISSN 0364-765X . 
  37. ↑ Lorenz, Dean H.; Raz, Danny (junio de 2001). "Un esquema de aproximación simple y eficiente para el problema del camino más corto restringido" . Operations Research Letters . 28 (5): 213– 219. doi : 10.1016/s0167-6377(01)00069-4 . ISSN 0167-6377 . 
  38. 1 2 Mehlhorn, Kurt; Ziegelmann, Mark (2000). "Resource Constrained Shortest Paths" . En Paterson, Mike S. (ed.). Algorithms - ESA 2000. Lecture Notes in Computer Science. Vol. 1879. Berlín, Heidelberg: Springer. pp. 326–337 . doi : 10.1007/3-540-45253-2_30 . ISBN   978-3-540-45253-9.
  39. ↑ García-Heredia, David; Molina, Elisenda; Laguna, Manuel; Alonso-Ayuso, Antonio (noviembre de 2021). "Un método de solución para el problema de múltiples rutas más cortas con recursos compartidos" . Expert Systems with Applications . 182 115193. doi : 10.1016/j.eswa.2021.115193 . hdl : 10016/30793 . ISSN 0957-4174 . 
  40. ↑ Handler, Gabriel Y.; Zang, Israel (diciembre de 1980). "Un algoritmo dual para el problema del camino más corto con restricciones" . Networks . 10 (4): 293–309 . doi : 10.1002/net.3230100403 . ISSN 0028-3045 . 

Bibliografía

  • Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (abril de 1990). "Algoritmos más rápidos para el problema del camino más corto" ( PDF) . Journal of the ACM . 37 (2). ACM: 213–223 . doi : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID 5499589. Archivado (PDF) del original el 9 de octubre de 2022. 
  • Axiotis, Kyriakos; Mądry, Aleksander; Vladu, Adrián (2020). "Control de circulación para un flujo de costo mínimo más rápido en gráficos de capacidad unitaria". En iraní, Sandy (ed.). 61.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2020, Durham, Carolina del Norte, EE. UU., 16 al 19 de noviembre de 2020 . IEEE. págs. 93-104 . arXiv : 2003.04863 . doi : 10.1109/FOCS46700.2020.00018 . ISBN  978-1-7281-9621-3.
  • 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. pp. 600–611 . arXiv : 2203.03456 . doi : 10.1109/focs54457.2022.00063 . ISBN  978-1-6654-5519-0. S2CID 247958461 . 
  • van den Brand, Jan; Lee, Yin Tat; Nanongkai, Danupon; Peng, Richard; Saranurak, Thatchaphol; Sidford, Aaron; Song, Zhao; Wang, Di (2020). "Emparejamiento bipartito en tiempo casi lineal en grafos moderadamente densos". En Irani, Sandy (ed.). 61.º Simposio Anual IEEE sobre Fundamentos de la Informática, FOCS 2020, Durham, NC, EE. UU., 16-19 de noviembre de 2020. IEEE. págs. 919-930 . arXiv : 2009.01802 . doi : 10.1109/FOCS46700.2020.00090 . ISBN  978-1-7281-9621-3.
  • Chen, Li; Kyng, Rasmus; Liu, Yang P.; Peng, Richard; Gutenberg, Maximilian Probst; Sachdeva, Sushant (2022). "Flujo máximo y flujo de costo mínimo en tiempo casi lineal". 63.º Simposio Anual IEEE sobre Fundamentos de la Informática, FOCS 2022, Denver, CO, EE. UU., 31 de octubre - 3 de noviembre de 2022. IEEE. págs. 612-623 . arXiv : 2203.00671 . doi : 10.1109/FOCS54457.2022.00064 . ISBN  978-1-6654-5519-0.
  • Cohen, Michael B.; Mądry, Aleksander; Sankowski, Piotr; Vladu, Adrian (2017). "Caminos más cortos con peso negativo y flujo de costo mínimo de capacidad unitaria enO~(metro10/7registro⁡W){\displaystyle {\tilde {O}}(m^{10/7}\log W)}tiempo". En Klein, Philip N. (ed.). Actas del Vigésimo Octavo Simposio Anual ACM–SIAM sobre Algoritmos Discretos, SODA 2017, Barcelona, ​​España, Hotel Porta Fira, 16–19 de enero . Sociedad de Matemáticas Industriales y Aplicadas. págs. 752–771 . doi : 10.1137/1.9781611974782.48 . 
  • Duan, Ran; Mao, Jiayi; Shu, Xinkai; Yin, Longhui (2023). "Un algoritmo aleatorio para la ruta más corta desde un único origen en grafos no dirigidos con pesos reales". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. pp. 484–492 . arXiv : 2307.04139 . doi : 10.1109/focs57990.2023.00035 . ISBN  979-8-3503-1894-4. S2CID 259501045 . 
  • Duan, Ran; Mao, Jiayi; Mao, Xiao; Shu, Xinkai; Yin, Longhui (2025). «Rompiendo la barrera de clasificación para rutas más cortas dirigidas desde una única fuente». Actas del 57.º Simposio Anual de la ACM sobre Teoría de la Computación (STOC) . Association for Computing Machinery. págs. 36–44 . doi : 10.1145/3717823.3718179 . ISBN  979-8-4007-1510-5.
  • Cherkassky, Boris V.; Goldberg, Andrew V .; Radzik, Tomasz (1996). "Algoritmos de caminos más cortos: teoría y evaluación experimental" . Mathematical Programming . 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]. «Single-Source Shortest Paths and All-Pairs Shortest Paths». Introduction to Algorithms (2.ª  ed.). MIT Press y McGraw-Hill. pp. 580–642 . ISBN  0-262-03293-7.
  • Dantzig, GB (enero de 1960). "Sobre 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 en relación con los grafos". Numerische Mathematik . 1 : 269–271 . Bibcode : 1959NuMat...1..269D . doi : 10.1007/BF01386390 . S2CID 123284777 . 
  • Fineman, Jeremy T. (2024). "Caminos más cortos de origen único con pesos reales negativos enO~(metronorte8/9){\displaystyle {\tilde {O}}(mn^{8/9})}tiempo". En Mohar, Bojan; Shinkar, Igor; O'Donnell, Ryan (eds.). Actas del 56.º Simposio Anual de la ACM sobre Teoría de la Computación, STOC 2024, Vancouver, BC, Canadá, 24-28 de junio de 2024. Association for Computing Machinery. págs. 3-14 . arXiv : 2311.02520 . doi : 10.1145/3618260.3649614 . 
  • 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). Montículos de Fibonacci y su uso 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). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" . Journal of the Association for Computing Machinery . 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" . Journal of Computer and System Sciences . 31 (2): 148– 168. doi : 10.1016/0022-0000(85)90039-X . MR 0828519 . 
  • Hagerup, Torben (2000). «Improved Shortest Paths on the Word RAM» . 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 grafos planares" . Journal of Computer and System Sciences . 55 (1): 3– 23. doi : 10.1006/jcss.1997.1493 .
  • Johnson, Donald B. (1977). "Algoritmos eficientes para rutas más cortas en redes dispersas" . Journal of the ACM . 24 (1): 1– 12. doi : 10.1145/321992.321993 . S2CID 207678246 . 
  • Johnson, Donald B. (diciembre de 1981). "Una cola de prioridad en la que la inicialización y las operaciones de cola toman O (log log D ) tiempo". Mathematical Systems Theory . 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 de modelado — Primer informe anual — 6 de junio de 1956 — 1 de julio de 1957 — Un estudio de técnicas de modelado 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 mediante comparaciones y adiciones» . 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 todos los caminos más cortos entre pares en grafos ponderados reales" . Theoretical Computer Science . 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ágina  225.
  • Schrijver, Alexander (2004). Optimización combinatoria: poliedros y eficiencia . Algoritmos y combinatoria. Vol.  24. Springer. vol. A, sect. 7.5b, p.  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. Bibcode : 1953BMaB...15..501S . 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" . Journal of the ACM . 46 (3): 362– 394. doi : 10.1145/316542.316548 . S2CID 207654795 . 
  • Thorup, Mikkel (2004). "Colas de prioridad entera con clave decreciente en tiempo constante y el problema de los caminos más cortos desde una única 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 vial". Operational Research Quarterly . 11 (1/2): 37–40 . doi : 10.1057/jors.1960.32 .
  • Williams, Ryan (2014). "Caminos más cortos entre todos los pares mediante 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 .  

Lecturas adicionales

  • Altıntaş, Gökhan (2020). Soluciones exactas de problemas de caminos más cortos basadas en analogías mecánicas: en relación con los laberintos . Amazon Digital Services LLC. ISBN 9798655831896.
  • Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "Problema de ruta más corta de origen único con salida acotada totalmente dinámica". Actas del 7.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos . Atlanta, GA. págs. 212–221 . CiteSeerX 10.1.1.32.9856 .  
  • Dreyfus, SE (octubre de 1967). 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.
Lecturas relacionadas
6 articulos
Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Trayectoria (teoría de grafos)Trayectoria (teoría de grafos)En teoría de grafos , un camino en un grafo es una secuencia finita o infinita de aristas que une una secuencia de vértices que, según la mayoría d...Vertex (graph theory)Vertex (graph theory)In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are form...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Glosario de teoría de grafosGlosario de teoría de grafosEste es un glosario de teoría de grafos . La teoría de grafos es el estudio de los grafos , sistemas de nodos o vértices conectados en pares por lí...Gráfico mixtoGráfico mixtoEn teoría de grafos , un grafo mixto G = ( V , E , A ) es un grafo que consta de un conjunto de vértices V , un conjunto de aristas (no dirigidas) ...