====== 전체쌍 최단 경로 (All-pairs shortest path) ======
  * [[https://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths|위키피디아]] 참고
  * 진짜로 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) 에 처리 가능하다.
    * 참고문제: [[ps:problems:boj:1761]]
  * 트리가 아닌 그래프에서는 쿼리에 특화된 방법은 없고, 그냥 전체 페어에 대해 다 계산하는게 최선이다.
  * [[ps:단일 출발지 최단 경로]] 알고리즘을 모든 노드에서 돌려서 푸는 방법과, [[#플로이드-와샬 알고리즘]]을 사용하는 방법이 있다.
  * [[#플로이드-와샬 알고리즘]]의 시간복잡도는 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하다 => 플로이드

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

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

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

==== 관련 문제 ====
  * [[ps:problems:boj:11404|플로이드]]