El problema de enrutamiento por k rutas más cortas es una generalización del problema de enrutamiento por rutas más cortas en una red dada. No solo se pregunta por una ruta más corta, sino también por las siguientes k−1 rutas más cortas (que pueden ser más largas que la ruta más corta). Una variación del problema son las k rutas más cortas sin bucles.
Es posible encontrar k caminos más cortos ampliando el algoritmo de Dijkstra o el algoritmo Bellman-Ford . [ cita requerida ]
Desde 1957, se han publicado muchos artículos sobre el problema de enrutamiento de k rutas más cortas. La mayoría de los trabajos fundamentales se realizaron entre los años 1960 y 2001. Desde entonces, la mayor parte de la investigación se ha centrado en las aplicaciones del problema y sus variantes. En 2010, Michael Günther et al. publicaron un libro sobre el cálculo simbólico de las k rutas más cortas y las medidas relacionadas con la herramienta de álgebra de procesos estocásticos CASPA . [1]
El algoritmo de Dijkstra se puede generalizar para encontrar los k caminos más cortos. [ cita requerida ]
Existen dos variantes principales del problema de enrutamiento de la ruta más corta k . En una variante, se permite que las rutas visiten el mismo nodo más de una vez, creando así bucles. En otra variante, se requiere que las rutas sean simples y sin bucles . La versión con bucles se puede resolver utilizando el algoritmo de Eppstein [2] y la variante sin bucles se puede resolver mediante el algoritmo de Yen . [3] [4]
En esta variante, el problema se simplifica al no requerir que los caminos no tengan bucles. [4] Una solución fue dada por BL Fox en 1975 en la que los k caminos más cortos se determinan en una complejidad temporal asintótica de O ( m + kn log n ) (usando la notación O grande ) . [5] En 1998, David Eppstein informó un enfoque que mantiene una complejidad asintótica de O ( m + n log n + k ) al calcular una representación implícita de los caminos, cada uno de los cuales puede generarse en O ( n ) tiempo extra. [2] [4] En 2015, Akiba et al. idearon un método de indexación como una alternativa significativamente más rápida para el algoritmo de Eppstein, en el que se construye una estructura de datos llamada índice a partir de un gráfico y luego se pueden obtener rápidamente las distancias top- k entre pares arbitrarios de vértices. [6]
En la variante sin bucles, se prohíbe que las rutas contengan bucles, lo que agrega un nivel adicional de complejidad. [4] Se puede resolver utilizando el algoritmo de Yen [3] [4] para encontrar las longitudes de todas las rutas más cortas desde un nodo fijo a todos los demás nodos en una red de n nodos con distancia no negativa, una técnica que requiere solo 2 n 2 adiciones y n 2 comparaciones, menos de lo que necesitan otros algoritmos de ruta más corta disponibles . La complejidad del tiempo de ejecución es pseudopolinomial , siendo O ( kn ( m + n log n )) (donde m y n representan el número de aristas y vértices, respectivamente). [3] [4] En 2007, John Hershberger y Subhash Suri propusieron un algoritmo de caminos de reemplazo, una implementación más eficiente del algoritmo de Lawler [7] y Yen con una mejora de O ( n ) en el tiempo para una gran cantidad de gráficos, pero no todos ellos (por lo tanto, sin cambiar el límite asintótico del algoritmo de Yen). [8]
El siguiente ejemplo utiliza el modelo de Yen para encontrar k rutas más cortas entre nodos finales que se comunican. Es decir, encuentra una ruta más corta, una segunda ruta más corta, etc. hasta la k -ésima ruta más corta. Puede encontrar más detalles aquí. El código proporcionado en este ejemplo intenta resolver el problema de enrutamiento de k rutas más cortas para una red de 15 nodos que contiene una combinación de enlaces unidireccionales y bidireccionales:
Otro ejemplo es el uso del algoritmo de rutas más cortas k para rastrear múltiples objetos. La técnica implementa un rastreador de múltiples objetos basado en el algoritmo de enrutamiento de rutas más cortas k . Se utiliza un conjunto de mapas de ocupación probabilísticos como entrada. Un detector de objetos proporciona la entrada.
Los detalles completos se pueden encontrar en “Laboratorio de Visión por Computador – CVLAB”.
Otro uso de los algoritmos de k rutas más cortas es diseñar una red de tránsito que mejore la experiencia de los pasajeros en los sistemas de transporte público. Un ejemplo de una red de tránsito de este tipo se puede construir teniendo en cuenta el tiempo de viaje. Además del tiempo de viaje, se pueden tomar otras condiciones dependiendo de las limitaciones económicas y geográficas. A pesar de las variaciones en los parámetros, los algoritmos de k rutas más cortas encuentran las soluciones más óptimas que satisfacen casi todas las necesidades de los usuarios. Estas aplicaciones de los algoritmos de k rutas más cortas se están volviendo comunes; recientemente, Xu, He, Song y Chaudry (2012) estudiaron los problemas de k rutas más cortas en los sistemas de redes de tránsito. [9]
El enrutamiento por ruta más corta k es una buena alternativa para:
Cherkassky et al. [10] proporcionan más algoritmos y evaluaciones asociadas.