25 All-Pairs Shortest Paths

25 All-Pairs Shortest Paths
이 챕터에서, 우리는 한 그래프에서 정점들의 모든 쌍 사이의 최단 경로를 찾는 문제를 고려한다. 이 문제는 road atlas에 대해 도시들의 모든 쌍 사이의 거리 테이블을 만들 때 발생할지도 모른다. Chapter 24에서 처럼, 우리는 가중치가 있고, 방향이 있는 그래프 G = (V, E)가 주어지는데, 가중치 함수 w : E -> R를가지고 있고, 간선에대해 실수값 가중치를 매핑시킨다. 우리는 V에 있는 정점 u와 v의 ㅁ든 쌍에 대해 u에서 v로 가는 최단 경로 (가장 적은가중치)를 발견하고자 한다, 거기에서 한 경로의 가중치는 그것의 구성되는 간선들의 가중치들의 합이다. 우리는 일반적으로 표 형식의 output을원한다: u의 행과 v의 열에 있는 entry는 u에서 v로가는 최단 경로가 되어야만 한다.

우리는 single-source shortest-paths algorithm을 |V|번 작동시켜서 모든 쌍의 최단경로 문제를 해결할 수 있다, source로서 각 정점에 대해 한 번씩. 만약 모든 간선 가중치들이 양수라면, 우리는 Dijkstra의 알고리즘을 사용할 수 있다. 만약 우리가 min-priority queue의 linear-array 구현을 사용한다면, 그 작동시간은 O(V^3 + VE) = O(V^3)이 된다. min-priority queue의 binary min-heap 구현은 O(VElgV)의 작동 시간을 낸다. 그리고 이것은 그 그래프가 sparse하다면 개선물이다. 대안적으로, 우리는 피보나치 힙으로 min-priority queue를 구현할 수 있고, 이것은 O(V^2lgV + VE)의 작동시간을 낸다.

만약 그 그래프가 음의 가중치 간선들을 가진다면, 우리는 다익스트라 알고리즘을 사용할 수 없다. 대신에, 우리는 각 정점으로 부터 한 번씩 더 느린 벨만 포드 알고리즘을 사용해야만 한다. 그 결과 작동 시간은 O(V^2E)이고, dense graph에 대해서는 O(V^4)이다. 이 챕터에서, 우리는 어떻게 이것을 더 잘할지를 볼 것이다. 우리는 또한 행렬 곱에 대해 모든 쌍의 최단 경로 문제의 연관성을 조사하고, 그것의 대수적 구조를 공부한다.

그래프의 인접리스트 표기를 사용하는, single-source algorithms과 다르게,  이챕터에서 대부분의 알고리즘들은 인접행렬 표기를 사용한다. (Section 25.3에서 sparse graphs에 대한 Johnson의 알고리즘은 인접리스트를 사용한다.) 편의성을 위해, 우리는 그 정점들이 1,2,...,|V|로 순서가 부여되었다고 가정한다, 그래서 그 입력은 n X n 행렬 W이고, n개의 정점을 가진 방향이 있는 그래프 G = (V,E)의 간선 가중치를 나타낸다. 즉, W = (w_ij)이고,



우리는 음의가중치 간선을 허용하지만, 우리는 입력 그래프가 어떠한 음의 가중치 사이클들을 포함하지 않는 다고 가정한다.

이 챕터에서 나타내어지는 모든 쌍의 최단 경로 알고리즘의 tabular output은
n X n 행렬 D = (d_ij) 이고, 여기에서 entry d_ij는 정점 i에서 정점j로 가는 최단 경로의 가중치를포함한다. 즉, 만약 우리가 &(i,j)를 정점 i에서 j로 가는 최단 경로 가중치로 표기한다면 (Chapter 24에서 처럼), 그러면 종료시에 d_ij = &(i, j)가 된다.

입력 인접 행렬에서 모든 쌍의 최단 경로 문제를 해결하기 위해서, 우리는 최단 경로 가중치뿐만 아니라, predecessor matrix 𝚷 = (𝝅_ij) 또한 계산해야 한다. 여기에서 만약 i = j 이거나 i에서 j로 가는 경로가 없다면 𝝅_ij는 NIL이고, 그렇지 않다면 𝝅_ij는 i로부터의 어떤 최단 경로에서 j의 predecessor이다. Chapter 24의 predecessor subgraph G_pi가 주어진 source vertex에 대해 최단 경로 트리인 것처럼, 𝚷행렬의 i번째 행으로부터 만들어지는 부분 그래프는 root i가 있는 최단 경로 트리여야 한다. V에있는 각 정점 i에 대해, 우리는 G의 predecessor subgraph를 G_pi,i = (V_pi,i , E_pi,i)로  정의한다. 거기에서


