가중치 DAG에서 최단 경로 또는 최장 경로를 찾기 위해 위상 정렬을 수행하는 이유는 무엇입니까?

Question

모서리 완화를 수행하기 전에 왜 토폴로지 정렬을 수행해야 하는지 궁금합니다.

다음과 같이 하면 더 좋지 않을까요?시작 정점이 "s"인 경우

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

의도적으로 Visited[] 배열을 생략했습니다.

Answer 1

이 알고리즘을 사용하면 예상되는 시간 복잡도는 다음과 같습니다. O(V+E) 가장자리를 여러 번 방문해야 하기 때문입니다.

queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue

그러나 위상 정렬을 사용하면 모서리를 정확히 한 번 방문하도록 정점을 통과해야 하는 순서를 얻습니다.그래서 우리는 T.C.를 보장할 수 있었습니다.~의 O(V+E).

그래서 이 문제를 해결하기 위해 O(V+E) 우리는 위상 정렬을 사용합니다.

하지만 이것이 충분하지 않다고 생각합니다. 여기서 위상 순서를 사용하는 이유도 알아야 하며 다른 문제에 도움이 되도록 해야 합니다.

왜 토폴로지 순서인가?

위상 순서는 다음과 같은 순서를 제공합니다. 0 1 2 3 4 5 그런 다음 이 순서대로 노드에 도달하면(예를 들어 4) 그런 다음 우리는 이미 그것에 대한 최단 경로를 계산했습니다(4) 유형의 모든 가장자리(경로 포함) u -> v (v = 4) 이미 방문했습니다.