25. All-Pairs Shortest Paths

그래프 내 모든 정점 쌍간 최단 경로를 구할 수는 없을까? 다익스트라나 벨만-포드로 O(V^{2} \lg V + VE), O(V^{2}E) 시간에 할 수는 있지만, 더 좋은 방법을 알아보자. 여기서 음의 가중치 간선은 허용하지만, 음의 가중치 순환은 허용하지 않는다. 이 때에는 인접 리스트 대신 인접 행렬을 사용하자. 또한, 전임자 행렬 \Pi = (\pi_{ij})도 구성해야 하는데, 이는 i = j거나 i에서 j로의 경로가 없으면 NIL이고 아니면 i로부터 어떠한 최단 경로에서 j의 전임자이다. \Pi의 i번째 행으로부터 유도되는 부분그래프는 i로부터의 최단 경로 트리가 된다. 이로부터 전임자 부분그래프도 정의된다. 전임자 부분그래프가 최단 경로 트리라면 i에서 j로의 최단 경로는 다음과 같이 출력된다.

PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, j)
if i == j
    print i
else if π_ij == NIL
    print "no path from" i "to" j "exists"
else
    PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, π_ij)
    print j

25.1. Shortest paths and matrix multiplication

먼저 방향그래프에서 모든 쌍의 최단 경로를 동적 계획법으로 구해보자. \Theta(V^{4}) 시간으로부터 시작해서 \Theta(V^{3} \lg V) 알고리즘을 알아본다.

The structure of a shortest path

모든 최단 경로의 부분경로는 최단 경로이다. \delta(i, j) = \delta(i, k) + w_{kj}이다.

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

이제 l_{ij, m}을 최대 m개의 간선으로 이루어진 i에서 j로의 경로의 최소값이라 할 때, l_{ij, m} = \min_{1 \leq k \leq n}(l_{ik, m - 1} +w_{kj})이 성립한다. \delta(i, j) = l_{ij, n - 1}이다.

Computing the shortest-path weights bottom up

위의 식을 알고리즘으로 옮기면 최단 경로를 하나씩 확장해나가는 알고리즘은 다음과 같다.

EXTEND-SHORTEST-PATHS(L, W)
n = L.rows
Let L' = (l'_ij) be a new n x n matrix
for i = 1 to n
    for j = 1 to n
        l'_ij = ∞
        for k = 1 to n
            l'_ij = min(l'_ij, l_ik + w_kj)
return L'

이를 다음의 행렬곱 알고리즘과 연관시켜 보자.

SQUARE-MATRIX-MULTIPLY(A, B)
n = A.rows
Let C be a new n x n matrix
for i = 1 to n
    for j = 1 to n
        c_ij = 0
        for k = 1 to n
            c_ij += a_ik * b_kj
return C

이로부터 다음을 얻는다.

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)
n = W.rows
L_1 = W
for m = 2 to n - 1
    let L_m be a new n x n matrix
    L_m = EXTENDED-SHORTEST-PATHS(L_(m-1), W)
return L_(n-1)

수행 시간은 \Theta(n^{4})이다.

Improving the running time

반복 제곱법으로 수행 시간을 \Theta(n^{3} \lg n)으로 줄일 수 있다.

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
n = W.rows
L_1 = W
m = 1
while m < n - 1
    let L_2m be a new n x n matrix
    L_2m = EXTENDED-SHORTEST-PATHS(L_m, L_m)
    m = 2m
return L_m

25.2 The Floyd-Warshall algorithm

플로이드-와샬 알고리즘으로 \Theta(n^{3}) 시간에 모든 쌍 최단 경로 문제를 풀 수 있다.

The structure of a shortest path

플로이드-와샬 알고리즘은 최단 경로의 중간 정점을 고려하며, i에서 j로의 경로의 모든 중간 정점이 \{1, \cdots, k\}에 있을 때 이들 중 최단 경로를 p라고 할 때 다음의 관계를 이용한다.

  • 어떤 k가 경로 p의 중간 정점이 아니라면, i에서 j로의 경로 중 중간 정점이 \{1, \cdots, k - 1\}에 있는 최단 경로는 i에서 j로의 최단 경로가 된다.
  • 어떤 k가 경로 p의 중간 정점이라면, 경로 p는 i에서 k로의 최단 경로와 k에서 j로의 최단 경로로 분해되고, 이 두 최단 경로는 중간 정점이 \{1, \cdots, k - 1\}로 구성된다.

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