이고



만약 G_pi,i는 최단 경로 트리라면, Chapter 22의 PRINT-PATH procedure의 수정된 버전인  다음의 procedure는 vertex i에서 vertex j로의 최단 경로를 출력한다

PRINT-ALL-PAIRS-SHORTEST-PATH(PI, i, j)
1 if i == j
2      print i
3 else if pi_ij == NIL
4      print "no path from" i "to" j "exists"
5 else PRINT-ALL-PAIRS-SHORTEST-PATH(PI, i, pi_ij)
6      print j

이 챕터에서 모든 쌍의 알고리즘의 필수적인 특징을 강조하기 위해서, 우리는 Chapter 24에서 predecessor subgraphs로 광범위 하게 다루었었던 만큼, predecessor 행렬의 생성과 특징을 다루지 않을 것이다. 몇 가지 exercises들은 그 basics를 다룬다.

Chapter outline
Section 25.1은 모든 쌍의 최다 ㄴ경로 문제를 해결하기 위해 행렬 곱을 기반으로 dynammic-programming algorith을 보여준다. "repeated squaring" 기법을 사용하여, 우리는 O(V^3 lgV)의 작동시간을 얻을 수 있다. Section 25.2는 또 다른 DP 알고리즘인 Floyd-Warshall 알고리즘을 주고, 이것은 O(V^3)의 시간이 걸린다. Section 25.2는 또한 방향이 있는 그래프의 transitive closure를 찾는 문제를 다룬다. 그 문제는 모든 쌍의 최단 경로 문제와 관련이 있다. 마지막으로, Section 25.3은 Johnson의 알고리즘을 보여주고, 그것은 모든 최단 경로 문제를 O(V^2lgV + VE) 시간 안에 해결하고, large, sparse graphs에 대한 좋은선택이 된다.

나아가기전에, 우리는 인접 행렬 표기에 대해 몇 가지 conventions를 만들 필요가 있다. 첫 째로, 우리는 일반적으로 그 입력 그래프 G = (V,E)가 n개의 정점을 가진다고 가정한다. n = |V|가 된다. 둘 째로, 우리는 대문자로 행렬을 표현하는 convention을사용할 것이다, W, L, or D같은, 그리고 밑에 표기되는 소문자로 그것들의 각각의 원소들을 표기한다, w_ij, l_ij, or d_ij 같이. 몇 행렬들은 괄호가 쳐져잇고 위에 숫자가 표시되는데, L^(m) = (l^(m)_ij) or D^(m) =  (d^(m)_ij) 같이, 이것은 반복을 나타내기 위해서이다. 마지막으로, 주어진 n X n 행렬 A에 대해, 우리는 n의 값이 A.row의 attribute에 저장되어있다고 가정할 것이다.

25.1 Shortest paths and matrix multiplication
이 섹션은 방향이 있는 그래프 G = (V, E)에서 모든 쌍의 최단 경로 문제에 대해 DP 알고리즘을 보여준다. DP의 각각의 주요한 loop는 행렬 곱과 매우 유사한 연산을 불러올것인데, 그 알고리즘이 반복된 행렬 곱처럼 보이게 하기 위해서이다. 우리는 모뜬 상의 최단 경로 문제에 대해 O(V^4)의 시간 알고리즘을 개발하여 시작할 것이고, 그것의 작동 시간을
O(V^3 lgV)로 개선할 것이다.

진행하기 전에, 우리가 간단하게 DP 알고리즘을 개발하는 것에 대해 Chapter 15에서 주어진 단계의 개요를 말해보자.

1. 최적의 해결책에 대한 structure를 특징화해라.
2. 재귀적으로 최적의 솔루션의 값을 정의해라.
3. bottom-up 방식으로 최적의 해결책의 값을 계산해라.

