Post Lists

2018년 9월 18일 화요일

24 Single-Source Shortest Paths

24 Single-Source Shortest Paths
Professor Patrick은 Phoenix에서 Indianapolis로 가는 가능한 가장 짧은 길을 찾길 원한다. 인접한 교차로의 각 쌍 사이의 거리가 표시된 미국의 road map이 주어진다면, 그녀는 어떻게 이 가장 짧은 루트를 결정할 수 있는가?

한 가지 가능한 방법은 Phoenix에서 Indianapolis까지의 모든 가능한 루트들을 열거하는 것이고, 각 루트에서 거리를 계산하고, 가장 짧은 것에서 선택한다. 그러나, 심지어 cycles을 포함하는 루트들을 허용하지 않은 채로, Professor Patrick은 수 많은 가능성을 조사해야만 하는 것을 아는 것은 쉽다. 그리고 그 대부분의 가능성들은 간단히 고려할 가치가 없다. 예를들어, Phoenix에서 Indianapolis로 Seattle을 거쳐서 가는 한 루트는 명백히 좋지 않은 선택이다. 왜냐하면 Seattle은 길 중에서 몇 백 마일이기 때문이다.

이 챕터와, 그리고 Chapter 25에서, 우리는 그러한 문제들을 효율적으로 어떻게 풀 것인지를 보여준다. shortest-paths problem에서, 우리는 가중치가 있고, 방향이 있는 그래프 G = (V, E)를 받고, weight function w: E -> R는 실수값 가중치로 매핑되는 간선들이 있다. 경로 p = {v_0, v_1, ... v_k}의 가중치 w(p)는 그것을 구성하는 간선들의 가중치들의 합이다:



우리는 u에서 v로가는 최단 경로 가중치 &(u,v)를 다음으로 정의한다.



정점 u에서 v로가는 최단 경로는 그러고나서 w(p) = &(u,v)의 가중치를 가진 어떤 경로 p로 정의된다.

Phoenix-to-Indianapolis 예제에서, 우리는 그 road map을 한 graph로 모델링할 수 있다: 정점들은 교차로를 나타내고, 간선들은 교차로 사이의 도로를, 그리고 간선의 가중치는 도로의 거리를 나타낸다. 우리의 목적은 Phoenix에서 주어진 교차로에서 Indianapolis에서 주어진 교차로까지의 최단경로를 찾는 것이다.

Edge 가중치들은 거리라기 보다는 시간, 비용, 페널티, 손실, 또는 길에 따라 선형으로 축적되고 우리가 최소화하길 원하는 어떤 양과 같은 측정치를 나타낼 수 있다.

Section 22.2의 breadth-first-search algorithm은 가중치가 없는 그래프에서 작동하는 최단 경로 알고리즘이다. 즉, 그 그래프는 각 간선이 단위 weight를 가진 그래프를 말한다. BFS로부터의 개념들의 대부분이 가중치 그래프에서의 최단 경로의 연구에서 많이 발생하기 때문에, 너는 더 나아가기 전에 Section 22.2를 다시 검토할 필요가 있을지도 모른다.

Variants
이 챕터에서, 우리는 single-source shortest-paths problem에 집중할 것이다: graph G = (V, E)가 주어진다면, 우리는 주어진 source vertex s in V에서 각 정점 v in V로 가는 최단 경로를 발견하고 싶다. 그 single-source 문제에 대한 알고리즘은 다음의 variants를 포함하면서 많은 다른 문제들을 해결할 수 있다.

Single-destination shortest-paths problem: 각 정점 v로부터 주어진 목적지 정점 t로 가는 최단 경로를 찾아라. 그래프에서 각 edge의 방향을 반대로하여, 우리는 이 문제를 single-source problem으로 만들 수 있다.

Single-pair shortest-path problem: 주어진 정점 u와 v에 대해 u에서 v로 가는 최단 경로를 찾아라. 만약 우리가 source vertex u를 가지고 single-source problem을 해결한다면, 우리는 이 문제 또한 해결할 수 있다. 게다가, 이 문제에 대해 모든 알려진 알고리즘들은 가장 좋은 single-source 알고리즘들과 같은 가장 worst-case asymptotic running time을 갖는다.

All-pairs shortest-paths problem: 모든 정점들 u와 v에 대한 쌍에 대해 u에서 v로가는 최단 경로를 찾아라. 비록 우리가 각 정점으로부터 single source algorithm을 작동시켜 이 문제를 풀 수 있을지라도, 우리는 보통 그것을 더욱 빠르게 풀 수 있다. 부가적으로, 그것의 구조는 그것 자체로도 흥미롭다. Chapter 25는 세부적으로 all-pairs problem을 다룬다.

Optimal substructure of a shortest path
최단 경로 알고리즘은 일반적으로 두 정점들 사이의 최단 경로가 그것 내에서 다른 최단 경로를 포함하는 특징에 의존한다. (Chapter 26에서 Edmonds-Karp maximmum-flow 알고리즘또한 이 특징에 의존한다.) optimal substructure가 dynamic programming(Chapter 15)와 greedy method (Chapter 16)가 적용할지도 모르는 key indicators중의 하나라는 것을 회상해라. 우리가 Section 24.3에서 볼 Dijkstra의 알고리즘은 greedy algorithm이고, 모든 정점들의 쌍 사이의 최단 경로를 찾는 (see Section 25.2) Floyd-Warshall algorithm은 dynamic-programming algorithm이다. 다음의 lemma는 좀 더 정확하게 최단 경로의 optimal-substructure property를 명시한다.

Lemma 24.1 (Subpaths of shortest paths are shortest paths)
가중치가 있고, 방향이 있는 그래프 G = (V, E), 거기에 w : E -> R인 가중치 함수도 있다고 고려하고, p = {v_0, v_1, ... v_k}가 정점 v_0에서 v_k로 가는 최단 경로라고 하자, 0 <= i <=j <= k 가 되게하는 i와 j에 대해, p_ij = {v_i, v_i+1, .... v_j}가 v_i정점에서 v_j정점으로 가는 p의 subpath라고 하자. 그러면 p_ij는 v_i에서 v_j로 가는 최단 경로이다.

