Algorithm 12 - APSP

 All pairs shortest path problem (APSP)
이는 각 노드 모두에서 모든 노드로 최소 경로를 찾는 문제로 이전과 달리 모든 노드가 source vertex가 된다. 즉 주어진 adj matrix를 가지고 i에서 j까지의 최소 경로인 matrix를 새로 만들어내야 한다.

따라서 이전의 알고리즘을 사용하면 다시 vertex 개수 v만큼이 추가되므로 O(v2log v+ velog v)나 O(v2e)의 time complexity를 가지게 된다. 이는 세제곱 이상이므로 해당 알고리즘들을 실전적으로 사용할 수 없다.

한 가지 brute force, naive 방법은 1개부터 n-1개의 edge를 가지는 shortest path를 모두 각각 계산하는 것이다. 그리고 이 중 가장 최소 인 것을 선택하면 i에서 j로 최소 경로를 찾을 수 있다.

이는 adj matrix를 가지고 가능한 경로를 행과 열을 선택해가며 하나씩 추가하여 최소값을 선택하는 것으로 L(n)을 얻을 수 있다.
이 과정은 각 단계에서 얻은 매트릭스와 인접 행렬을 곱하는 것과 비슷하다. 대신, 각 곱의 결과를 더하지 않고, 해당 결과들 중에 가장 작은 것을 다음 단계의 매트릭스 값으로 선정하면 된다.
i.e L(4) = L(3) x W = min( i*j ) 단, 곱셈과 같은 방법으로 곱하는게 아니라 두 매트릭스 값을 더해야 한다. (경로의 weight이므로)

그러나 여전히 해당 방법은 O(v4)의 time complexity를 가지고 있으므로 사용하기가 어렵다. 그러나 이 아이디어를 가지고 우리는 dynamic programming을 적용해 더 실전적인 알고리즘을 얻어낼 수 있다.

FLoyd-warshall algorithm
APSP를 해결하는 dynamic programming 방법. shortest path problem을 정의하기 위해 negative weight cycle만 없으면 모든 경우에 적용 가능하다.
intermediate vertex : i부터 j까지 가는 경로에서 거치는 모든 노드 (except source and destination)

i부터 j까지 가는 최적 경로에 대해 어떤 intermediate vetex k 가 포함될 수도 있고, 아닐 수도 있다. 전자라면 k를 기준으로 다시 i -> k, k->j로 분리할 수 있고, 만약 k가 포함되지 않는다면 intermediate vertex에서 k를 제거해도 된다.

이 방법을 통해 for루프에서 n개를 모두 확인하지 않고도 tabulation을 통해 이전 결과를 비교하여 최적 경로를 찾을 수 있다. (O(1)의 constant time만 필요)
따라서 전체 loop도 한 차수가 줄어든 O(v3)의 time complexity를 가진다.

transitive closure : 모든 쌍의 노드 사이에 path가 존재하는 것. 즉, 어떤 경로로든 두 노드 사이에 경로가 존재하면 된다.
이를 확인하려면 floyd warshall algorithm을 그냥 모든 edge에 대해 weight를 1로 두고 D를 획득하여 무한인 경로가 존재하는지 확인하면 된다. 만약 무한인 경로가 존재한다면 어떤 경로를 통해서도 도달하지 못하는 쌍이 있다는 의미이다.