24. Single-Source Shortest Paths

최단 경로 문제에서는 가중치가 부여된 방향그래프에 대해서 최단 경로 가중치를 가진 최단경로를 찾는 문제이다. 넓이 우선 탐색은 가중치가 없는 비방향그래프에 대해서 최단 경로를 찾는다.

Variants

이 장에서는 출발점이 하나인 단일 출발점 최단 경로 문제를 알아본다. 이는 다음에 응용될 수 있다.

  • 도착점이 하나인 단일 도착점 최단 경로 문제.
  • 단일 쌍 최단 경로 문제.
  • 모든 쌍 최단 경로 문제.

Optimal substructure of a shortest path

다음이 성립한다.

Lemma. (Subpaths of shortest paths are shortest paths) 가중치 w가 주어진 방향그래프 G = (V, E)에 대해 최단 경로의 부분경로는 역시 최단 경로이다.

Negative-weight edges

G = (V, E)가 출발점 s로부터 도달 가능한 음수 가중치 순환을 가지지 않는 한 최단 경로는 잘 정의된다. 음수 가중치 순환을 가진 경우에는 s로부터의 최단 경로는 -\infty가 된다. 다익스트라 알고리즘은 모든 가중치가 음이 아님을 가정한다. 벨만-포드 알고리즘은 음수 가중치 순환만 없으면 된다. 있다면 이를 감지 가능하다.

Cycles

최단 경로는 음수 가중치 순환도 양수 가중치 순환도 가질 수 없다. 0의 가중치 순환은 일반성을 잃지 않고 없앨 수 있다. 그러므로 최단 경로는 최대 V – 1개의 간선으로 제한할 수 있다.

Representing shortest paths

최단 경로를 나타내기 위해서, 각 정점마다 전임점 v.\pi를 둔다. 이 전임점으로 전임점 부분그래프를 만들면 이는 종료 시 최단 경로 트리가 된다. 이는 다음의 특성을 갖는다.

  1. V^{\prime}은 s로부터 도달 가능한 정점들이다.
  2. G^{\prime}은 s를 루트로 하는 트리이다.
  3. 모든 v \in V^{\prime}에 대해, 유일 경로 s \to v \in G^{\prime}는 최단 경로이다.

Relaxation

이 장의 알고리즘은 완화 법을 사용한다. 각 정점 v \in V에 대해, s로부터 v로의 최단 경로의 상한인 최단 경로 추정 v.d를 두는데, 이는 다음과 같이 초기화한다.

INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex v ∈ G.V
    v.d = ∞
    v.π = NIL
s.d = 0

간선 (u, v)에 대한 완화는 v를 통과하는 u로부터의 최단 경로를 고려함에 따라 v.d와 v.π를 업데이트하는 것이다.

RELAX(u, v, w)
if v.d > u.d + w(u, v)
    v.d = u.d + w(u, v)
    v.π = u

이 장의 알고리즘은 간선 각각에 대해 완화를 얼마나 하냐에 따라 달라진다. 다익스트라 알고리즘과 비순환 방향그래프에 대한 최단 경로 알고리즘은 각 간선에 대한 완화를 1번만 수행한다. 벨만-포드 알고리즘은 V – 1번 수행한다.

Properties of shortest paths and relaxation

최단 경로와 완화에 대해서는 다음 특성들이 있다.

  • 삼각 부등식. 모든 간선 (u, v) \in E에 대해, \delta(s, v) \leq \delta(s, u) + w(u, v).
  • 상한 특성. 항상 v.d \geq \delta(s, v)이며, v.d = \delta(s, v)가 되면 그 값은 바뀌지 않음.
  • 경로 없음 특성. s에서 v로의 경로가 없다면 v.d = \delta(s, v) = \infty이다.
  • 수렴 특성. s \to u \to v가 u, v에 대해 최단 경로이고 (u, v)에 대한 완화 전 u.d = \delta(s, u)가 된다면, 항상 v.d = \delta(s, v)이다.
  • 경로 완화 특성. 최단 경로 내의 간선들을 완화한다면, 최단 경로 끝점 v_{k}에 대해 v_{k}.d = \delta(s, v_{k})이다.
  • 전임자-부분그래프 특성. 모든 v에 대해 v.d = \delta(s, v)가 된다면, 전임자 부분그래프는 s를 루트로 하는 최단 경로 그래프이다.