위의 관찰로부터, d_{ij, k}를 i에서 j로의 경로 중 중간 정점이 \{1, \cdots, k\}에 있는 경로들 중 최단 경로의 가중치라고 하면, 다음이 성립한다.

d_{ij, k} = w_{ij} if k = 0, \min(d_{ij, k - 1}, d_{ik, k - 1} + d_{kj, k - 1}) if k \geq 1. 그리고 d_{ij, n} = \delta(i, j)이다.

Computing the shortest-path weights bottom up

이로부터 다음의 플로이드-와샬 알고리즘을 얻는다.

FLOYD-WARSHALL(W)
n = W.rows
D_0 = W
for k = 1 to n
    let D_k = d_{ij, k} be a new n x n matrix
    for i = 1 to n
        for j = 1 to n
            d_{ij, k} = min(d_{ij, k}, d_{ik, k - 1} + d_{kj, k - 1})
return D_n

수행 시간은 \Theta(n^{3})이다.

Constructing a shortest path

최단 경로를 구성하는 방법은 전임자 행렬을 만들어 PRINT-ALL-PAIRS-SHORTEST-PATH를 수행하는 방법이 있다. O(n^{3})이다. 또 다른 방법도 있다.

Transitive closure of a directed graph

방향그래프 G의 추이적 폐포는 정점 i에서 j로의 경로가 G 내에 있는 경우 간선 (i, j)를 추가한 그래프로 정의된다. 플로이드-와샬 알고리즘을 써서 \Theta(n^{3})에 구할 수 있다. 또는 다음과 같이 구할 수도 있다.

TRANSITIVE-CLOSURE(G)
n = |G.V|
let T_0 = t_{ij, 0} be a new n x n matrix
for i = 1 to n
    for j = 1 to n
        if i == j or (i, j) ∈ G.E
            t_{ij, 0} = 1
        else
            t_{ij, 1} = 0
for k = 1 to n
    let T_k = t_{ij, k} be a new n x n matrix
    for i = 1 to n
        for j = 1 to n
            t_{ij, k} = t_{ij, k - 1} ∨ (t_{ik, k - 1} ∧ t_{kj, k - 1})
return T_n

25.3. Johnson’s algorithm for sparse graphs

존슨의 알고리즘은 모든 쌍간 최단 경로를 O(V^{2} \lg V + VE) 시간에 구한다. 희소 그래프일 경우 플로이드-와샬보다 빠르다. 이는 O(VE)재가중 기법을 사용한다. 다시 매겨진 가중치는 다음 특성을 만족해야 한다.

  • 모든 정점 u, v \in V에 대해 최단 경로를 바꾸지 않는다.
  • 가중치가 음이 아니다.

Preserving shortest paths by reweighting

위의 특성을 만족시키는 재가중을 알아보자.

Lemma. (Reweighting does not change shortest paths) h : V \to \mathbb{R}에 대해 \hat{w}(u, v) = w(u, v) + h(u) - h(v)라 하면 이는 최단 경로를 바꾸지 않는다.

Producing nonnegative weights by reweighting

원 그래프와 별개의 출발점 s를 정의하고 h(v) = \delta(s, v)일 때 위의 재가중을 사용하면 가중치는 음이 아니게 된다.

Computing all-pairs shortest paths

위로부터 얻어지는 존슨의 알고리즘은 다음과 같다.

JOHNSON(S, w)
compute G', where G'.V = G.V ∪ {s}, G'.E = G.E ∪ {(s, v) : v ∈ G.V}, and w(s, v) = 0 for all v ∈ G.V
if BELLMAN-FORD(G', w, s) == FALSE
    print "the input graph contains a negative-weight cycle"
else
    for each vertex v ∈ G'.V
        set h(v) to the value of δ(s, v) computed by the Bellman-Ford algorithm
    for each edge (u, v) ∈ G'.E
        w'(u, v) = w(u, v) + h(u) - h(v)
    let D = d_uv be a new n x n matrix
    for each vertex u ∈ G.V
        run DIJKSTRA(G, w', v) to compute δ'(u, v) for all v ∈ G.V
        for each vertex v ∈ G.V
            d_uv = δ'(u, v) + h(v) - h(u)
    return D

이는 피보나치 힙을 썼을 때 O(V^{2} \lg V + VE), 이진 힙을 썼을 때 O(VE \lg V)가 된다. 그래프가 희소하다면 둘 모두 플로이드-와샬보다 빠르다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중