우리는 exercises를 위해 그 네 번째 단계를 보류한다 - 연산된 information으로부터 최적의 솔루션을 구성하는 것.

The structure of a shortest path

우리는 최적의 솔루션의 structure를 특징화 하여 시작한다. graph G = (V, E)에서 모든 쌍의 최단 경로에 대해, 우리는 (Lemma 24.1) 최단 경로의 모든 하위 경로가 최단 경로라는 것을 입증했다. 우리가 인접 행렬 W = (w_ij)로 그 그래프를 나타낸다고 가정하자. 정점 i에서 j로 가는 최단 경로 p를 고려하고, p가 최대 m개의 간선들을 포함한다고 가정하자. 음의 가중치 사이클이 없다고 가정하여, m은 유한이다. 만약 i = j라면, 그러면 p는 0의 가중치를 가지고, 어떠한 간선도 없다. 만약 정점들 i와 j가 구분된다면, 그러면 우리는 path p를 

i ->(p') k -> j로 분해할 수 있고, path p'는 이제 최대 m - 1개의 간선들을 포함한다. Lemma 24.1에 의해, p'는 i에서 k로 가는 최단 경로이고, 그래서 &(i, j) = &(i,k) + w_kj가 된다.

A recursive solution to the all-pairs shortest-paths problem

이제, l^(m)_ij를 최대 m개의 간선들을 포함하는 정점 i에서 j로 가는 어떤 경로의 최소 가중치라고 하자. m = 0일 때, 간선이 없는 i에서 j로 가는 최단 경로가 있다, 만약 i = j라면. 따라서,

m >= 1에 대해, 우리는 l^(m)_ij를 (최대 m - 1개의 간선들로 구성된 i에서 j로 가는 최단 경로의 가중치인) l^(m-1)_ij의 최소값으로서 연산하고, 최대 m개의 간선들로 구성된 i에서 j로 가는 경로의 최소 가중치를 연산하고, j의 모든 가능한 predecessors k를 보아서 어어진다. 따라서, 우리는 재귀적으로 다음을 정의한다

그 후자 식은 모든 j에 대해 wjj = 0이기 때문에 따른다.

실제 최단 경로 가중치 &(i, j)는 무엇인가? 만약 그 그래프가 어떠한 음의 가중치 사이클을 포함하고 있지 않다면, 그러면 &(i, j) < infinity인 정점 i와 j의 모든 쌍에 대해, 간단하고 따라서 최대 n - 1개의 간선들을 포함하는 i에서 j로가는 최단 경로가 있다. n - 1개의 이상의 간선을 가진 정점 i에서 j로가는 한 경로는 i에서 j로 가는 최단 경로보다 더 낮은 가중치를 가질 수 없다. 그 실제 최단 경로 가중치는 그러므로 다음과 같이 주어진다

Computing the shortest-path weights bottom up

우리의 입력 행렬 W = (w_ij)를 취하여, 우리는 일련의 행렬 L^(1), L^(2), ... , L^(n-1)를 연산할 수 있고, m = 1,2,..., n-1에 대해, 우리는 L^(m) = (ㅣ^(m)_ij)를 갖게 된다. 그 최종 행렬 L^(n-1)은 실제 최단 경로 가중치를 포함한다. V에 있는 모든 정점들 i와 j에대해 l^(1)_ij = w_ij인 것을관찰해라, 그래서 L^(1) = W 이다.

그 알고리즘의 중심부는 다음의 procedure인데, 주어진 행렬 L^(m-1)과 W에 대해, 행렬 L^(m)을 반환한다. 즉, 그것은 지금 까지 연산된 최단 경로를 간선 한 개 더로 확장한다.

EXTEND-SHORTEST-PATHS(L, W)
1 n = L.rows
2 let L' = (l'_ij) be a new n x n matrix
3 for i = 1 to n
4     for j = 1 to n
5        l'_ij = infinity
6        for k = 1 to n
7             l'_ij = min(l'_ij, l_ik + w_ki)
8 return L'

그 절차는 matrix L' = (l'_ij)를 연산하는데,그것은 마지막에 반환된다. 그것은 방정식25.2를연산하여 그렇게한다, 모든 i와 j에 대해. L^(m-1)에 대해 L을사용하고, L^(m)에 대해 L'를사용해서. 그것의 작동시간은 세 번 중첩된 loops에 의해 O(n^3)이다.