Chapter outline

이 장에서는 여러 단일 출발점 최단 경로 알고리즘을 알아본다.

24.1. The Bellman-Ford algorithm

벨만-포드 알고리즘은 간선 가중치가 음일 때에도 단일 출발점 최단 경로를 찾아낸다. 이는 다음과 같다.

BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
for i = 1 to |G.V| - 1
    for each edge (u, v) ∈ G.E
        RELAX(u, v, w)
for each edge (u, v) ∈ G.E
    if v.d > u.d + w(u, v)
       return FALSE
return TRUE

수행 시간은 O(VE)이다. 이 알고리즘에 대한 증명은 다음과 같다.

Lemma. G = (V, E)가 가중치가 부여된 방향그래프이며 s로부터 도달 가능한 음의 가중치 순환이 없다고 할 때, BELLMAN-FORD의 1번째 for 루프를 돌고 나면 s로부터 도달 가능한 모든 정점 v에 대해 v.d = \delta(s, v)이다.

Corollary. G = (V, E)가 가중치가 부여된 방향그래프이며 s로부터 도달 가능한 음의 가중치 순환이 없다고 할 때, 각 정점 v에 대해, s로부터 v로의 최단 경로가 존재할 조건은 BELLMAN-FORD가 종료되었을 때 v.d < \infty가 됨과 동치이다.

Theorem. (Correctness of the Bellman-Ford algorithm) G = (V, E)가 가중치가 부여된 방향그래프일 때, 시작점 s가 있으면, s로부터 도달 가능한 음의 가중치 순환이 없다면 이 알고리즘은 TRUE를 리턴하고, v.d = \delta(s, v)이며, 전임자 부분그래프는 s를 루트로 하는 최단 경로 트리이다. s로부터 도달 가능한 음의 가중치 순환이 있다면, 알고리즘은 FALSE를 리턴한다.

24.2. Single-source shortest paths in directed acyclic graphs.

가중치가 부여된 방향 비순환그래프의 경우에서는 위상 정렬로 \Theta(V + E) 시간에 최단 경로를 구할 수 있다. 또한, 이 때 최단 경로는 항상 잘 정의된다. 음의 가중치 순환이 없기 때문이다.

DAG-SHORTEST-PATHS(G, w, s)
topologically sort the vertices of G
INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex u, taken in topologically sorted order
    for each vertex v ∈ G.Adj[u]
        RELAX(u, v, w)

Theorem. 가중치가 부여된 방향 비순환그래프에 대해, DAG-SHORTEST-PATHS가 끝나고 나면 v.d = \delta(s, v)이며, 전임자 부분그래프는 s를 루트로 하는 최단 경로 트리이다.

이 알고리즘의 흥미로운 응용은 PERT 차트 분석에서 가장 긴 임계 경로를 판별하는 것이다. 이는 가중치의 부호를 반전시키고 DAG-SHORTEST-PATHS를 동작시켜 구할 수 있다.

24.3. Dijkstra’s algorithm

다익스트라 알고리즘은 가중치가 전부 음이 아닐 때 단일 시작점 최단 경로 문제를 푼다. 좋은 구현이라면 벨만 포드보다 빠르다. 알고리즘은 다음과 같다.

DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = Φ
Q = G.V
while Q ≠ Φ
    u = EXTRACT-MIN(Q)
    S = S ∪ {u}
    for each vertex v ∈ G.Adj[u]
        RELAX(u, v, w)

이는 탐욕적 알고리즘이다.

Theorem. (Correctness of Dijkstra’s algorithm) 다익스트라의 알고리즘은 음이 아닌 가중치 부여된 방향그래프에 적용되었을 때 시작점 s에 대해 모든 정점 u에 대해 u.d = \delta(s, u)로 끝난다.

Corollary. 다익스트라의 알고리즘은 음이 아닌 가중치 부여된 방향그래프에 적용되었을 때 시작점 s에 대해 전임자 부분그래프는 s를 루트로 하는 최단 경로 트리이다.

Analysis

