Sugerencias para KSPA en el gráfico no dirigido

Question

Hay una implementación personalizada de KSPA que necesita ser reescrita. La implementación actual usa un algoritmo de Dijkstra modificado cuyo pseudocódigo se explica más o menos a continuación. Se lo conoce comúnmente 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 

como entiendo el algoritmo, para obtener k-ésima trayectoria más corta, SPT 'k-1' se encuentran entre cada par fuente-destino y 'k-1' bordes de cada uno de uno SPT se van a eliminar al mismo tiempo para cada combinación. Claramente, este algoritmo tiene complejidad combinatoria y obstruye el servidor en gráficos grandes. La gente me sugirió el algoritmo de Eppstein (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf). Pero este documento blanco cita un "dígrafo" y no vi una mención que funcione solo para los dígrafos. Solo quería preguntarle a la gente si alguien ha usado este algoritmo en un gráfico no dirigido.

Si no, ¿hay 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) + log V * (V))) la complejidad

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

realizamos una Djikstra modificado de la siguiente manera:

• Para cada nodo, en lugar de mantener la mejor relación costo-sabe actualmente de la ruta de principio-nodo. Mantenemos las mejores rutas K desde el nodo de inicio
• Al actualizar los vecinos de un nodo, no verificamos si mejora la mejor ruta actualmente conocida (como hace Djikstra), verificamos si mejora lo peor de K ' ruta actualmente conocida.
• Después de procesar la primera de las mejores rutas de K de nodos, no necesitamos encontrar K mejores rutas, pero solo tenemos K-1 restante, 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. Usamos esta cola de prioridad para determinar cuál de los K 'es mejor y se usará en las colas de prioridad de Djikstra como el representante del nodo.
  • En la otra cola de prioridad, la ruta más larga está en la parte superior. Usamos este para comparar las rutas candidatas a la peor de las rutas K '.