이제 우리는 행렬곱과의 관계를 볼 수 있다. 우리가 두 개의 n X n 행렬 A와 B의 행렬 곱 C = A * B를 연산한다고 가정하자. 그러고나서, i , j = 1,2, ... , n에대해,우리는 다음을 연산한다



만약 우리가 치환을 한다면 방정식 (25.4)를 얻게 된다
l^(m-1) -> a,
       w -> b
l^(m) -> c
min -> +,
   + -> *

따라서, 만약 우리가 EXTEND-SHORTEST-PATHS에 이러한 변화를 만든다면, 또한 infinity를 0으로 바꾼다면, 우리는 section 4.2에서 보았던 square matrices를 곱하는 것에 O(n^3)-time procedure를 얻게 된다:

SQUARE-MATRIX-MULTIPLY(A,B)
1 n = A.rows
2 let C be a new n x n matrix
3 for i = 1 to n
4     for j = 1 to n
5         c_ij = 0
6         for k = 1 to n
7             c_ij = c_ij + a_ik * b_kj
8 return C

모든 쌍의 최단 경로 문제로 돌아가서, 우리는 shortest paths를 edge마다 확장하여 최단 경로 가중치를 계산한다. EXTEND_SHORTEST_PATHS(A,B)에 의해 반환된 A * B가 행렬"곱"을 나타낸다고 하여, 우리는 n - 1행렬의 시퀀스를 계산한다

L^(1) = L(0) * W = W,
L^(2) = L(1) * W = W^2,
...

L^(n-1) = L^(n-2) * W = W^(n-1).

우리가 위에서 주장했듯이, 그 행렬 L^(n-1) = W^(n-1)은 최단 경로 가중치들을 포함한다. 다음의 procedure는 이 시퀀스를 O(n^4) 시간안에 연산한다.

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)
1 n = W.rows
2 L^(1) = W
3 for m = 2 to n - 1
4    let L^(m) be a new n X n matrix
5    L^(m) = EXTEND-SHORTEST-PATHS(L^(m-1), W)
6 return L^(n-1)

그림 25.1은 SLOW-ALL-PAIRS-SHORTEST-PATHS 절차에 의해 연산된 한 그래프와 행렬 L^(m)을 보여준다.

Improving the running time
그러나 우리의 목적은 모든 L^(m) 행렬들을 연산하는 것이 아니다: 우리는 오직 L^(n-1) 행렬에만 관심이있다. 음의 가중치 사이클이 없이, 방정식 (25.3)은 모든 정수 m >= n -1에 대해 L^(m) = L^(n-1) 인 것을 암시한다는 것을 기억해라. 전통적인 행렬 곱이 결합법칙이 되기 때문에, EXTEND-SHORTEST-PATHS 절차에 의해 행렬곱이 정의된다 (Exercise 25.1-4). 그러므로, 우리는 L^(n-1)를 다음의 시퀀스로 연산하여 오직 ceil(lg(n-1))의 행렬곱으로 연산할 수 있다.

L^(1) = W,
L^(2) = W^2 = W * W,
L^(3) = W^4 = W^2 * W^2,
...

L^(2ceil(lg(n-1))) = W^(2ceil(lg(n-1))) = W^(2ceil(lg(n-1)) - 1) * W^(2ceil(lg(n-1)) - 1)

2^(ceil(lg(n-1))) >= n-1이기 때문에 최종 곱 L^(2(ceil(lg(n-1))))은 L^(n-1) 동일하다.

다음의 procedure는 이 repeated squaring의 기법을 사용해서 행렬의 위의 시퀀스를 계산한다.

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
1 n = W.rows
2 L^(1) = W
3 m = 1
4 while m < n - 1
5      let L^(2m) be a new n x n matrix
6      L^(2m) = EXTEND-SHORTEST-PATHS(L^(m), L^(m))
7      m = 2m
8 return L^(m)

lines 4-7의 while loop의 매 반복에서, 우리는 L^(2m) = (L^(m))^2 를 계산한다, m = 1에서 시작하여서. 각 반복의 끝에서, 우리는 m의 값을 두 배 한다. 그 최종 iteration은 L^(n-1)을 연산한다, 실제로 n - 1 <= 2m < 2n - 2에 대해 L^(2m)을 연산하여서. 방정식 (25.3)에 의해, L^(2m) = L^(n-1)이 된다. line 4에서 그 테스트가 수행되는 다음 번에, m음 두배 가 되었고, m은 두배가 되어있어서, 그래서 이제 m >= n - 1이다. 그 테스트는 실패하고, 그래서 그 procedure는 그것이 연산한 마지막 행렬을 반환한다.