다익스트라의 알고리즘의 복잡도는 최소 우선순위 큐를 어떻게 구현하느냐에 따라 다르다. 가장 쉽게 구현하면 O(V^{2})가 되고, 이진 힙으로 하면 O((V+E) \lg V), 피보나치 힙으로 하면 O(V \lg V + E)가 된다.

24.4. Difference constraints and shortest paths

선형 프로그래밍 중에서는 단일 출발점 최단 경로 문제로 바꿔 풀 수 있는 특수한 경우가 존재한다.

Linear programming

선형 계획법에서는 m x n 행렬 A, m 벡터 b, n 벡터 c에 대해 Ax = b라는 조건 하에 목적 함수 c · x를 최대화 시키는 n 벡터 x를 찾는 것이다. 이는 항상 다항 시간에 풀 수 있는 것은 아니지만, 다항 시간에 찾을 수 있는 선형 계획법이 존재한다. 다항 시간으로 문제를 축소할 수 있다면 그렇게 하면 되고, 일부 케이스는 단일 출발점 최단 경로 문제나 최대 유량 문제로 바꿔 풀 수 있다. 어떨 때는 Ax \leq b만 만족시키는 실현 가능 해를 찾기도 한다. 여기서는 이런 실현 가능성 문제를 알아본다.

Systems of difference constraints

차이 조건계에서는 선형 계획법의 행렬 A가 각 행마다 하나의 1, 하나의 -1, 나머지 0을 갖는다. 즉, x_{j} - x_{i} \leq b_{k} 꼴의 차이 조건이 m개 존재하는 것이다.

Lemma. x가 차이 조건계에 대한 Ax \leq b의 해이면, x + d도 Ax \leq b의 해이다.

Constraint graphs

Ax \leq b의 차이 조건계에 대해, 조건 그래프는 각 차이 조건 x_{j} - x_{i} \leq b_{k}에 대해 가중치 b_{k}의 간선 (i, j)로 유도되는 그래프를 말한다.

Theorem. 차이 조건계로부터 유도되는 조건 그래프가 있다면, 음의 가중치 순환이 없다면 x = (\delta(v_{0}, v_{1}), \cdots, \delta(v_{0}, v_{n}))이 실현 가능해가 된다. 음의 가중치 순환이 있다면 실현 가능해가 없다.

Solving systems of difference constraints

위의 정리로부터 벨만-포드 알고리즘을 사용해서 차이 조건계를 풀 수 있음을 알 수 있다. 이는 O(n^{2} + nm) 시간이 걸리지만, O(nm) 시간으로 줄일 수 있다.

24.5. Proofs of shortest-paths algorithm

The triangle inequality

Lemma. (Triangle inequality) 모든 간선 (u, v) \in E에 대해, \delta(s, v) \leq \delta(s, u) + w(u, v)이다.

Effects of relaxation on shortest-path estimates

Lemma. (Upper-bound property) 항상 v.d \geq \delta(s, v)이며, v.d = \delta(s, v)가 되면 그 값은 바뀌지 않음.

Corollary. (No-path property) s에서 v로의 경로가 없다면 v.d = \delta(s, v) = \infty이다.

Lemma. 간선 (u, v)로부터 완화한 직후, v.d \leq u.d + w(u,v)가 성립함.

Lemma. (Convergence property) s \to u \to v가 u, v에 대해 최단 경로이고 (u, v)에 대한 완화 전 u.d = \delta(s, u)가 된다면, 항상 v.d = \delta(s, v)이다.

Lemma. (Path-relaxation property) 최단 경로 내의 간선들을 완화한다면, 최단 경로 끝점 v_{k}에 대해 v_{k}.d = \delta(s, v_{k})이다.

Relaxation and shortest-paths trees

Lemma. INITIALIZE-SINGLE-SOURCE(G, s)를 수행하고 난 후에는 전임자 부분그래프가 s를 루트로 하는 트리이며, G 내의 임의의 간선들의 열에 대해 완화를 하더라도 이 특성이 유지된다.

Lemma. (Predecessor-subgraph property) 모든 v에 대해 v.d = \delta(s, v)가 된다면, 전임자 부분그래프는 s를 루트로 하는 최단 경로 그래프이다.

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중