Proof 만약 우리가 경로 p를 v_0 ->(p_0i) v_i ->(p_ij) v_j ->(p_jk) v_k로 분해한다면, 그러면 우리는 w(p) = w(p_0t) + w(p_ij) + w(p_jk)를 갖는다. 이제 v_i에서 v_j로 가고 weight w(p`_ij) < w(p_ij)인 경로 p`_ij가 있다고 가정하자. 그러면, v_0 ->(p_0i) v_i ->(p'_ij) v_j ->(p_jk) v_k는 v_0에서v_k로 가는 경로인데, 가중치 w(p_0i) + w(p'_ij) + w(p_jk)이고, 이것은 w(p)보다 작다. 그리고 이것은 p가 v_o에서 v_k로 가는 최단 경로인 가정과 모순된다.

Negative-weight edges
single-source shortest-paths problem의 어떤 예시들은 가중치가 음수인 간선들을 포함할지도 모른다. 만약 그래프 G = (V, E)가 source s로부터 도달가능한 음의 가중치 사이클을 포함하지 않는다면, 그러면 모든 v in V에 대해, 최단 경로 weight &(s, v)는 잘 정의되게 된다. 비록 그것이 음의 값을 가질지라도. 만약 그 그래프가 s에서 도달가능한 음의 가중치 사이클을 포함한다면, 그러나, 최단 경로 가중치는 잘 정의되지 않는다. s에서 그 사이클에 있는 한 정점으로 가는 어떠한 경로도 최단 경로가 될 수 없다 - 우리는 항상 제안된 "shortest" 경로를 따르고, 그러고나서 음의 가중치 사이클을 가로질러서 더 낮은 가중치를 가진 한 경로를 항상 찾을 수 있다. 만약 s에서 v로 가는 어떤 경로에서 음의 가중치 사이클이 있다면, 우리는 &(s,v) = -infinity로 정의한다.

그림 24.1은 음의 가중치와 최단 경로 가중치에서 음의 가중치 사이클의 효과를 보여준다. s에서 a로 가는 (경로 <s, a>)것은 오직 한 경로만 있기 때문에, &(s,a) = w(s,a) = 3이다. 유사하게, s에서 b로 가는 것은 오직 하나의 경로만 있고, 그래서 &(s,b) = w(s,a) + w(a,b) = 3 + (-4) = -1이다. s에서 c로 가는 무한히 많은 경로들이 있다: <s.c>, <s,c,d,c>, <s,c,d,c,d,c,>, and so on.  cycle <c,d,c>는 가중치 6 + (-3) = 3 > 0을 가지기 때문에, s에서 c로 가는 최단 경로는 <s, c>이고, 가중치 &(s,c) = w(s,c) = 5가 된다. 유사하게, s에서 d로가는 최단 경로는 <s,c,d>이고, 가중치 &(s,d) = w(s,c) + w(c,d) = 11이다. 유사하게, s에서 e로 가는 무수히 많은 경로들이 있다: <s,e>, <s,e,f,e,>, <s,e,f,e,f,e,>, 등등. cycle <e,f,e>는 3 + (-6) = -3 < 0의 가중치를 가지기 때문에, 그러나, s에서 e로가는 어떠한 최단 경로가 없다. 음의 가중치 사이클 <e,f,e>를 임의로 여러번 지남으로써, 우리는 s에서 e로 가는 임의의 큰 음의 가중치를가진 경로를 발견할 수 있고, 그래서 &(s,e) = -infinity이다. 유사하게, &(s, f) = -infinity이다. f에서 g가 도달 가능하기 때문에, 우리는 또한 s에서 g로 가는 임의의 큰 음의 가중치를 가진 경로를 찾을 수 있고, 그래서 &(s,g) = -infinity이다. 정점 h, i, and j는 또한 음의 가중치 사이클을 형성한다. 그러나 그것들은 s로부터 도달가능하지 않고,그래서 &(s,h) = &(s,i) = &(s,g) = infinity이다.

Dijkstra의 알고리즘 같은 몇 가지 최단 경로 알고리즘들은 입력 그래프에서 모든 간선의 가중치들이 road-map example에서 처럼 음이 아니라고 가정한다. Bellman-Ford algorithm같은 다른 것들은 입력 그래프에서 음의 가중치 간선들을 허용하고, source로부터 어떠한 음의 가중치 사이클들이 없는 한 올바른 답을 만들 수 있다. 일반적으로, 만약 그러한 음의 가중치 사이클이 있다면, 그 알고리즘은 그것의 존재를 탐지하고 보고할 수 있다.

Cycles
최단 경로는 사이클을 포함할 수 있는가? 우리가 보았듯이, 그것은 음의 가중치 사이클은 포함할 수 없다. 그것은 양의 가중치 사이클도 또한 포함할 수 없다. 왜냐하면 그 경로에서 사이클을 제거하는 것은 같은 source and destination vertices를 가지고 있고, 더 낮은 path weight를 가진 경로를 만들어내기 때문이다. 즉, 만약 p = {v_0, v_1, ..., v_k}가 한 경로이고, c = {v_i, v_i + 1, ...., v_j}가 이 경로에 있는 양의 가중치 사이클이라면 (v_i = v_j이고 w(c) > 0인_, 그러면 그 경로 p' = {v_0, v1, ...., v_i, v_j + 1, v_j+2, ... v_k>는 w(p') = w(p) - w(c) < w(p)인 가중치를 갖고, 그래서 p는 v_0에서 v_k로 가는 최단 경로가 될 수 없다.

그것은 오직 0인 가중치 사이클을 남긴다. 우리는 가중치가 같은 다른 경로를 만들기 위해 0-가중치 사이클을 어떤 경로로부터 제거할 수 있다. 따라서, 만약 0-weight cycle을 포함하는 한 source vertex s에서 destination vertex v로 가는 최단 경로가 있다면, 그러면 이 사이클 없이 s에서 v로 가는 또 다른 최단경로가 있다. 최단 경로가 0-weight cycles를 가지는 한, 우리는 반복적으로 cycle이 없는 최단 경로를 갖을 때까지 이러한 사이클을 그 경로에서 제거할 수 있다. 그러므로, 일반성에 대한 손실 없이, 우리가 최단 경로를 찾을 때, 최단 경로들이 사이클들이 없다고 가정할 수 있다. 즉, 그것들은 simple paths이다. graph G = (V, E)에서 어떤 비순환 경로는 최대 |V|개의 다른 정점들을 포함하기 때문에, 그것은 또한 최대 |V| - 1의 간선을 포함한다. 따라서, 우리는 최대 |V| - 1개의 간선들의 최단 경로로 우리의 관심을 제한할 수 있다.

Representing shortest paths
우리는 종종 최단 경로 가중치를 계산할 뿐만 아니라, 또한 최단경로에 있는 정점들을 연산하길 원한다. 우리는 Section 22.2에서 breadth-first trees를 나타냈던 방식과 유사하게 최단 경로를 나타낸다. graph G = (V, E)가 주어진다면, 우리는 다른 정점이거나 NIL중의 하나인 predecessor v.pi를 각 정점 v in V에 대해 유지한다. 이 챕터에서 최단 경로 알고리즘은 pi attributes를 설정한다. 이것은 한 정점 v에서 기원이 있는 predeessors의 chain이 s에서 v로 가는 최단 경로를 따라 뒤로 흘러 간다. 따라서, v.pi != NIL인 어떤 정점 v가 주어다면, Section 22.2의 procedure PRINT-PATH(G,s,v)는 s에서 v로 가는 최단 경로를 출력할 것이다.

PRINT_PATH(G, s, v)
1 if v == s
2      print s
3 else if v.pi == NIL
4      print "no path from" s "to" v "exists"
5 else PRINT-PATH(G, s, v.pi)
6      print v

그러나, 최단 경로 알고리즘을 실행하는 중간에, pi values는 최단 경로를 가리키지 않을지도 모른다. BFS에서 처럼, 우리는 pi values에 의해 추론되는 G_pi = (V_pi, E_pi)의 predecessor subgraph에 흥미가 있을 것이다. 여기에서 다시, 우리는 vertex set V_pi를 NIL predecessors가 없는 G의 정점들의 집합으로정의한다, source s를더해서:

V_pi = {v in V : v.pi != NIL} U {s}.

방향이 있는 edge 집합 e_pi는 V_pi에 있는 정점들에 대해 pi values에 의해 유도되는 간선들의 집합이다:

E_pi = {(v.pi, v) in E: v in V_pi - {s}}.

우리는 이 챕터에서 그 알고리즘들에 의해 만들어진 pi values가 종료시에 G_pi가 "shortest-paths tree"라는 특징을 갖는다는 것을 증명할 것이다 - 비공식적으로, rooted tree인데, 이것은 source s에서 s로부터 도달할 수 있는 모든 정점으로 가는 최단 경로를 포함한다. 최단 경로 트리는 Section 22.2의 breadth-first tree와 같지만, 그것은 간선의 개수 대신에, edge weights의 관점으로 정의된 source로부터의 최단 경로를 포함한다. 정확히 하기 위해서, G = (V, E)가 가중치가 있고, 방향이 있는 그래프이며, 가중치 함수 w: E -> R이라고 하자. 그리고 G가 source vertex s in V로부터 도달가능한 어떠한 음의 가중치 사이클을 포함하지 않는다고 가정하자.이것은 최단 경로가 잘 정의되기 위해서이다. s를 root로하는 shortest-paths tree는 방향이 있는 subgraph G' = (V', E')이고, 거기에서, V' in V이고, E' in E이다. 다음을 성립하기 위해서이다.


  1. V'는 G에서 s로부터 도달가능한 정점들의 집합이다.
  2. G'는 root s를 가지는 rooted tree이고,
  3. 모든 v in V'에 대해, G;에서 s에서 v로가는 unique simple path는 G에서 s에서 v로 가는 최단 경로이다.

최단 경로들은 필수적으로 unique하지 않고, shortest-paths trees도 아니다. 예를들어, 그림 24.2는 가중치가 있고, 방향이 있는 그래프와 같은 root를 가진 두 개의 최단 경로 트리를 보여준다.

Relaxation
이 챕터에서 알고리즘들은 relaxation 기법을 사용한다. v in V인 각 정점에 대해, 우리는 v.d attribute를 유지하는데, 이것은 source s에서 v로 가는 최단 경로의 가중치에 대한 upper bound이다. 우리는 v.d를 shortest-path estimate라고 부른다. 우리는 shortest-path estimates와 predecessors를 다음의 O(V)-time procedure로 초기화한다:

INITIALIZE-SINGLE-SOURCE(G,s)
1 for each vertex v in G.V
2      v.d = INFINITY
3      v.pi = NIL
4 s.d = 0

초기화 후에, 모든 v in V에 대해, v.pi = NIL를 갖고, v in V - {s}에 대해 v.d = INFINITY를 갖게된다.

한 edge(u,v)를 relaxing하는 프로세스는 우리가 u를 거쳐서 지금까지 발견된 v로 가는 최단 경로를 개선시킬 수 있는지를 확인하고, 만약 그렇다면 v.d와 v.pi를 업데이트 시키는 것으로 구성된다. relaxation step은 최단 경로 estimate의 값을 낮추고 v의 predecessor attribute v.pi를 업데이트 시킬지도 모른다. 다음의 코드는 O(1) time에 edge(u, v)에 대해 relaxation step을 형성한다:

RELAX(u, v, w)
1 if v.d > u.d + w(u,v)
2   v.d = u.d + w(u,v)
3   v.pi = u

그림 24.3는 한 edge를 relaxing하는 것의 두 예제를 보여준다. 하나는, 최단 경로 estimate가 줄어들고, 하나는 estimate 변화가 없다.

이 챕터에서의 각 알고리즘은 INITIALIZE-SINGLE-SOURCE를 호출하고, 그러고나서 반복적으로 edges를 relaxes한다. 게다가, relaxation은 최단 경로 estimates와 predecessors가 바뀌는 유일한 수단이다. 이 챕터에서의 알고리즘들은 그것들이 각 간선을 얼마나 많이 relax하고, 그것들이 edges들을 relax시키는 순서가 다르다. Dijkstra의 알고리즘과 방향이 있는 비순환 그래프에 대해 최단 경로 알고리즘은 각 간선을 정확히 한 번만 relax한다. Bellman-Ford 알고리즘은 각 간선을 |V| - 1번 relax한다.

Properties of shortest paths and relaxation
이 챕터에 있는 알고리즘들이 올바르다는 것을 증명하기 위해, 우리는 최단 경로의 몇 가지 특성과 relaxation에 대해 호소할 것이다. 우리는 여기에서 이러한 특징들을 말하고, Section 24.5가 그것들을 공식적으로 증명한다. 너의 레퍼런스에 대해, 여기에서 명시되는 각 특징은 Section 24.5로부터 적절한 lemma or corollary number를 포함한다. shortest-path estimates or the predecessor subgraph를 말하는 이러한 특성들 중 뒤에서 5개는 implicitly하게, 그래프가 INITIALIZE-SINGLE-SOURCE(G, s)에 대한 호출로 초기화 되었다는 것을 가정하고, shortest-path estimates와 the predecessor subgraph가 변화하는 유일한 방법이 relaxation steps의 몇 가지 순서에 의한 것이라고 가정한다.

Triangle inequality (Lemma 24.10)
 어떤 간선 (u, v) in E에 대해, 우리는 &(s, v) <= &(s,u) + w(u,v).

Upper-bound property (Lemma 24.11)
 우리는 모든 v in V에 대해 항상 v.d >= &(s,v)를 갖고, v.d가 &(s,v)를 얻게된다면, 그것은 결코 바뀌지 않는다.

No-path property (Corollary 24.12)
 만약 s에서 v로가는 어떠한 경로도 없다면, 그러면 우리는 항상 v.d = &(s,v) = INFINITY를 갖는다.

Convergence property (Lemma 24.14)
 만약 s -> u -> v가 어떤 u,v in V에 대해 G에서의 최단 경로이고, edge (u,v)를 relax시키기 전에 언제든지 u.d = &(s,u)이라면, 그러면 그 후에 항상 v.d = &(s,v) 이렇게 된다.

Path-relaxation property (Lemma 24.15)
 만약 p = <v_0, v_1, ..., v_k>가 s = v_0에서 v_k까지의 최단 경로이고, 우리가 (v_0, v_1), (v_1, v_2), ..., (v_{k-1}, v_k)의 순서로 p의 간선들을 relax시킨다면, 그러면 v_k.d = &(s, v_k)이다. 이 특징은 발생하는 어떤 다른 relaxation steps와 상관없이 유효하다. 비록 그것들이 p의 edges의 relaxations와 서로 섞일지라도.

Predecessor-subgraph property (Lemma 24.17)
 모든 v in V에 대해, v.d = &(s,v)이기만 한다면, 그 predecessor subgraph는 s를 root로하는 최단 경로 tree이다.

Chapter outline
Section 24.1은 Bellman-Ford 알고리즘을 보여준다. 이 알고리즘은 간선들이 음수의 가중치를 가질 수 있는 일반 경우에서의 single-source shortest-paths problem을 해결한다. 그 Bellman-Ford algorithm은 놀랍게도 간단하고, 그것은 더욱이 negative-weight cycle이 source로부터 도달가능한 지를 탐색하는 이득을 가지고 있다. Section 24.2는 방향이 있는 비순환 그래프에서, single source로부터 최단 경로를 연산하는 linear-time algorithm을 준다. Section 24.3은 Dijkstra의 알고리즘을 다루고, 그것은 Bellman-Ford algorithm보다 더 적은 running time을 갖지만, 간선의 가중치들이 음이 아니도록 요구한다. Section 24.4는 linear programming의 특별한 경우를 해결하기 위해 Bellman-Ford 알고리즘을 어떻게 사용할 수 있는지를 보여준다. 마지막으로, Section 24.5는 위에서 명시된 최단 경로의 특성과 relaxation의 특성을 증명한다.

우리는 infinities와 연산을 하기 위한 몇 가지 convetions을 요구한다. 우리는 a != -infinity인 실수에 대해, 우리가  a + infinity = infinity + a = infinity라고 가정한다. 또한, 음의 가중치 사이클의 존재에서 우리의 증명을 유효하게 만들기 위해, 우리는 a != infinity인 실수에 대해, 우리는  a + (-infinity) = (-infinity) + a = -infinity라고 가정할 것이다.

이 챕터에서 모든 알고리즘들은 방향이 있는 그래프 G가 인접리스트 표기로 저장된다고 가정한다. 부가적으로, 그것의 가중치가 각 간선과 함께 저장된다. 우리가 각 인접 리스트를 가로지를 때, 우리가 edge마다 O(1)의 시간으로 edge 가중치들을 결정할 수 있도록 하기위해서 이다.

24.1 The Bellman-Ford algorithm
Bellman-Ford algorithm은 간선의 가중치가 음수일지도 모르는 일반적인 경우의 single-source shortest-paths 문제를 푼다. 가중치가 있고, 방향이 있는 그래프 G = (V, E)가 주어진다면, 거기에 source s와 가중치 함수 w : E -> R이 더해지면, 그 Bellman-Ford 알고리즘은 source로부터 도달할 수 있는 음의 가중치 사이클이 있는지 없는지를 알려주는 boolean value를 반환한다. 만약 그러한 사이클이 있다면, 그 알고리즘은 어떠한 해결책이 존재하지 않는다고 가리킨다. 만약 그러한 사이클이 없다면, 그 알고리즘은 최단 경로와 그것들의 가중치를 만들어낸다.

그 알고리즘은 edges를 relax하고, 점진적으로 source s에서 각 정점 v in V까지의 최단 경로의 가중치에 있는 estimate v.d를 줄이면서. 이것은 그것이 실제 최단 경로 가중치 &(s,v)에 도달할 때 까지 한다. 그 알고리즘은 True를 반환하는데 if and only if (iff) 그 그래프가 그 source로부터 도달가능한 어떠한 음의 가중치 사이클을 포함하지 않는다면 일 때 이다.


BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i = 1 to |G.V| - 1
3    for each edge (u,v) in G.E
4            RELAX(u,v,w)
5 for each edge(u,v) in G.E
6       if v.d > u.d + w(u.v)
7            return FALSE
8 return TRUE

그림 24.4는 5개의 정정이 있는 한 그래프에서 벨만포드 알고리즘의 실행을 보여준다. line 1에서 모든 정점들의 d와 pi values를 초기화 한 후에, 그 알고리즘은 그래프의 간선들에 대해 |V| - 1번 passes를 한다. 각 pass는 lines 2-4의 for loop의 한 번의 반복이고, 그 그래프의 각 간선을 relaxing을 한 번 하는 것으로 구성된다. 그림 24.4 (b)-(e)는 그 간선들에 대해 4개의 passes들 각각 후의 알고리즘의 상태를 보여준다. |V| - 1의 passes를 한 후에, lines 5-8은 negative-weight cycle에 대해 체크하고, 적절한 boolean value를 반환한다. (우리는 이 체크가 왜 작동하는지를 조금 나중에 볼 것이다.)

그 벨만포드 알고리즘은 O(VE)의 시간에 작동한다. 왜냐하면 line 1에서 초기화는 O(V) time이 걸리고, lines 2-4에서 간선들에 대해 |V| - 1 passes의 각각은 O(E) time이 걸리고, for loop of lines 5-7은 O(E) time이 걸린다.

벨만 포드 알고리즘의 올바름을 증명하기 위해, 우리는 만약 어떠한 음의 가중치 사이클이 없다면 그 알고리즘이 source로부터 도달가능한 모든 정점들에 대해 올바른 최단 경로 가중치를 연산한다는 것을 보여주어서 시작한다.

Lemma 24.2
G = (V, E)가 가중치 있고, 방향이 있는 그래프이고, 거기에 source s와 가중치 함수 w : E -> R이 있다고 하자. 그리고 G가 s로부터 도달가능한 어떠한 음의 가중치 사이클들을 포함하지 않는다고 가정하자. 그러고나서 BELLMAN-FORD의 lines 2-4의 for loop의 |V| - 1번의 반복 후에, 우리는 s로부터 도달가능한 모든 정점 v에 대해 v.d = &(s,v)를 가진다.

Proof path-relaxation property를 이용하여 lemma를 증명한다. s로부터 도달가능한 어떤 정점 v를 고려하자, p = <v_0, v_1, ... ,v_k>라고 하자. 거기에서 v_0 = s이고, v_k = v이고, 그 p는 s로부터 v로가는 최단경로라고하자. 최단 경로는 simple하기 때문에, p는 최대 |V| - 1개의 edges를 가지고, 그래서 k <= |V| - 1이다. lines 2-4의 for loop의 |V| - 1의 반복의 각각이 모든 |E| edges를 relax한다. i = 1,2,...,k에 대해, (v_i-1, v_i)는 i번째 반복에서, relaxed된 간선들 사이에있다. path-relaxation property에 의해, 그러므로, v.d = v_k.d = &(S,v_k) = &(s,v)이다.

Corollary 24.3
G가 가중치가 있고 방향이 있는 그래프라고 하고, source vertex s와 weight function w: E->R이 있다고 하자. 그리고 G가 s로부터 도달가능한 어떠한 음의 가중치 사이클을 포함하지 않는다고 가정하자. 그러고나서 각 v in V에 대해, s에서 v로 가는 경로가 있다. if and only if(iff) 벨만 포드가 G에 대해 작동될 때 v.d < infinity로 종료된다면.

Proof 그 증명은 Exercise 24.1-2 (이건 그렇지 않다면 갈 수 없게 되므로 옳다.)

Theorem 24.4 (Correctness of the Bellman-Ford algorithm)
BELLMAN-FORD가 가중치 있고, 방향이 있는 그래프 G = (V, E)라고하고, source s와 weight function w: E -> R이 있다고 하자. 만약 G가 s로부터 도달가능한 음의 가중치 사이클을 포함하지 않는다면, 그 알고리즘은 TRUE를 반환하고, 우리는 모든 정점들 v in V에 대해 v.d = &(s,v)를 갖는다. 그리고 predecessor subgraph G_pi는 s를 root로 하는 최단 경로 트리이다. 만약 G가 s로부터 도달가능한 음의 가중치 사이클을 포함한다면, 그러면 그 알고리즘은 FALSE를 반환한다.

Proof 그래프 G가 s로부터 도달가능한 음의 가중치 사이클을 포함하지 않는다고 가정하자. 우리는 처음에 종료시에 모든 v in V에 대해 v.d = &(s,v)라고 하는 주장을 증명한다. 만약 정점 v가 s로부터 도달가능하다면, 그러면 Lemma 24.2는 이 주장을 증명한다. 만약 v가 s로부터 도달할 수 없다면, 그러면 그 주장은 no-path property를 따른다. 따라서, 그 주장은 증명된다. 그 주장을 따라 predecessor-subgraph property는 G_pi가 최단 경로 트리라는 것을 암시한다. 우리는 이제 BELLMAN-FORD가 TRUE를 반환한다는 것을 보여주기 위해 그 주장을 사용한다. 종료시에, 우리는 모든 edges (u,v) in E에 대해 다음으 갖는다.

v.d = &(s,v)
     <= &(s,u) + w(u,v)  (by the triangle inequality)
      = u.d + w(u,v)

그리고 line 6에 있는 테스트들 중 어떠한 것도 BELLMAN-FORD가 FALSE를 반환하도록 일으키지 않는다. 그러므로, 그것은 TRUE를 반환한다.

이제 그래프 G가 s로부터 도달가능한 음의 가중치 사이클을 포함한다고 가정하자; 이 사이클이 c = <v_0, v_1, ..., v_k>라고 하고, v_0 = v_k이다. 그러고나서

sum(from i = 1 to k) w(v_i-1, v_i) < 0.         (24.1)

모순의 목적으로, Bellman-Ford 알고리즘이 TRUE를 반환하다고 가정하자. 따라서, i = 1,2,...,k에 대해 v_i.d <= v_i-1.d + w(v_i-1, v_i) 이다. cycle c에 대해 부등식을 합하는 것은 우리에게 다음을 준다.



v_0 = v_k이기 때문에, c에 있는 각 정점은 정확히 sum{from i = 1 to k} v_i.d와 v_i-1.d 에 한 번씩 나타나고, 그래서



게다가, Corollary 24.3에 의해, v_i.d는 1.2.,,,.k에 대해 유한하다. 따라서,



이것은 부등식(24.1)과 모순된다. 우리는 만약 그래프 G가 source로부터 어떠한 음의 가중치 사이클을 포함하지 않는다면 TRUE를 반환하고, 그렇지 않다면 FALSE를 반환한다고 결론짓는다.

{
책에서의 증명은 수식으로 하여 해결하는데, 그래프를 relax시킬 때 어떻게 되는지 생각해보면 알 수 있다.
음의 가중치 Cycle이 존재할 때, 한 정점당 |V| - 1번의 Relaxation을 할 때, 그 음의 Cycle에 있는 음의 가중치 간선은 매우 큰 음의 값으로 한 정점의 estimate를 뺄셈하게 된다. 그래서 나중에 그 매우 여러번 뺄셈하게 된 정점에서 그 음의 사이클 내의 다른 정점으로 가게 될 때 edge(u,v) 상황에서, v.d > u.d + cost의 상황이 발생하게 되는 것이다.
}

24.2 Single-source shortest paths in directed acyclic graphs
가중치가 있는 dag(directed acyclic graph) G = (V, E)의 간선들을 relaxing하여, 그것의 정점들의 위상정렬에 따라서, 우리는 single source로부터의 최단 경로를 O(V+E) 시간에 연산할 수 있다. 최단 경로들은 항상 dag에서 잘 정의된다. 왜냐하면 비록 음의 가중치 간선들이 있을지라도, 어떠한 음의 가중치 사이클들이 존재하지 않기 때문이다.

그 알고리즘은 dag를 위상정렬하여 시작한다 (see Section 22.4). 이것은 정점들을 linear ordering으로 만들기 위해서이다. 만약 그 dag가 정점 u에서 정점 v로가는 한 경로를 포함한다면, 그러면 u는 위상정렬에서 v를 선행한다. 우리는 위상 정렬된 순서의 정점들에 대해 한 번의 pass를 한다. 우리가 각 정점을 처리함에 따라, 우리는 그 정점을 떠나는 각 간선을 relax한다.


DAG-SHORTEST-PATHS(G,w,s)
1 topologically sort the vertices of G
2 INITIALIZE-SINGLE-SOURCE(G,s)
3 for each vertex u, taken in topologically sorted order
4       for each vertex v in G.adj[i]
5             RELAX(u,v,w)

그림 24.5는 이 알고리즘의 실행을 보여준다.

이 알고리즘의 작동 시간은 분석하기에 쉽다. 그림 22.4에서 보여지듯이, line 1의 위상 정렬 은 O(V + E) time이 걸린다. line 2에서 INITIALIZE-SINGLE-SOURCE의 호출은 O(V) time이 걸린다. lines 3-5의 for loop는 정점마다 한 번의 반복을 한다. 모두 합쳐서, lines 4-5의 for loop는 각 edge를 정확히 한 번 relaxes한다 (우리는 여기에서 aggregate analysis를 사용했다.) inner for loop의 각 반복은 O(1) 시간이 걸리기 때문에, 그 총 작동시간은 O(V + E)이다. 그리고 이것은 그래프의 인접 리스트 표기의 크기에서 linear하다.

다음의 정리는 DAG-SHORTEST-PATHS 절차가 정확히 shortest paths를 연산하는 것을 보여준다.

Theorem 24.5
만약 한 가중치가 있고, 방향이 있는 그래프 G = (V, E)가 정점 vertex s와 어떠한 사이클을 가지고 있지 않다면, 그러면 DAG-SHORTEST-PATHS 절차의 종료 때, 모든 v in V에 대해, v.d = &(s,v)가 되고, 그 predecessor subgraph G_pi는 최단 경로 트리가 된다.

Proof 우리는 처음에 종료시에 모든 정점들 v in V에 대해 v.d = &(s,v)인 것을 보여준다. 만약 v가 s로부터 도달가능하지 않다면, 그러면 v.d = &(s,v) = infinity가 된다. no-path property에 의해. 이제, v가 s로부터 도달가능하다고 가정하자. 최단 경로 p = <v_0, v_1,..., v_k>가 있도록 하기 위해서 이다. 여기에서 v_0 = s이고 v_k = vㅇ이다. 우리가 정점들을 위상정렬 순서대로 처리하기 때문에, 우리는 (v_0, v_1), (v_1, v_2), ... (v_k-1, v_k)의 순서대로 p에 있는 간선들을 relax한다. path-relaxation property는 i = 0,1,...,k에 대해 종료시에
v_i.d = &(s, v_i)인 것을 암시한다. 마침내, predecessor subgraph property에 의해, G_pi는 최단 경로 트리이다.

이 알고리즘의 흥미로운 적용은 PERT(Program Evaluation and Review Technique) char analysis에서 critical paths(임계경로)를 결정하는데 발생한다. 간선들은 수행될 작업들을 나타내고, 간선의 가중치들은 특정한 일을 수행하는데 요구되는 시간을 나타낸다. 만약 간선(u, v)가 정점 v에 들어가고, 간선(v,x)가 v를 떠난다면, 그러면 job(u,v)는 (v,x)에 들어가기전에 수행되어져야 한다. 이 dag를 통한 한 경로는 특정한 순서로 수행되어져야 하는 jobs의 순서를 나타낸다. critical path는 dag를 통과하는 가장 긴 경로이고, 이것은 jobs의 어떤 순서를 수행하는 가장 긴 시간과 대응된다. 따라서, 한 임계경로의 가중치는 모든 jobs를 수행하는 총 시간에 대해 lower bound(하한)을 제공한다. 우리는 critical path를 다음의 둘 중 하나를 통해 찾을 수 있다.


  • 간선 가중치를 음수화하고, DAG-SHORTEST-PATHS를 작동시키거나
  • DAG-SHORTEST-PATHS를 수정하여 작동시키는데, INITIALIZE-SINGLE-SOURCE의 line 2에서 우리는 INFINITY를 -INFINITY로 수정한다.  그리고 Relax procedure에서 ">"를 "<"로 바꾼다.

24.3 Dijkstra's algorithm
다익스트라 알고리즘은 가중치가 있고 방향이 있는 그래프 G = (V, E)에 대해 모든 간선의 가중치가 음이 아닌 경우에 single-source shortest-paths problem을 해결한다. 그러므로, 이 섹션에서, 우리는  w(u,v)가 각 간선 (u,v) in E에 대해 0보다 크거나 같다고 가정한다. 우리가 보게 되듯이, 좋은 구현과 함께, 다익스트라 알고리즘의 작동시간의 벨만포드 알고리즘보다 더 낮다.

다익스트라 알고리즘은 source s로부터의 마지막 최단 경로의 가중치가 이미 결정된 정점들의 집합 S를 유지한다. 그 알고리즘은 반복적으로 최단경로의 minimum estimate를 가진 정점 u in V - S을 선택하고, u를 S에 더하고, u를 떠나는 모든 edges를 relaxes한다. 다음의 구현에서, 우리는 그것들의 d값들에 의해 key가 되는 정점들의 min-priority queue Q를 사용한다.


DIJKSTRA(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 S = 0
3 Q = G.V
4 while Q != 0
5     u = EXTRACT-MIN(Q)
6     S = S U {u}
7     for each vertex v in G.Adj[u]
8            RELAX(u,v,w)

다익스트라 알고리즘은 그림 24.6에 보여지는 간선들을 relax한다. Line 1은 보통의 방식으로 d와 pi 값을 초기화하고, line 2는 그 집합 S를 공집합으로 초기화한다. 그 알고리즘은 lines 4-8의 while loop의 각 반복의 시작에서 Q = V - S인 invariant를 유지한다. Line 3는 min-priority queue Q가 V에 있는 모든 정점들을 포함하도록 초기화한다; 이 때 S = 0이기 때문에, 그 invariant는 line 3 이후에 참이다. lines 4-8의 while loop를 통해 매번, line 5는 Q = V - S로부터 정점 u를 추출하고, line 6는 그것을 집합 S에 넣는다. 그것으로 인해 그 invariant를 유지한다. (이 루프를 통한 첫 번째에 u = s이다.) 그러므로, 정점 u는 V - S에 있는 어떤 정점의 가장 작은 최단 경로 estimate를 가진다. 그러고나서 lines 7-8은 u를 떠나는 각 간선(u,v)를 relax하고, 따라서 estimate v.d와 predecessor v.pi를 업데이트 시킨다. 만약 우리가 u를 거쳐서 지금까지 발견된 v로가는 최단 경로를 개선시킬 수 있다면. 그 알고리즘이 line 3 이후에, Q로 어떠한 정점도 넣지 않고, 각 정점이 Q로부터 추출되는 것을 관찰해라. 그리고 그 각 정점은 즉히 한 번씩 S로 더해진다. 이것은 lines 4-8이 정확히 |V|번 반복하도록 하기 위해서이다.

다익스트라 알고리즘은 집합 S에 추가하기 위해 항상 V - S에 있는 "lightest" or "closest" vertex을 고르기 때문에, 우리는 그것이 greedy strategy를 사용한다고 말한다. Chapter 16은 greedy strategies에 대해 세부적으로 설명하지만, 너는 다익스트라 알고리즘을 이해하기 위해 그 챕터를 읽을 필요는 없다. 그리디 전략은 항상 일반적으로 최적의 결과를 만들어내는 것은 아니지만, 다음의 정리와 corollary가 보여주듯이, 다익스트라 알고리즘은 정말로 최단 경로를 연산한다. 그 key는 그것이 정점 u를 S에 추가할 때 마다, 우리가 u.d = &(s,u)를 갖는 것을 보여주는 것이다.

Theorem 24.6 (Correctness of Dijkstra's algorithm)
다익스트라 알고리즘은 가중치가 있고 방향이 있는 그래프 G = (V,E)에 작동하고, 그것은 음의 가중치 함수 w가 없고, source s가 있다. 그리고 모든 정점 u in V에 대해 u.d = &(s.u)로 끝나게 된다.

Proof 우리는 다음의 loop invariant를 따른다:
 lines 4-8의 while loop의 각 반복의 시작에서, 각 정점 v in S에 대해 v.d = &(s,v) 이다.

각 정점 u in V에 대해, u가 집합 S에 추가 될 때 우리가 u.d = &(s,u)를 갖는다는 것을 보여주는 것은 충분하다. 일단 우리가 u.d =&(s,u)라는 것을 보여주기만 한다면, 우리는 그 부등식이 항상 유효하다는 것을 보여주기 위해 upper-bound property에 의존한다.

Initialization : 초기에, S = 0이고, 그래서 그 invariant는 자명하게 참이다.
Maintenance : 우리는 각 반복에서, 집합 S에 추가되는 정점에 대해 u.d = &(s,u)라는 것을 보여주길 원한다. 모순의 목적을 위해, u가 집합 S에 추가될 때 u.d != &(s,u)가 되는 첫 번째 정점이라고 하자. 우리는 우리의 관심을 while loop의 반복의 초기 상황에 둘 것인데, 거기에서 u는 S에 추가되고, s에서 u로 가는 최단 경로를 조사하여 그 시기에 u.d = &(s,u)라는 모순을 끌어낸다. 우리는 u != s를 가져야만 한다. 왜냐하면 s가 집합 S에 추가되는 첫 번째 정점이고, 그 때 s.d = &(s,s) = 0이기 때문이다. u != s가 아니기 때문에, 우리는 또한 u가 S에 추가되기 전에 s != 0을 갖게된다. s에서 u로 가는 몇 가지 경로가 있어야만 한다. 왜냐하면 그렇지 않으면, no-path property에 의해 u.d = &(s,u) = infinity이기 때문이다. 그리고 이것은 u.d != &(s,u)라는 우리의 가정을 위반할 것이다. 적어도 한 가지 경로가 있기 때문에, s에서 u로 가는 최단 경로 p가 있다. u를 S에 추가하기 전에, 경로 p는 S에 있는 한 정점을 이름 그대로 s는 V - S에 있는 이름 그대로 u인 한 정점에 연결한다. 우리가 첫 번째 정점을 p를 따라 y라고 고려하자. 이것은 y in V - S에 있도록 하기 위해서이다., 그리고 x가 S에 있고 p를 따라 y의 predecessor라고 해보자. 따라서 그림 24.7이 보여주듯이, 우리는 경로 p를 s ->(p1)x -> y ->(p2) u로 분해할 수 있다 (paths p1 or p2 둘 중 하나는 간서을 가지지 않을지도 모른다.)

우리는 u가 S에 추가될 때 y.d = &(s,y)라고 주장한다. 이것을 증명하기 위해서, x in S를 관찰해라. 그러고나서, 우리가 u를 그것이 S에 추가될 때 u.d != &(s,u)인 것을 선택했기 때문에, 우리는 x가 S에 추가 되었을 때 x.d =&(s, x)이다. Edge (x,y)는 그 당시에 relaxed되어졌고, 그 주장은 convergence property를 따른다.

우리는 이제 u.d = &(s,u)를 증명하는 한 모순을 얻을 수 있다. y가 u전에 s에서 u로 가는 최단 경로에 나타났고, 모든 간선 가중치들이 음이 아니기 때문에, 우리는 &(s,y) <= &(s,u)를 가지고, 따라서

y.d = &(s,y)
     <= &s,u)
      <= u.d (by the upper-bound property).

그러나 두 정점 u와 y는 line 5에서 u가 선택될 때 V - S에 있었기 때문에, 우리는 u.d <= y.d를 갖는다. 따라서 두 부등식은 사실 다음을 주능 부등식이다.

y.d = &(s,y) = &(s,u) = u.d.

결과적으로 u.d = &(s,u)이고, 이것은 u의 우리의 선택과 모순된다. 우리는 u가 S에 추가될 때, u.d = &(s,u)라고 결론짓고, 이 부등식이 항상 유지된다고 결론짓는다.

Termination : 종료시에, Q = 0이고, 우리의 이전 invariant를 따라 Q = V - S이고, 이것은 S = V인 것으 암시한다. 따라서, 모든 정점 u in V에 대해 u.d = &(s,u)이다.

Corollary 24.7
만약 양의 가중치 함수 w와 source s를 가진 DAG G = (V,E)에 다익스트라 알고리즘을 작동시킨다면, 그러면 종료시에, 그 predecessor subgraph G_pi는 s를 루트로하는 최단 경로 트리이다.

Proof 정리 24.6과 predecessor-subgraph property로 즉시 증명된다.

Analysis
다익스트라 알고리즘은 얼마나 빠른가? 그것은 세 개의 우선순위 큐 연상늘 호출하여 min-priority queue Q를 유지한다: INSERT (implicit in line 3), EXTRACT-MIN (line 5), and DECREASE-KEY (implicit in RELAX, which is called in line 8). 그 알고리즘은 정점마다 INSERT와 EXTRACT-MIN을 호출한다. 각 정점 u in V는 집합 S에 정확히 한 번씩 추가되기 때문에, 인접리스트 Adj[u]에 있는 각 간선은 알고리즘 과정 동안 정확히 한 번 lines 7-8의 for loop에서 검사된다. 모든 인접리스트들에서 간선들의 총 개수가 |E|이기 때문에, 이 for loop는 총 |E|번 반복하고, 따라서 그 알고리즘은 전반적으로 최대 |E| 번 DECREASE-KEY를 호출한다. (우리가 aggregate analysis를 사용하고 있다는 것을 다시 한 번 관찰해라.)

다익스트라 알고리즘의 작동시간은 우리가 min-priority queue를 어떻게 구현했는지에 의존한다. 처음에 우리가 min-priority queue를 1부터 |V|까지 숫자가 부여된 정점들을 이용하여 유지하는 것을 고려해라. 우리는 간단히 한 배열의 v번째 entry에 v.d를 저장한다. 각 INSERT와 DECREASE-KEY 연산은 O(1)시간이 걸리고, 각 EXTRACT-MIN 연산은 O(V) 시간이 걸린다 (우리가 전체 배열을 통해 탐색하기 때문에), O(V^2 + E) = O(V^2)의 총시간에 대해.

만약 그 그래프가 충분히 sparse하다면, 즉, E = o(V^2/lgV) - 우리는 그 알고리즘을 binary min-heap인 min-priority queue로 구현하여 개선할 수 있다. (Section 6.5에서 이야기 되었듯이, 그 구현은 그 정점들과 대응되는 heap elements들이 서로에 대한 handles을 유지하도록 해야한다.) 각 EXTRACT-MIN 연산은 O(lgV)의 시간이 걸린다. 이전처럼, |V| 개의 그러한 연산들이 있다. binary min-heap을 구성하는 시간은 O(V)이다. 각 DECREASE-KEY 연산은 O(lgV)의 시간이 걸리고, 여전히 최대 |E|개의 그러한 연산들이 있다. 그러므로 그 총 작동 시간은 O((V+E)lgV) 이고, 만약 모든 정점이 source로부터 도달 가능하다면 O(ElgV)이다. 이 작동시간은 간단한 O(V^2) 시간 구현에 대해 개선된다. 만약 E = o(V^2/lgV) 라면.

우리는 사실 Fibonacci heap으로 (see Chapter 19) min-priority queue를 구현하여 O(VlgV + E)의 작동시간을 얻을 수 있다. |V| EXTRACT-MIN 연산의 각각의 그 amortized cost는 O(lgV)이고, 각 DECREASE KEY 호출은, 최대 |E|번 있는, 오직 O(1) amortized time만이 걸린다. 역사적으로, 피보나치힙의 개발은 다익스트라 알고리즘이 일반적으로 EXTRACT-MIN calls보다 DECREASE-KEY calls를 더 하게 되는 관찰에 의해 동기부여 받았다. 이것은 각 DECREASE-KEY 연산을 EXTRACT-MIN의 amortized time을 증가시키는 것 없이 o(lgV)로 줄이는 어떤 방법이 binary heaps보다 asymptotically faster implementation을 만들어내게 하기 위해서이다.

다익스트라 알고리즘은 BFS와 (see Section 22.2) 최소 신장 트리를 연산하는 프림의 알고리즘 (see Section 23.2)를 닮았다. 그것은 집합 S가 BFS에서 있는 검은 정점들의 집합과 대응된다는 점에서 BFS와 같다; S에 있는 정점들은 그것들의 마지막 최단 경로 가중치를 가지고 있기 때문에, 그래서 BFS에서 검은 정점들은 그것들의 올바른 breadth-first distances를 갖는다. 다익스트라 알고리즘은 프림 알고리즘과 같은데, 두 알고리즘이 주어진 집합 (다익스트라의 알고리즘에서 집합 S와, 프림 알고리즘에서 성장하는 트리) 밖에서 "lightest" 정점을 찾기 위해 min-priority queue를 사용하고, 이 정점을 그 집합에 넣고, 그에 따라 집합 밖의 남아 있는 정점들의 가중치를 조절한다는 점에서 같다.





댓글 없음:

댓글 쓰기