ceil(lg(n-1)) 행렬곱 각각은 O(n^3) 시간이 걸리기 때문에, FASTER-ALL-PAIRS-SHORTEST-PATHS는 O(n^3lgn) 시간이 걸린다. 그 코드가 tight한 것을 관찰해라, 어떠한 elaborate data structures를 포함하는 것 없이. 그리고 O-notation에 숨겨저 있는 상수는 그러므로 작다.

25.2 The Floyd-Warshall algorithm
이 섹션에서, 우리는 유향 그래프 G = (V, E)에서 모든 쌍의 최단 경로 문제를 해결하기 위해 다른 DP 공식을 사용할 것이다. Floyd-Warshall algorithm으로 알려진 그 최조 ㅇ알고리즘은 O(V^3) 시간에 작동한다. 이전 처럼, 음의 가중치 간선들을 존재할지 모르지만, 우리는 어떠한 음의 가중치 사이클이 없다고 가정한다. Section 25.1에서 처럼, 우리는 그 알고리즘을 개발하기 위해 DP process를 따른다. 최종 알고리즘을 공부한 후에, 우리는 유항 그래프의 transitive closure를 발견하는 유사한 방법을 보여준다.

The structure of a shortest path
플로이드-와셜 알고리즘에서, 우리는 우리가 Section 25.1에서 특징화했던 방식과는 다르게 최단 경로의 구조를 특징화한다. 플로이드와셜 알고리즘은 최단 경로의 중간 정점들을 고려하는데, 거기에서 간단한 경로 p = <v1, v2, ...., vl>의 한 intermidate 정점은 v1 또는 vl이 아닌 어떤 다른 p의 저엊미다, 즉, 집합 {v2, v3, ... , vl-1}에 있는 어떤 정점이다.

그 플로이드와셜 알고리즘은 다음의 관찰에 의존한다. G의 정점들이 V = {1,2,...,n}이라는 가정하에, 우리가 어떤 k에 대해 정점들의 {1,2,...,k}의 부분집합을 고려해보자. V안에 있는 정점들 i,j의 어떤 상에 대해, i에서 j로 가는 모든 경로들을 고려해보자, 거기에서 intermediate vertices들은 모두 {1, 2,...,k}로부터 끌어와지고, p가 그것들 사이에 있는 최소 가중치 경로라고 하자 (Path p is simple.) 그 플로이드 와셜 알고리즘은 경로 p와 집합 {1,2,..., k - 1}에 있는 모든 중간 정점을 가진 i에서 j로 가는 최단 경로 사이의 관계를 이용한다. 그 관계는 k가 path p의 intermediate vertex인지 아닌지에 의존한다.

• 만약 k가 경로 p의 intermediate vertex가 아니라면, 그러면 경로 p의 모든 intermediate vertices들은 {1,2,.., k - 1}안에 있다. 따라서, {1,2,...,k-1} 집합 안에 있는 모든 intermediate vertices가 있는 정점 i에서 j로 가는 최단 경로는 또한 {1,2,...,k} 집합에 있는 모든 intermediate vertices가 있는 i에서 j로 가는 최단 경로이다.
• 만약 k가 path p의 intermediate vertex라면, 우리는 p를 i ->(p1) k ->(p2) j로 분해한다. 그림 25.3이 보여주듯이. Lemma 24.1에 의해, p1은 {1,2,...,k} 집합에서 모든 intermediate vertices를 가진 i에서 k로 가는 최단 경로이다. 사실, 우리는 다소 더 강한 주장을 할 수 있다. vertex k가 path p1의 intermediate vertex가 아니기 때문에, p1의 모든 intermediate vertices는 {1,2,...,k-1}안에 있다. 그러므로 p1은 집합{1,2,...,k-1}에서 모든 중간 정점들을 가진 i에서 k로 가는 최단 경로이다. 유사하게, p2는 집합 {1,2,.,,,k-1}에서 모든 중간 점점들을 가진 k에서 j로 가는 최단 경로이다.

