전체쌍 최단 경로 (All-pairs shortest path)

위키피디아 참고
진짜로 O(n^2)개의 모든 페어에 대해서 전부 구해야 하는 문제가 있고, 그 정도까지는 아니고 Q개의 쿼리에 대해서 구해야 하는 문제가 있을수 있다.
트리에서는 LCA를 이용해서 처리할 수 있다. 루트에서 각 노드까지의 거리를 미리 O(N)에 구해둔다면, u에서 v까지의 거리는 d(U,V) = d(root,U) +d(root,V) - d(root,lca)*2 로 구할수 있다. 쿼리당 걸리는 시간은 lca에 걸리는 시간과 동일하다.
- LCA를 구하는 방법이 여러가지인데, Q가 N과 비슷한 크기라면, HLD에 기반한 방법이 실질적으로 가장 빠르다. O(N)에 전처리를 한 뒤, O(logN)에 쿼리를 처리하게 되므로 시간복잡도는 O(N+QlogN) 이다
- 전체 페어에 대해서 거리를 모두 구하거나.. 그정도는 아니라도 Q가 크다면, sparse table을 이용해서 O(NlogN)에 전처리하고 O(1)에 LCA 쿼리를 처리하는 방식을 써야 한다. O(N^2) 또는 O(Q) 에 처리 가능하다.
- 참고문제: 1761
트리가 아닌 그래프에서는 쿼리에 특화된 방법은 없고, 그냥 전체 페어에 대해 다 계산하는게 최선이다.
단일 출발지 최단 경로 (Single Source Shortest Path) 알고리즘을 모든 노드에서 돌려서 푸는 방법과, 플로이드-와샬 알고리즘을 사용하는 방법이 있다.
플로이드-와샬 알고리즘의 시간복잡도는 O(V^3)이고, 코드가 간단하고 상수값이 작은 편이라서, 다른 방법으로도 O(V^3)이 나온다면 플로이드 알고리즘을 쓰는 것이 유리하다
구체적인 예를 생각해보자
- 가중치 없는 그래프:
  - 그래프가 sparse 하다 ⇒ V번의 BFS.
    - BFS로 단일출발지 최단 경로를 구하는 데에는 O(E)가 걸리고, V번 반복하는데에는 O(EV)가 걸린다. 플로이드보다 유리하다
  - 그래프가 dense 하다 ⇒ V번의 dense BFS
    - dense 그래프에서는 V번의 BFS로 얻은 O(EV)가 플로이드의 O(V^3)보다 빠르지 않으므로 플로이드를 써야 할것 같다.
    - 하지만 dense BFS를 이용하면 단일출발지 최단 경로를 O(V)에 구할수 있으므로, 총 O(V^2)이 걸려서 플로이드보다 빠르다.
- 양수 가중치만 갖는 그래프
  - 그래프가 sparse하다 ⇒ V번의 데이크스트라
    - 데이크스트라로 단일출발지 최단 경로를 구하는데에 O(ElogV)가 걸리고 V번 반복하는데에는 O(VElogV)가 걸린다. |E|<(V^2)/logV 이면 플로이드의 O(V^3)보다 빠르다. 플로이드의 상수가 작은 것을 고려하면, 그래프가 많이 sparse해야 한다.
  - 그래프가 dense하다 ⇒ 플로이드
    - dense 그래프라면, 힙을 안쓰는 버전의 데이크스트라를 쓰는 것이 유리하다. 그러면 O(V^2)을 V번 반복하므로 O(V^3). 플로이드보다 빠르지 않으므로, 그냥 플로이드를 쓴다
- 음수 가중치도 갖는 그래프
  - 그래프가 sparse하다 ⇒ 존슨 알고리즘
    - 그래프가 sparse 하더라도, 벨만-포드나 SPFA로 단일출발지 최단 경로를 구하게 된다면 O(VE)가 걸리고, 이것을 모든 노드에 돌리면 O(V^2E)로 느리므로, 플로이드를 써야 할것 같다
    - 하지만, 존슨 알고리즘을 이용하면, O(VE)에 양수 그래프로 변환한 뒤에 데이크스트라를 V번 돌리는 것으로 처리할수 있다. 총 O(VElogV)가 걸리므로 플로이드보다 빠르다
  - 그래프가 dense하다 ⇒ 플로이드

플로이드-와샬 알고리즘

Floyd-Warshall_algorithm 참고
위키 에 의하면 빠른 행렬곱 연산을 이용해서 속도를 높이는 방법이 있다고 한다. 그렇지만 상수항이 커서 아주 큰 그래프에서만 효과있다고 한다. 아마도 PS에서는 신경안써도 될거 같다
음수 가중치 엣지가 있는 그래프에서도 잘 동작한다. 만약 음수 사이클이 있는지를 체크하고 싶다면 dist[u][u]<0 이 되는 u가 있는지를 찾으면 된다.
인접행렬 형태로 주어진 그래프에서 O(|V|^3)에 계산된다. 하지만 코드가 매우 심플하고 상수항이 작다는 특징이 있다. dense한 그래프에서는 단일 출발지 최단 경로를 찾을때에도 O(|V||E|)인 벨만포드 알고리즘보다 더 빠르게 수행되는 경우도 있다고 한다

구현

그래프가 인접행렬 형태로 주어지면 바로 실행할 수 있지만, 인접리스트 형태를 사용하는 다른 그래프 알고리즘과 일관성이 안맞는 문제가 있다. 일단은 인접행렬을 인자로 받게 만들었다. 필요하면 사용자가 인접리스트를 인접행렬로 변환해서 돌리도록 했다.
path reconstruction이 필요할 경우도 있는데.. 지금은 고려 안함. 필요하면 나중에 생각해보겠음..

코드

teflib.graph.all_pairs_shortest_paths

목차

전체쌍 최단 경로 (All-pairs shortest path)

플로이드-와샬 알고리즘

구현

코드

관련 문제