테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP) ======  
  * [[https://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths|위키피디아]] 참고
  * 그래프의 모든 정점쌍 사이의 최단 경로를 전부 구하는 문제이다.
  * Q개의 정점쌍에 대해서 최단 경로를 구해야 하는 문제나 (Q가 거의 n^2에 가깝게 크게 들어온다), 모든 정점쌍 사이의 거리중에서 최적값을 찾는 등의 문제가 있다.
  * 모든 정점쌍 사이의 최단 경로를 구하는 알고리즘은 대표적으로는 [[#플로이드-와샬 알고리즘]]이 있지만, [[ps:단일 출발지 최단 경로]] 알고리즘을 모든 정점에 대해서 돌리는 방법도 가능하고, 경우에 따라서는 그쪽이 더 효율적인 경우도 있다.
    * 하지만 웬만하면 그냥 무지성으로 [[#플로이드-와샬 알고리즘]]을 돌려도 거의 다 풀린다.
    * 그리고 Solved.ac 에서는 '전체쌍 최단 경로'라는 태그는 따로 없고, 대신 관련 문제에는 모두 '플로이드-와샬' 태그가 붙어 있다.

===== 플로이드-와샬 알고리즘 =====
<WRAP box round>
- 기본 난이도: 골드5 \\
- 기본 문제: [[ps:problems:boj:11404]] \\
- 필요한 사전 지식: 그래프
</WRAP>
  * [[wp>Floyd-Warshall_algorithm]] 참고
  * 가중치의 범위 (가중치 없음, 양수 가중치, 양수와 음수를 모두 포함하는 가중치)에 관계없이 모두 적용가능한 알고리즘이다. 
    * 음수 사이클이 있는지를 체크하는 용도로도 사용 가능하다.
  * 시간복잡도는 O(V^3). 하지만 코드가 매우 심플하고 상수항이 작다는 특징이 있다. dense한 그래프에서는 단일 출발지 최단 경로를 찾을때에도 O(|V||E|)인 벨만포드 알고리즘보다 더 빠르게 수행되는 경우도 있다고 한다
  * 하지만, 코드가 간단한것에 비해, 정확한 동작 원리를 이해하는 것은 그렇게 간단하지 않다. 실제로 구현해야 할때는 3중루프의 순서를 헷갈리지 않는것도 중요하다. 보통은 루프 인덱스 변수를 k,i,j 순서로 사용하고, d[i][j] = min(d[i][k]+d[k][j], d[i][j]) 와 같은 식으로 갱신하는 것이 일반적이다.

==== 구현 ====
  * 그래프가 인접행렬 형태로 주어지면 바로 실행할 수 있지만, 인접리스트 형태를 사용하는 다른 그래프 알고리즘과 일관성이 안맞는 문제가 있다. 일단은 인접행렬을 인자로 받게 만들었다. 필요하면 사용자가 인접리스트를 인접행렬로 변환해서 돌리도록 했다.
  * path reconstruction은 좀 복잡하다. 이게 필요하면 그냥 플로이드 대신 데이크스트라 V번 돌리는 식으로 해결하자
  * 무방향 그래프라면, dist(i,j)와 dist(j,i)를 동시에 업데이트해줄 수 있으므로, 루프 횟수를 절반으로 줄일 수 있다.

==== 코드 ====
  * [[:ps:teflib:graph#all_pairs_shortest_paths|teflib.graph.all_pairs_shortest_paths]]

==== 관련 문제 ====
  * [[ps:problems:boj:11404]] 표준문제. V<=100
  * [[ps:problems:boj:11265]] 벤치마크용. V<=500

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
===== 트리에서의 전체쌍 최단 경로 =====
<WRAP box round>
- 기본 난이도: 플래티넘5 \\
- 기본 문제: [[ps:problems:boj:1761]] \\
- 필요한 사전 지식: [[ps:LCA]]
</WRAP>
  * 웬만한 형태의 그래프에서는 그냥 플로이드를 돌려도 최적 시간복잡도에 근접하므로 시간초과가 나는 경우는 거의 없지만, 트리에서는 플로이드를 돌리는 것이 비효율적이다.
  * 모든 정점쌍에 대해서 최단경로가 필요한 경우
    * V번의 BFS/DFS 를 사용하자
    * 트리에서는 두 점사이의 경로가 유일하기 때문에 BFS/DFS로도 O(V)에 단일 출발지 최단 경로를 구할수 있다. V개의 시작점에 대해서 돌리면 총 O(V^2). 플로이드보다 훨씬 효율적이다.
  * Q개의 정점쌍에 대한 최단 거리만 필요 
    * [[ps:LCA]]를 이용하자
    * 트리에서는 두 점사이의 경로가 유일하고, 그 경로의 길이는 경로상의 엣지들의 가중치의 합이므로, 두 점사이의 최단거리는 단순한 형태의 [[ps:경로 쿼리]]가 된다. 이것은 LCA를 이용해서 구할 수 있다. 루트에서 각 노드까지의 거리를 미리 O(V)에 구해둔다면, u에서 v까지의 거리는 d(U,V) = d(root,U) +d(root,V) - d(root,lca)*2 로 구할수 있다. 쿼리당 걸리는 시간은 lca를 구하는데에 걸리는 시간과 동일하다.
    * LCA를 구하는 방법은 여러가지가 있지만, Q가 V와 비슷한 크기라면, HLD에 기반한 방법이 실질적으로 가장 빠르다. O(V)에 전처리를 한 뒤, O(logV)에 쿼리를 처리하게 되므로 시간복잡도는 O(V+QlogV) 이다.
    * Q가 크다면, LCA를 sparse table을 이용해서 처리하는 것이 더 빠를수 있다. 전처리에 O(VlogV)이 걸리고, O(1)에 LCA를 구할수 있다. 총 시간복잡도는 O(VlogV + Q)

===== 단일 출발지 최단 경로를 반복해서 풀기 =====
<WRAP box round>
- 기본 난이도: not rated \\
- 필요한 사전 지식: [[ps:SSSP]]
</WRAP>
  * 트리가 아니더라도, 그래프의 상태에 따라서 [[ps:SSSP]] 알고리즘을 모든 정점에 대해서 돌리는 것이 플로이드-와샬 보다 효율적인 경우가 있다.
  * 시간복잡도는 단일출발지 최단경로를 구하는 데에 O(T)가 걸린다면, 총 O(VT)가 된다. 이것이 플로이드의 O(V^3)보다 작으면 이쪽을 쓰는것이 유리하다. 
    * 만약 똑같이 O(V^3)이 걸린다면, 플로이드가 코드가 간단하고 상수값이 작은 편이므로 그냥 플로이드를 쓰는 것이 낫다.
  * 구체적인 예를 생각해보자
    * 가중치 없는 그래프
      * 그래프가 sparse 하다 => V번의 BFS.
        * BFS로 단일출발지 최단 경로를 구하는 데에는 O(E)가 걸리고, V번 반복하는데에는 O(EV)가 걸린다. E << V^2 일때는 플로이드보다 유리하다
      * 그래프가 sparse하지 않다 => 플로이드.
      * 그래프가 매우 dense 하다 => V번의 dense BFS
        * 사실 해본적은 없는데, dense BFS 를 이용하면 빠를거 같다. O(E)에 complement graph를 만들수 있고, 그 위에서 dense bfs를 돌리는 것은 O(E')에 구할수 있다 (E' = complement graph의 에지수). 총 O(E + VE')이 걸리니까, E'이 작으면 플로이드보다 빠르다.
    * 양수 가중치만 갖는 그래프
      * 그래프가 sparse하다 => V번의 데이크스트라
        * 데이크스트라로 단일출발지 최단 경로를 구하는데에 O(ElogV)가 걸리고 V번 반복하는데에는 O(VElogV)가 걸린다. |E|<(V^2)/logV 이면 플로이드의 O(V^3)보다 빠르다. 플로이드의 상수가 작은 것을 고려하면, 그래프가 많이 sparse해야 한다.
      * 그래프가 dense하다 => 플로이드
        * dense 그래프라면, 단일출발지 최단 경로를 구할때에 힙을 안쓰는 버전의 O(V^2) 데이크스트라를 쓰는 것이 유리하다. 그렇다 해도 전체 시간복잡도는 O(V^2)을 V번 반복하므로 O(V^3). 플로이드보다 빠르지 않으므로, 그냥 플로이드를 쓴다
    * 음수 가중치도 갖는 그래프
      * 그래프가 sparse하다 => 존슨 알고리즘
        * 그래프가 sparse 하더라도, 벨만-포드나 SPFA로 단일출발지 최단 경로를 구하게 된다면 O(VE)가 걸리고, 이것을 모든 노드에 돌리면 O(V^2E)로 느리므로, 플로이드를 써야 할것 같다
        * 하지만, 존슨 알고리즘을 이용하면, O(VE)에 양수 그래프로 변환한 뒤에 데이크스트라를 V번 돌리는 것으로 처리할수 있다. 총 O(VElogV)가 걸리므로 플로이드보다 빠르다
      * 그래프가 sparse하지 않다 => 플로이드

==== 관련 문제 ====
  * [[ps:problems:boj:3075]] V<=100, E<=100 으로 매우 sparse하므로, 데이크스트라를 반복하는 것이 효율적이다.
  * [[ps:problems:boj:14938]] V<=100, E<=100 으로 매우 sparse하므로, 데이크스트라를 반복하는 것이 효율적이다.
      
===== 활용 =====

==== 그래프의 지름, 반지름, 중심 ====
  * 트리에서는 두번의 DFS로 지름, 반지름을 찾을수 있지만, 일반 그래프에서는 그러한 간단한 방법은 없다.
  * 다소 무식해 보이지만, 전체쌍 최단 경로 문제로 변환해서 모든 dist(u,v)를 구한 뒤에 다음처럼 계산하는 것이 최선이다.  
    * 지름: $ \max_{u,v}{dist(u,v)} $
    * 반지름: $ \min_u\max_v{dist(u,v)} $
    * 중심: $ \text{argmin}_u\max_v{dist(u,v)} $
    * Median: $ \min_u \sum_v dist(s, t) $
  * 관련문제:
    * 2660: 센터와 반지름
  
==== Transitive Closure ====
  * [[wp>transitive closure]] 를 참고.
  * 한국어로 번역한 용어로는 '추이적 폐포', '전이적 폐쇄' 등이 쓰이는것 같은데, 뭐든 너무나도 어색하다. 그냥 Transitive Closure 라고 부르자;
  * 용어는 어렵지만, 의미는 어렵지 않다. 매우 단순하게 생각하면, 그래프가 주어지고, u->v 에지가 u에서 v로 이동가능하다는 것을 표현할때, 각 노드에서 출발해서 도착 가능한 모든 노드들을 계산한 것이라고 생각하면 된다.
  * 무방향 그래프에서는, 그냥 같은 [[ps:연결 요소]]에 있는 노드들은 모두 이동 가능하므로, 연결요소를 구하는 것과 동일하다. 그냥 BFS나 DFS를 돌려서 구하면 된다
  * 보통 사용되는 경우는 [[ps:DAG]]이다. u->v 에지가 u가 v보다 크다라는 관계를 표현하는 경우가 많다. 주요 문제는 크기 비교가 가능/불가능한 노드들을 찾거나, 순위를 확정할 수 있는/없는 노드를 찾는 식의 문제가 많이 나온다
    * 이 경우가 바로 APSP를 이용해서 transitive closure를 구해야 하는 경우이다.
  * DAG가 아니라 사이클이 있는 방향그래프에서는, 같은 SCC안의 노드들은 모두 
  * [To be filled] 비트셋을 쓰자!
  * 관련문제: 2458, 10159, 1613

==== APSP conjecture ====
  * [[https://koosaga.com/310]] 참고
  * APSP 문제는 다항시간에 풀리는 문제이기는 하지만, O(n^3)이라는 꽤 큰 시간이 들기 때문에 마냥 쉽지는 않은 문제다. 다른 문제들에 대해서도 문제가 어렵다는 것을 보이기 위해 (시간복잡도가 O(n^3)이상이라는 것을 증명하기 위해서), APSP 문제로 리덕션하는 접근법을 쓰는 경우가 있다고 한다.
  * [[https://koosaga.com/310]]의 Theorem 6 에는 이러한 O(n^3) 이상이 걸리는 문제들이 나열되어있다. 나중에 이러한 문제들을 접하게 되면, 빠르게 푸는 방법을 찾으려 고생하지 말고, 그냥 APSP로 바꿔서 O(n^3)에 풀도록 하자.
    * 앞에서 언급한 그래프의 반지름, 중심도 이 목록에 포함되어있다.
    * 그래프의 지름의 경우는 더 빠른 방법이 존재할 가능성이 있지만, 아직 발견되지 않았다고 따로 언급되어있다.


==== 임시메모 ====
11404 가중치/방향/N=100
2458 critical project/N=500
1956 가중치/방향/N=400/cycle 찾기
14938 가중치/무방향/스파스/N=100,M=100
2660 무가중치/무방향/N=50 / 반지름과 중심찾기
10159 transitive closure/N=100
1613 transitive closure/N=400
11780 [역추적]가중치/방향/N=100
1719 [역추적]가중치/무향/N=200
1507 [응용]..
2617 transitive closure/N=100
2610 transitive closure/N=100
17182 가중치/방향/N=10 + TSP
11562 가중치(0-1)/방향/N=250
11265 가중치/방향/N=500
11423 가중치/무향/N=100 
21278 가중치/무향/N=100 
21940 가중치/방향/N=200 / 중심찾기 변형
11097 (DAG 아닌) Transitive reduction
2219 가중치/무향/N=200 / 중심찾기
16958 이건 플로이드 아닌거같은데
13168 가중치/무향/N=100 
9870 N=200
12875 무가중치/무향/N=50/ 지름찾기
2273 transitive closure/ N=256