A recursive solution to the all-pairs shortest-paths problem

위의 관찰을 기반으로, 우리는 Section 25.1의 것과 다른 최단 경로 측정의 재귀 공식을 정의한다. d^(k)_ij가 모든 중간 정점들이 집합 {1,2,...,k}에 있는 정점 i에서 j로 가는 최단 경로의 가중치라고 하자. k가 0일 때, 어떠한 중간 정점이 0보다 더 높게 순서를 받지 않은 정점 i에서 j로 가는 한 경로는 어떠한 중간정점도 가지고 있지 않다. 그러한 경로는 최대 한 간서을 가지고 있고, 그러므로 d^(0)_ij = w_ij이다. 위의 이야기에 따라서, 우리는 d^(k)_ij를 재귀적으로 다음과 같이 정의한다.

어떤 경로에 대해, 모든 중간 정점들은 {1,2,...,n} 집합 안에 있기 때문에, 행렬 D^(n) = (d^(n)_ij)는 최종 답을 준다: d^(n)_ij = &(i,j) for all i, j in V.

Computing the shortest-path weights bottom up

재귀를 기반으로 (25.5), 우리는 k값의 증가하는 순서로 d^(k)_ij의 값을 연산하기 위해 다음의 bottom-up procedure를 사용할 수 있다. 그것의 입력은 n X n 행렬 W가 방정식 (25.1)에서 처럼 정의되어 있다. 그 procedure는 최단 경로 가중치의 행렬 D^(n)은 반환한다.

FLOYD-WARSHALL(W)
1 n = W.rows
2 D^(0) = W
3 for k = 1 to n
4      let D^(k) = (d^(k)_ij) be a new n X n matrix
5       for i = 1 to n
6           for j = 1 to n
7                d^(k)_ij = min(d^(k-1)_ij, d^(k-1)_ik + d^(k-1)_kj)
8 return D^(n)

그림 25.4는 그림 25.1에서 그래프에 대해 Floyd-Warshall 알고리즘에 의해 연산된 행렬 D^(k)를 보여준다.

플로이드 와셜 알고리즘의 작동시간은 lines 3-7의 세 번 중첩된 for loops에 의해 결정된다. Section 25.1에서 최종 알고리즘에서 처럼, 그 코드는 tight하다, 어떠한 elaborate data structures가 없이, 그래서 그 O-notation에 숨겨진 상수는 작다. 따라서, 플로이드 와셜 알고리즘은 심지어 적당한 크기의 입력 그래프에 대해 실용적이다.r

Constructing a shortest path
플로이드 와셜 알고리즘에서 최단 경로들을 구성하는 다양한 다른 방법들이 있다. 한 방법은 최단 경로 가중치의 행렬 D를 연산하고, 그러고나서 D 행렬로부터 predecessor matrix PI를 구성하는 것이다. Exercise 25.1-6은 너에게 이 방법을 구현하라고 요구한다, 그것이 O(n^3) 시간안에 작동하도록. predecessor matrix PI가 주어진다면, PRINT-ALL-PAIRS-SHORTEST-PATH procedure는 주어진 최단 경로에 있는 정점들을 출력할 것이다.

대안적으로, 우리는 그 알고리즘이 행렬 D^(k)를 연산하는 동안 predecessor matrix PI를 연산할 수 있다. 구체적으로, 우리는 PI^(0), PI^(1), ..., PI^(n) 행렬들의 시퀀스를 연산한다, 거기에서 PI = PI^(n)이고, 우리는 pi^(k)_ij를  집합 {1,2,...,k}에 있는 모든 중간 정점들과 함께 정점 i에서 출발하는 최단 경로에서 정점 j의 predecessor로서 정읭한다.

우리는 pi^(k)_ij의 재귀 공식을 줄 수 있다. k = 0일 떄, i에서 j로 가는 최단 경로는 어떠한 중간 정점을 가지고 있지 않다. 따라서,



