algorithm - para - ruta mas corta en python
¿Encontrar una ruta más corta que pase por alguna secuencia arbitraria de nodos? (4)
En esta pregunta anterior, el OP preguntó cómo encontrar una ruta más corta en un gráfico que va de u a v y también pasa a través de algún nodo w. La respuesta aceptada, que es bastante buena, fue ejecutar el algoritmo de Dijkstra dos veces: una para obtener de u a w y una para obtener de w a v. Esto tiene una complejidad de tiempo igual a dos llamadas al algoritmo de Dijkstra, que es O (m + n log n).
Ahora considere una pregunta relacionada: se le da una secuencia de nodos u 1 , u 2 , ..., u k y desea encontrar la ruta más corta desde u 1 hasta u k , de manera que la ruta pase a través de u 1 , u 2 , ..., u k en orden. Claramente, esto podría hacerse ejecutando instancias k-1 del algoritmo de Dijkstra, una para cada par de vértices adyacentes, y luego concatenando las rutas más cortas juntas. Esto lleva tiempo O (km + kn log n). Alternativamente, podría usar un algoritmo de rutas más cortas de todos los pares, como el algoritmo de Johnson, para calcular todas las rutas más cortas, luego concatenar las rutas más cortas apropiadas en tiempo O (mn + n 2 log n), lo que es bueno para k mucho más grande que n.
Mi pregunta es si existe un algoritmo para resolver este problema que sea más rápido que los enfoques anteriores cuando k es pequeño. ¿Existe tal algoritmo? ¿O es iterado de Dijkstra lo mejor que se puede?
En lugar de ejecutar instancias aisladas del algoritmo de Dijkstra para encontrar las rutas u(k) -> u(k+1) una ruta a la vez, ¿se puede iniciar una sola instancia de una búsqueda similar a Dijkstra en cada nodo en la secuencia simultáneamente? , con los caminos formados cuando las regiones de búsqueda se encuentran "en el medio".
Esto potencialmente reduciría el número total de bordes visitados y reduciría la recrudecimiento de bordes en comparación con hacer una serie de llamadas aisladas al algoritmo de Dijkstra.
Un ejemplo fácil sería encontrar la ruta entre dos nodos. Sería mejor expandir las regiones de búsqueda de ambos nodos en lugar de expandir solo uno. En el caso de un gráfico uniforme, la segunda opción daría una región de búsqueda con un radio igual a la distancia entre los nodos, la primera opción daría dos regiones de la mitad del radio, menos el área de búsqueda general.
Solo un pensamiento.
EDIT: Supongo que estoy hablando de una variante multidireccional de una búsqueda bidireccional , con tantas direcciones como nodos haya en la secuencia {u(1), u(2), ..., u(m)} .
Mirando su problema desde una perspectiva de dividir y vencer, dado el gráfico G con n nodos, k de los cuales [1 <= k <= n] queremos atravesar en orden desde 1-k (i1, i2, ... , ik),
Digamos que f (j) es el camino más corto de i1 a ij. El problema se subdivide bien (ya ve a dónde va esto) en casos más pequeños de encontrar caminos más cortos, y finalmente se convierte en la suma de f (j) cuando j va de 1 a k. Por lo tanto, su problema está limitado por las iteraciones k-1 del algoritmo de Djikstra. La única forma de mejorarlo sería encontrar un algoritmo más rápido que el de Djikstra para descubrir el camino más corto entre 2 puntos.
Al menos esa es mi opinión. / estudiante graduado
No veo cómo podemos hacerlo mucho mejor, esto es todo lo que puedo pensar. Suponiendo que la gráfica no esté dirigida, la ruta más corta desde cualquier nodo u al nodo v sería la misma que la de v a u (por supuesto, al revés).
Ahora, para su caso de una ruta más corta en el orden u1 u2 u3 .. un, podríamos ejecutar el algoritmo de Djikstra en u2 (y encontrar las rutas más cortas u1-u2, u2-u3 en una ejecución), luego en u4 (para u3 -u4 y u4-u5), luego u6 .. y así sucesivamente. Esto reduce la cantidad de veces que aplica Djikstra''s en aproximadamente la mitad. Tenga en cuenta que la complejidad es que esto es idéntico a la solución original.
Obtiene la ruta más corta de un vértice a todo el otro en el gráfico mediante una llamada al algoritmo de Dijkstra. Por lo tanto, solo necesita hacer una búsqueda para cada vértice de inicio único para que los vértices repetidos no dificulten más el problema.