Sugestões para KSPA no grafo não direcionado

Question

Há uma implementação personalizada do KSPA que precisa ser re-escrita. A implementação atual usa um algoritmo de Dijkstra modificado cujo pseudocódigo é mais ou menos explicado abaixo. É comumente conhecido como KSPA usando a estratégia de borda eliminação acho que sim. (Eu sou um novato no gráfico-teoria).

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 eu entendo o algoritmo, para obter k caminho mais curto, 'k-1' TSC encontram-se entre cada par origem-destino e 'k-1' bordas de cada de um SPT devem ser apagadas simultaneamente para cada combinação . É evidente que este algoritmo tem complexidade combinatória e obstrui o servidor em grandes gráficos. As pessoas me sugeriu o algoritmo de Eppstein ( http: //www.ics. uci.edu/~eppstein/pubs/Epp-SJC-98.pdf ). Mas este papel branco cita um 'dígrafo' e eu não vi uma menção de que ele funciona apenas para dígrafos. Eu só queria perguntar pessoas aqui se alguém usou este algoritmo em um grafo não direcionado?

Se não, existem bons algoritmos (em termos de tempo de complexidade) para implementar KSPA em um grafo não direcionado?

Agradecemos antecipadamente,

Answer 1

Tempo complexidade: O (K * (E * log (K) + V * log (V)))

complexidade memória de O (K * V) (+ O (E) para armazenar a entrada).

Realizamos uma Djikstra modificado da seguinte forma:

• Para cada nó, em vez de manter o custo melhor atualmente conhecida de rota de start-nó. Nós mantemos as melhores rotas K do nó de início
• Ao atualizar um nodos vizinhos, nós não verificamos se ele melhora o melhor caminho conhecido atualmente (como Djikstra faz), vamos verificar se ele melhora o pior da K' melhor caminho conhecido atualmente.
• Depois que nós já processada a primeira de K melhores rotas de um dos nós, nós não precisamos de encontrar K melhores rotas, mas só tem K-1 remanescente, e depois de mais um K-2. Isso é o que eu chamada K'.
• Para cada nó vamos manter duas filas de prioridade para a K' melhores atualmente conhecidos de caminho-comprimentos.
  • Em uma prioridade da fila o caminho mais curto está no topo. Usamos essa fila de prioridade para determinar qual dos K' é melhor e será usado nas regulares filas de prioridade de Djikstra como representante do nó.
  • Na outra fila de prioridade o caminho mais longo está no topo. Nós usamos esta para comparar caminhos candidatos para o pior dos caminhos a K'.