k >= 1에 대해, 만약 우리가 i -> k -> j의 경로를 가진다면, k !=j인 곳에서, 그러면 우리가 선택한 j의 predecessor는 우리가 집합 {1,2,...,,k - 1}에 있는 모든 중간 정점을 가진 k로부터의 최단 경로에서 선택한 j의 predecessor와 같다. 만약 그렇지 않다면, 우리는 집합
{1,2,...,k - 1}에 있는 모든 중간 정점들이 있는 i에서부터의 최단 경로에서 선택한 j의 같은 predecessor를 선택한다. 공식적으로 k >= 1에 대해



우리는 PI^(k) 행렬 연산의 통합을 FLOYD-WARSHALL procedure에 넣는 것을 Exercise 25.2-3에 남긴다. 그림 25.4는 그림 25.1의 그래프에 대해 최종 알고리즘이 연산하는 PI^(k) 행렬의 sequence를 보여준다. 그 exercise는 또한 predecessor subgraph_pi,i 가 root i를 가지는 최단 경로 트리인 것을 제공하는 좀 더 어려운 과제를 요구한다. Exercise 25.2-7은 최단 경로를 재구성하는 또 다른 방법을 요구한다.

Transitive closure of a directed graph
정점 집합 V = {1,2,...,n}가 있는 유향 그래프 G = (V,E)가 주어진다면, 우리는 G가 V에 있는 모든 정점에 있는 상 i, j에 대해 i에서 j로 가는 한 경로를 포함하는지를 결정하길 원한다. 우리는 G의 transitive closure를 G* = (V, E*)라고 정의하는데, 여기에서

E* = {(i,j) : there is a path from vertex i to vertex j in G}.

O(n^3) 시간안에 한 그래프의 transitive closure를 연산하는 한 방식은 1의 한 가중치를 E의 각 edge에 할당하고, Floyd-Warshall algorithm을 작동시키는 것이다. 만약 정점 i에서 j로 가는 한 경로가 있다면, 우리는 d_ij < n을 얻게된다. 만약 그렇지 않다면, 우리는 d_ij = infinity를 얻는다.

실제로 시간과 공간을 절약할 수 있는 G의 transitive closure를 O(n^3)안에 연산하는 또 다른, 유사한 방법이 있다. 이 방법은 논리적 연산 OR과 AND를 플로이드 와셜 알고리즘에서 수학 연산 min과 +로 대체한다. i,j,k = 1,2,....,n에 대해, 우리는 t^(k)_ij가 1이 되도록 정의한다, 만약 그래프 G에서 i에서 j로가는 한 경로가 존재한다면, 집합 {1,2,...,k}안에 모든 중간 정점들과 함께, 그리고 그렇지 않다면 0으로 저으이한다. 우리는 edge(i,j)를 E*에 넣어서
G* = (V, E*)를 구성하는데, t^(n)_ij = 1이여야만 한다. t^(k)_ij의 재귀 정의는, 재귀(25.5)과 유사한,



그리고 k >= 1에 대해



플로이드 와셜 알고리즘에서 처럼, 우리는 T^(k) = (t^(k)_ij) 행렬을 증가하는 k의 순서로 연산한다.

TRANSITIVE-CLOSURE(G)
1  n = |G.V|
2  let T^(0) = (t^(0)_ij) be a new n X n matrix
3  for i = 1 to n
4     for j = 1 to n
5          if i == j or (i,j) in G.E
6              t^(0)_ij = 1
7          else t^(0)_ij = 0
8  for k = 1 to n
9        let T^(k) = (t^(k)_ij) be a new n X n matrix
10       for i = 1 to n
11           for j = 1 to n
12              t^(k)_ij = t^(k-1)_ij | (t^(k-1)_ik & t^(k-1)_kj)
13  return T^(n)

그림 25.5는 샘플 그래프에서 TRANSITIVE-CLOSURE procedure에 의해 연산되는 행렬 T^(k)를 보여준다. 플로이드 와셜 앙ㄹ고리즘 처럼, 그 TRANSITIVE-CLOSURE procedure는 O(n^3) 시간에 작동한다. 몇 컴퓨터에서, 그러나, 단일 비트 값에 대한 논리적 연산은 정수 데이터 words에 대한 수적 연산보다 더 빠르게 실행된다. 게다가, 그 직접적인 transitive-closure algorithm은 오직 정수값보다 boolean values만을 사용하기 때문에, 그것의 공간 요구사항은 컴퓨터 저장공간의 한 word의 크기에 대응하는 요소에 의해 플로이드 와셜 알고리즘 보다 더 작다.