¿Podemos encontrar k rutas más cortas entre todos los pares más rápido que resolver el problema por pares repetidamente?

9

Quiero producir ruta más corta ( k sería menos de 10) entre todos los pares en un gráfico. El gráfico es (en realidad un mapa del metro):kk

  • ponderado positivamente
  • no dirigido
  • escaso
  • con unos 100 nodos

Mi plan actual es aplicar ruta de ruta más cortak a cada par; Ahora estoy buscando una alternativa más eficiente (posiblemente con programación dinámica).

algorithms graphs optimization shortest-path Franklin Yu
fuente
3
Honestamente, para 100 vértices, parece poco probable que necesite algo más eficiente que resolver cada uno de los 45,000 problemas por pares.
David Richerby

Respuestas:

6

k

El todos los paresk

Esta parece ser un área de investigación bastante joven. Un artículo reciente de Agarwal y Ramachandran se puede encontrar en ArXiv [1]. La sección de trabajo anterior también le dará una idea de la historia del problema.

k

Aquí, de hecho, es la mejor opción para aplicar repetidamente el algoritmo Eppsteins [2]. La observación general de que una aplicación repetida de un algoritmo para la versión de fuente única del problema es el enfoque más rápido ya fue realizada en 1977 por EL Lawler [3]; Eppstein proporciona el algoritmo más rápido hasta la fecha para este subproblema.

Referencias

k

[2] Eppstein, D. Encontrar los k caminos más cortos. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, EL Comenta sobre calcular las k rutas más cortas en un gráfico. Comunicaciones de la ACM, 20 (8): 603–605, 1977.

Mentira
fuente
Gracias. Como estoy trabajando con el mapa del metro, necesito que sean una ruta simple (no tiene sentido que mi software guíe a las personas para ir y venir), así que supongo que simplemente seguiría el algoritmo de Yan .
Franklin Yu
Es interesante y bastante sorprendente que aparentemente 10,000 casos de un problema no se puedan resolver más rápido que solo resolver 10,000 casos individuales, uno tras otro.
gnasher729
la idea de caminos con bucles incluidos en los "caminos más cortos" Parece contradictorio y poco común porque al parecer hay un "camino" equivalente con el bucle eliminado, y uno se pregunta si estos pueden ser construidos de manera eficiente de los caminos sencillos, etc ...
vzn