k rutas más cortas

En esta variante, el problema se simplifica al no requerir que los caminos sean sin bucles. ^{[ 4 ]} BL Fox dio una solución 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 de la gran O ). ^{[ 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 un tiempo adicional de O ( n ). ^{[ 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 grafo y luego se pueden obtener rápidamente las k distancias superiores entre pares arbitrarios de vértices. ^{[ 6 ]} 

En la variante sin bucles, los caminos tienen prohibido contener bucles, lo que añade un nivel adicional de complejidad. ^{[ 4 ]} Se puede resolver utilizando el algoritmo de Yen ^{[ 3 ] [ 4 ]} para encontrar las longitudes de todos los caminos más cortos 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 ² sumas y n ² comparaciones, menos que otros algoritmos de camino más corto 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 rutas 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 un gran número de grafos, pero no para todos ellos (por lo tanto, no cambia la cota asintótica 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 la ruta más corta, la segunda 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 k rutas más cortas para el seguimiento de múltiples objetos. Esta técnica implementa un sistema de seguimiento de múltiples objetos basado en el algoritmo de enrutamiento de k rutas más cortas. Se utiliza un conjunto de mapas de ocupación probabilísticos como entrada. Un detector de objetos proporciona dicha entrada.

Encontrará todos los detalles en " Laboratorio de Visión por Computadora – CVLAB".

Another use of k shortest paths algorithms is to design a transit network that enhances passengers' experience in public transportation systems. Such an example of a transit network can be constructed by putting traveling time under consideration. In addition to traveling time, other conditions may be taken depending upon economical and geographical limitations. Despite variations in parameters, the k shortest path algorithms finds the most optimal solutions that satisfies almost all user needs. Such applications of k shortest path algorithms are becoming common, recently Xu, He, Song, and Chaudhry (2012) studied the k shortest path problems in transit network systems.^[9]