ps:shortest_path_faster_algorithm
Shortest Path Faster Algorithm (SPFA)
- worst-case 시간 복잡도는 벨만 포드와 똑같은 O(VE)이지만, 평균 시간복잡도는 O(E)라고 한다. 평균 복잡도만 보면 무려 다익스트라보다도 빠르기는 하지만, PS에서 이러한 문제가 나올때는 대부분의 경우 테스트 케이스에 SPFA가 O(VE)로 돌게 만드는 저격용 케이스가 들어있으므로 O(E)를 기대하기는 어렵다.
- 그렇지만 어쨌든 벨만포드보다 더 안좋아지지는 않으므로 음수 웨이트 엣지가 있는 경우에는 SPFA를 쓰기로 하자
- 만약 그래프가 dense해서 E=O(V^2)이라면, 총 시간 복잡도는 O(V^3)이 된다. 이 경우에는 같은 O(V^3)인 플로이드-와샬 알고리즘을 쓰는 것이 상수항이 작아서 더 낫다.
- 그래프에 음수 웨이트 엣지가 있는 경우에는, 음수 웨이트 사이클이 생기는 경우도 있다. 이 경우에는 사이클을 계속 돌면 코스트가 무한히 줄어드므로, 제대로 된 최단경로를 찾는 것이 불가능하므로 따로 처리해줘야 한다.
- 벨만-포드에서는 바깥쪽 루프가 |V|번을 돌았는데도 값이 갱신이 된다면 음수 사이클이 있는것으로 판단한다
- SPFA에서는 몇가지 방법이 있다.
- 간단한 방법은, 각 노드의 업데이트 횟수 또는, 각 노드까지의 최단 경로에 포함된 노드의 갯수를 이용해서 판정하는 것. 사이클이 생기는 즉시 찾을수는 없고, 사이클을 따라서 얼만큼 돌아간 다음에 사이클이 있다는 것을 발견하게 된다. 그래도 후자쪽이 좀더 효율적이다
- 어떤 노드까지의 거리를 업데이트 할때, 그 노드가 업데이트 된 횟수를 카운트해서, |V|번 이상이면 음수 사이클이 있는 것으로 판단한다
- 어떤 노드까지의 거리를 업데이트 할때, 그 노드까지의 최단경로에 포함된 노드의 갯수를 갱신해서, 갯수가 |V|개 이상이면 음수 사이클이 있는 것으로 판단한다. [이 방법으로 구현했다]
- 조금 더 복잡한 방법은, 어떤 노드까지의 거리를 업데이트 할때 그 노드의 이전 노드를 함께 저장한다. 이러면 모든 노드로의 경로를 트리 형태로 갖게 되는데, 이중에서 사이클이 있는지를 체크하는 DFS를 n번마다 돌려서 처리하는 것이다.
- 출처는 여기
- DFS를 돌리는 것은 O(n)이지만, 그 작업을 n번 갱신될때마다 한번씩만 수행하므로 시간복잡도가 더 늘어나지는 않는다.
- 작업 자체는 좀더 무거워 보이지만, 일반적으로는 음수 사이클을 좀더 빨리 디텍트할수 있어서 더 빠르게 돈다고 한다 (실제 구현은 안해봤다)
- 그 외에 내가 시도해본 것은, 각 노드들마다 그 노드까지 경로에 속하는 노드들을 모두 셋으로 저장하고 있는 방법이다. 어떤 노드까지의 거리를 업데이트할때 사이클이 생기는 지의 여부는 사이클이 생기는 순간 O(1)에 찾을수 있지만, 노드를 갱신할때마다 셋을 클론해야 하는 작업이 필요해서 시간복잡도상 손해를 본다. 사이클을 빨리 찾을수 있기 때문에 시간이 많이 단축되는 경우도 있지만, 그렇지 못할때에는 오히려 소폭 느려지는 경우도 있다.
- 음수 사이클이 존재하지 않는 것이 확정된 문제에서는, 그냥 음수사이클 체크를 빼버림으로써 속도 향상이 가능하다
- 음수 사이클이 존재할때 처리하는 방법에 관해서는 문제마다 요구하는 것이 조금씩 다를 수 있는데 아래 음수 사이클 처리를 참고.
음수 사이클 처리
- 음수 사이클이 존재할때 처리하는 방법에 관해서는 문제마다 요구하는 것이 조금씩 다를수 있다.
- 1) 음수 사이클이 존재하지 않는다는 조건이 주어져있을때, 최단 경로를 찾는 문제
- ⇒ 음수 사이클 체크 로직을 아예 빼버리고 최단경로 알고리즘을 돌리는게 가장 효율적
- 2) 최단경로를 찾되, 출발지점에서 도달할 수 있는 음수 사이클이 존재하면 다르게 처리하는 문제
- ⇒ 최단경로 알고리즘을 돌리다가 음수 사이클이 발견되면 거기서 바로 중단하면 된다.
- 3) 최단경로를 찾되, 출발지점에서 음수 사이클을 거쳐서 도착지점까지 도달할 수 있는 경로가 있을때만 다르게 처리하는 문제
- ⇒ 최단경로 알고리즘을 돌리다가 음수 사이클을 발견하더라도 그 사이클에서 도착지점까지 갈 수 없으면, 출발점에서 도착점까지의 최단 경로는 존재하므로 계속 알고리즘을 돌려야 한다. 이것을 하기 위해서 발견한 음수사이클에서 시작해서 다시 DFS같은것을 돌려서 도착점까지 경로가 존재하는지를 확인하는 식으로 가르치는 경우도 있는데, 더 쉬운 방법은 음수 사이클이 발견되면 그 노드까지의 거리를 마이너스 무한대로 저장하는 것이다. 그러고 SPFA를 계속 돌리면 알아서 거기에서부터 도달 가능한 노드들은 모두 마이너스 무한대로 갱신되고, 한번 갱신된 노드로는 다시 방문하지 않으므로 루프가 계속 이어지지도 않는다. (c++ 이라면, 무한대는 실수형으로만 포함되므로 거리를 정수형으로 저장하고 있었다면 사용하기 어려운 방법이 맞다. 파이썬에서는 그냥 하면 된다)
- 4) 그래프 안에 음수 사이클이 존재하는지 묻는 문제
- ⇒ 단순히 임의의 출발지점을 잡아서 최단경로 알고리즘을 돌릴 경우에는, 출발지점에서 도달 불가능한 노드들 사이에서 음수 사이클이 존재할 경우 이것을 찾을수 없다.
- ⇒ 출발지점을 바꿔가면서 반복해서 돌릴수도 있지만, 좀더 간단한 것은 초기화할때 모든 노드를 도달 가능한 것으로 설정하고 알고리즘을 시작하는 것이다. 벨만포드라면 dist값을 INF가 아니라 0으로 초기화하고 시작하면 된다. SPFA라면 거기에 더불어서 큐에 모든 노드들을 집어넣을 상태로 시작하면 된다.
- ⇒ 라이브러리에 있는 함수를 수정없이 쓰고 싶은 경우에는 이렇게 초기값을 마음대로 변경할수 없을수도 있는데, 이때 가능한 방법은 그래프에 가상의 노드를 하나 추가하는 것이다. 그 노드에서 다른 모든 노드로 연결되는 엣지를 추가한 다음에, 그 노드를 출발점으로 해서 최단경로 알고리즘을 돌리면 같은 효과를 얻을수 있다. 엣지의 수가 |V|+|E|로 늘어나므로, 벨만포드 같은 경우에는 총 시간복잡도가 O(|V|^2 + |V||E|)가 된다. |E|가 작은 경우에는 속도 저하가 생길수도 있다. SPFA에서는 이렇게 추가한 시작 노드가 다시 큐에 들어갈 일이 없기 때문에 딱히 느려질 일은 없다.
- teflib의 구현에서는 v1.0버전에서는 음수 사이클이 있으면 바로 예외를 던지고 중단하는 식으로 구현했다가, v1.1로 코드를 업데이트 하면서 음수 사이클이 있으면 거리를 마이너스 무한대로 갱신하고 끝까지 돌리는 식으로 구현을 수정했다. 2)번 유형을 풀때는 조금 더 느려지지만, 3)번 유형을 같이 처리할수 있어서 그렇게 했다. 2)번 유형을 처리할 때는, spfa를 돌려서 얻은 각 노드까지의 거리들 중에 -INF가 포함되어있는지를 확인하면 된다.
코드
관련 문제
ps/shortest_path_faster_algorithm.txt · 마지막으로 수정됨: 2022/09/22 07:13 저자 teferi
토론