최단 경로 알고리즘 업데이트

N 도시가있다 그들에게 연결 M 양방향 도로, 나는 최단 경로 알고리즘 업데이트

이 개 고정 도시 A와 B

사이의 최단 경로를 찾을 필요가있다 그러나 문제는 Q 쿼리가 주어진 것입니다 두 도시 간의 경로가 차단되어 있으므로 Q 쿼리마다 최단 경로를 찾아야합니다.

나에게 시간 제한 초과 오류를주고 내 무력 알고리즘에 내 시간 복잡도는 O (QNlogN가), 난 내 솔루션을 향상시킬 수있는 방법 도와주세요

Pseduo 코드 :

for u in Q: 
    cin>>a>>b; 
graph[a][b] = graph[b][a] = INFINITY VALUE 
dijkstra algorithm(); 
cout<<Distance[D]<<endl;

MY CODE Which Is giving me Time Limit Exceeded Error

Plese 도움말 알고리즘을 개선하려면 어떻게합니까?

이 사이트에는 최단 경로 또는 Djikstra의 알고리즘을 다룰 수있는 게시물이 많이 있거나 google로 이동해야합니다. –

[가능한 최단 경로 알고리즘] (http://stackoverflow.com/questions/1846836/the-best-shortest-path-algorithm) –

@DavidColer 그의 시간 복잡성은 그가 Dijkstra의 알고리즘을 사용하고 있음을 보여줍니다. –

용지 Vickrey Prices and Shortest Paths: What is an edge worth? by John Hershberger and Subhash Suri은 O (NlogN + M) 시간에이 문제를 해결하는 방법을 보여줍니다. 여기서 N은 정점의 수이고 M은 가장자리의 수입니다.

이렇게하면 차단 된 도로에 따라 M 응답을 미리 계산할 수 있으므로 O (NlogN + M + Q)의 전체 복잡성에 대해 O (1)의 각 쿼리에 응답 할 수 있습니다.

2014-12-30 20:18:10

답변