Sugerencias para KSPA en gráficos no dirigidos

Question

Hay una implementación personalizada de KSPA que necesita ser reescrita. La implementación actual utiliza un algoritmo de Dijkstra modificado cuyo pseudocódigo se explica más o menos a continuación. Es comúnmente conocido como KSPA usando una estrategia de eliminación de bordes, creo que sí. (Soy un novato en la teoría de grafos).

Step:-1.  Calculate the shortest path between any given pair of nodes using the Dijkstra algorithm. k = 0 here.
Step:-2.   Set k = 1
Step:-3.   Extract all the edges from all the ‘k-1’ shortest path trees. Add the same to a linked list Edge_List.
Step:-4.  Create a combination of ‘k’ edges from Edge_List to be deleted at once such that each edge belongs to a different SPT (Shortest Path Tree). This can be done by inspecting the ‘k’ value for each edge of the combination considered. The ‘k’ value has to be different for each of the edge of the chosen combination.
Step:-5.   Delete the combination of edges chosen in the above step temporarily from the graph in memory.
Step:-6.   Re-run Dijkstra for the same pair of nodes as in Step:-1.
Step:-7.   Add the resulting path into a temporary list of paths. Paths_List.
Step:-8.   Restore the deleted edges back into the graph.
Step:-9.   Go to Step:-4 to get another combination of edges for deletion until all unique combinations are exhausted. This is nothing but choosing ‘r’ edges at a time among ‘n’ edges => nCr.
Step:-10. The ‘k+1’ th shortest path is = Minimum(Paths_List).
Step:-11. k = k + 1 Go to Step:-3, until k < N.
Step:-12. STOP

Según entiendo el algoritmo, para obtener kth ruta más corta, se deben encontrar SPT 'k-1' entre cada par de origen-destino y los bordes 'k-1' cada uno de un SPT se deben eliminar simultáneamente para cada combinación . Claramente, este algoritmo tiene complejidad combinatoria y obstruye el servidor en grandes gráficos. La gente me sugirió el algoritmo de Eppstein ( http: //www.ics. uci.edu/~eppstein/pubs/Epp-SJC-98.pdf ). Pero este libro blanco cita un "dígrafo" y no vi una mención de que funciona solo para los dígrafos. Solo quería preguntar a la gente si alguien ha usado este algoritmo en un gráfico no dirigido.

Si no, ¿existen buenos algoritmos (en términos de complejidad de tiempo) para implementar KSPA en un gráfico no dirigido?

Gracias de antemano,

Answer 1

Complejidad de tiempo: O (K * (E * log (K) + V * log (V)))

Complejidad de memoria de O (K * V) (+ O (E) para almacenar la entrada).

Realizamos un Djikstra modificado de la siguiente manera:

• Para cada nodo, en lugar de mantener el mejor costo de ruta actualmente conocido desde el nodo de inicio. Mantenemos las mejores rutas K desde el nodo de inicio
• Al actualizar los vecinos de los nodos, no verificamos si mejora la mejor ruta conocida actualmente (como lo hace Djikstra), verificamos si mejora la peor de las mejores rutas conocidas actualmente de K '.
• Después de que ya procesamos la primera de las mejores rutas de K de los nodos, no necesitamos encontrar las mejores rutas de K, sino que solo nos queda K-1, y después de otra K-2. Eso es lo que llamé K '.
• Para cada nodo mantendremos dos colas de prioridad para las mejores longitudes de ruta conocidas actualmente de K '.
  • En una cola de prioridad, la ruta más corta está en la parte superior. Utilizamos esta cola de prioridad para determinar cuál de los K 'es mejor y se usará en las colas de prioridad de Djikstra como representante del nodo.
  • En la otra cola de prioridad, la ruta más larga está en la parte superior. Usamos este para comparar rutas candidatas con la peor de las rutas K '.