전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP)

• 위키피디아 참고
• 그래프의 모든 정점쌍 사이의 최단 경로를 전부 구하는 문제이다.
• Q개의 정점쌍에 대해서 최단 경로를 구해야 하는 문제나 (Q가 거의 n^2에 가깝게 크게 들어온다), 모든 정점쌍 사이의 거리중에서 최적값을 찾는 등의 문제가 있다.
• 모든 정점쌍 사이의 최단 경로를 구하는 알고리즘은 대표적으로는 플로이드-와샬 알고리즘이 있지만, 단일 출발지 최단 경로 (Single Source Shortest Path) 알고리즘을 모든 정점에 대해서 돌리는 방법도 가능하고, 경우에 따라서는 그쪽이 더 효율적인 경우도 있다.
  • 하지만 웬만하면 그냥 무지성으로 플로이드-와샬 알고리즘을 돌려도 거의 다 풀린다.
  • 그리고 Solved.ac 에서는 '전체쌍 최단 경로'라는 태그는 따로 없고, 대신 관련 문제에는 모두 '플로이드-와샬' 태그가 붙어 있다.

• 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)를 동시에 업데이트해줄 수 있으므로, 루프 횟수를 절반으로 줄일 수 있다.

• teflib.graph.all_pairs_shortest_paths

• 플로이드 표준문제. V⇐100
• 11265 벤치마크용. V⇐500

• 웬만한 형태의 그래프에서는 그냥 플로이드를 돌려도 최적 시간복잡도에 근접하므로 시간초과가 나는 경우는 거의 없지만, 트리에서는 플로이드를 돌리는 것이 비효율적이다.
• 모든 정점쌍에 대해서 최단경로가 필요한 경우
  • V번의 BFS/DFS 를 사용하자
  • 트리에서는 두 점사이의 경로가 유일하기 때문에 BFS/DFS로도 O(V)에 단일 출발지 최단 경로를 구할수 있다. V개의 시작점에 대해서 돌리면 총 O(V^2). 플로이드보다 훨씬 효율적이다.
• Q개의 정점쌍에 대한 최단 거리만 필요
  • 최소 공통 조상 (Lowest Common Ancestor / LCA)를 이용하자
  • 트리에서는 두 점사이의 경로가 유일하고, 그 경로의 길이는 경로상의 엣지들의 가중치의 합이므로, 두 점사이의 최단거리는 단순한 형태의 경로 쿼리가 된다. 이것은 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)

• 트리가 아니더라도, 그래프의 상태에 따라서 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하지 않다 ⇒ 플로이드

• 3075 V⇐100, E⇐100 으로 매우 sparse하므로, 데이크스트라를 반복하는 것이 효율적이다.
• 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 를 참고.
• 한국어로 번역한 용어로는 '추이적 폐포', '전이적 폐쇄' 등이 쓰이는것 같은데, 뭐든 너무나도 어색하다. 그냥 Transitive Closure 라고 부르자;
• 용어는 어렵지만, 의미는 어렵지 않다. 매우 단순하게 생각하면, 그래프가 주어지고, u→v 에지가 u에서 v로 이동가능하다는 것을 표현할때, 각 노드에서 출발해서 도착 가능한 모든 노드들을 계산한 것이라고 생각하면 된다.
• 무방향 그래프에서는, 그냥 같은 연결 요소 (Connected Component)에 있는 노드들은 모두 이동 가능하므로, 연결요소를 구하는 것과 동일하다. 그냥 BFS나 DFS를 돌려서 구하면 된다
• 보통 사용되는 경우는 방향 비순환 그래프 (Directed Acyclic Graph; DAG)이다. u→v 에지가 u가 v보다 크다라는 관계를 표현하는 경우가 많다. 주요 문제는 크기 비교가 가능/불가능한 노드들을 찾거나, 순위를 확정할 수 있는/없는 노드를 찾는 식의 문제가 많이 나온다
  • 이 경우가 바로 APSP를 이용해서 transitive closure를 구해야 하는 경우이다.
• DAG가 아니라 사이클이 있는 방향그래프에서는, 같은 SCC안의 노드들은 모두
• [To be filled] 비트셋을 쓰자!
• 관련문제: 2458, 10159, 1613

• 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