bellman-ford알고리즘은 E개의 모든 간선에 대해서 V번 업데이트 해보는데, spfa는 E개의 모든 간선을 업데이트 하는 대신 갱신된 노드에 연결된 간선들에 대해서만 업데이트 한다.
bellman-ford처럼 모든 간선에 대해서 업데이트를 하더라도, 결국은 직전에 갱신되었던 노드에 연결된 노드들만 업데이트될 것이기 때문에, spfa는 bellman-ford에서 불필요한 업데이트 과정을 빼서 성능의 향상을 노려볼 수 있다.
하지만 spfa역시 최악의 경우에는 bellman-ford와 같다고 하고, 평균적으로 O(E)의 시간복잡도를 갖는다고 한다.
그리고 또 하나 문제가 되는 것이... 바로 음수 사이클의 존재 여부를 판별하는 것인데, 일단 시작점에서 각 점들까지의 최단거리는 최대 V-1개의 edge로 연결되어 있고, 한 번 update할 때마다 최단 경로를 구성하는 적어도 하나의 edge는 찾게 되므로 최대 V-1번만 update하면 최단 경로가 찾아지고, 만약 negative cycle이 존재한다면 V번째도 update(relax)가 될 것이다.
(정점의 개수V를 n으로 놓고 써야겠다.)
spfa같은 경우는 조금 까다로워 보일 수 있는데, 일단 spfa방식은 queue를 사용하고, bfs와 유사하기 때문에 bfs에서의 한 단계를 수행할 때마다 (최단 경로를 구성하는) 적어도 하나의 edge는 찾게 될 것이다. 그러므로 bfs의 단계가 최대 n-1번만 실행되고 더이상 실행이 안되어야 정상인데, 만약 더 n번이상 실행된다면 negative cycle이 있는 것으로 볼 수 있겠다.
더 간단한 방법으로는 각 정점이 queue에 들어가는 횟수를 기록해놓고 그 중 하나라도 n번 이상이 되면 negative cycle이 있는 것으로 판별하는 것이다. negative cycle이 없다면 어떤 정점이 queue에 n번 들어가기전에 이미 최단거리는 구해졌을 것이다. 그래서 어떤 정점이 queue에 n번 들어갈리도 없을 것이다.
그리고 내가 잘못 생각했던 것이, 그냥 정점이 update될때마다 횟수를 세서 n번 이상 update되면 negative cycle로 판별하는 것이었는데, 통과할 때도 있겠지만... 안되는 것이... 일단 반례를 찾았다. 정점이 2개가 있고, 그 두 정점을 연결하는 edge가 여러개인 경우에 negative cycle이 있다고 잘못 판별하게 된다.
ex) A와 B사이에 A에서 B로 가는 각각 가중치가 5, 4, 3, 2, 1이렇게 있을 때 5번이나 갱신하게 된다.
- 끊임없이 배우고 생각하고 깨닫자.
추가+) 11657 타임머신 문제를 spfa로 풀어보았다. 위의 방법중에, bfs의 단계를 세주는 방식으로 구현해봤는데, bfs의 단계의 수를 cnt에 기록하고, cnt가 n이상이 되면 negative cycle인 것으로 판단하였다. 근데 cnt가 n 이상인지 판단하는 위치가 중요하다.
1) WA를 받는 코드(cnt가 n이상인지 판단하는 위치 잘 보기)
이렇게 할 경우, n-1번째 단계에서서 최단 경로에 속한 마지막 edge를 찾은 후 queue에 마지막 vertex가 들어가 있을것이다. 그리고 cnt=n-1일 것이다. 그리고 다시 while loop로 올라가서 내려오면서 보는데, 이미 최단 경로를 찾았기 때문에, 마지막 vertex에 연결된 점들은 더이상 갱신되지 않을 것이다. 그래서 queue는 비게되고, 여기서 while문을 탈출하면 되는데, 문제는 저 cnt>=n인지를 보는 코드가 아래에 위치해 있기 때문에, cnt++을 한 후 cnt는 n이되어 negative cycle로 판별하고 종료해버린다.
그렇기 때문에 이 것을 해결하기 위해서 저 부분만 위로 올려주면 된다.
2) AC를 받는 코드(cnt가 n이상인지 판단하는 위치 잘 보기)
이렇게 바꿔주면, 위에서 말한 경우는 while(!q.empty()) 이 부분에서 while loop를 탈출하게 될 것이다.
음 이렇게 쓰고 보니 좋은 방식인지는 모르겠다.
아니면 그냥 중간에 q가 비어버리면 break를 시킨다든지 하는 방법도 있을 것이다.
댓글 없음:
댓글 쓰기