[Algorithm Part 2] 4. Shortest Paths

이번 글에서는, weighted digraph의 대표 문제인 최소 경로 문제에 대해 살펴볼 것이다.

weighted digraph가 주어졌을 때, edge v에서 edge w까지의 최소 경로를 찾는 문제다.

수많은 문제가 최단 경로 문제로 재구성될 수 있기에, 꼭 집고 가야 하는 문제다.

---

Shortest path variants

1. Source-sink: from one vertex to another (1-to-1)
2. Single-source: from one vertex to every other (1-to-N)
3. All pairs: between all pairs of vertices (N-to-N)

본문에서는, single-source 문제에 대해서만 살펴보겠다.

Weighted digraph representation

digraph와 동일하다. 다만, edge의 가중치 값을 추가로 저장해야 한다.

• Diraph: if v→w exists, then adj[v][w] = true (or adj[v].append(w))
• Weighted Digraph: if v→w exists, then adj[v][w] = weight (or adj[v].append((w, weight)))

---

Shortest-path properties

1. s에서 v까지의 최소 경로가 $(s=w_1, w_2, \cdots, w_k=v)$일 경우,
   s에서 $w_i$의 최소 경로는 $(s=w_1, w_2, \cdots, w_i)$가 된다. 즉, 최소 경로의 하위 경로도 최소 경로다.
   $(s=w_1, w_2, \cdots, w_i)$보다 짧은 경로가 존재 시, $(s=w_1, w_2, \cdots, w_k=v)$가 최소 경로가 아니기 때문이다.
2. 순환 시, 경로가 길어지기 때문에, 최소 경로에는 순환이 없다.

2가지 특성에 의해, s에서 모든 v까지의 최소 경로를 spanning tree로 표현할 수 있으며,
이를 Shortest-path tree (SPT)라고 표현한다.

 

SPT를 2개 배열로 표현할 수 있다.

1. distTo[v]: length of shortest path from s to v
2. edgeTo[v]: last edge on shortest path from s to v

더 나아가, SPT는 unique하지 않다. 즉, 여러 가지 SPT가 나올 수 있다.

---

Shortest-paths optimality conditions

distTo[v]가 s에서 v까지의 최소 경로 길이가 되기 위한 필요충분조건:

1. distTo[v]는 s에서 v까지의 모든 경로 중 한 경로 길이다.
2. 각 edge $e$(=w→v)에 대해, distTo[v] ≤ distTo[w] + e.weight다.

명제1은 distTo[v]의 전체집합(=s에서 v까지의 모든 경로 길이)을 의미하며,

명제2는 전체집합 중 특정 조건(=distTo[v] ≤ distTo[w] + e.weight)을 만족하는 부분 집합을 의미한다.

Proof

A = distTo[v]는 s에서 v까지의 최소 경로 길이다.

B =  각 edge $e$(=w→v)에 대해 distTo[v] ≤ distTo[w] + e.weight이다.

 

1. A → B (~B → ~A)

임의의 edge $e$(=w→v)에 대해 distTo[v] > distTo[w] + e.weight이면, 

distTo[v]는 최소 경로 길이가 아니다.

distTo[v]보다 길이가 짧은 경로(=w를 통한 경로)가 존재하기 때문이다.

 

2. B→ A

s에서 v까지의 최소 경로가 $s = w_0  \rightarrow w_1 \rightarrow \cdots \rightarrow w_k = v$라고 가정하자.

 

그럼 B 명제로 인해,

1. $\text{distTo}[w_{i+1}] \le \text{distTo}[w_i] + \text e_{i+1}\text{.weight}$ ($\text e_{i+1}\text{.weight}$ = shortest edge $w_i \rightarrow w_{i+1}$)
2. $\text{distTo}[v] = \text{distTo}[w_k] \le \text e_1\text{.weight} + \text e_2\text{.weight} + \cdots + \text e_k\text{.weight}$
3. "distTo[v]는 s에서 v까지의 최소 경로 길이보다 작거나 같아"야 한다.

distTo[v]는 "s에서 v까지의 모든 경로 중 하나의 경로 길이"이여야 하므로,
distTo[v]는 s에서 v까지의 최소 경로 길이보다작을 수 없다.

결론: distTo[v]는 s에서 v까지의 최소 경로 길이다.

---

Generic shortest-paths algorithm

1. distTo[s] = 0, distTo[v] = ∞로 초기화한다.
2. optimality conditions을 충족할 때까지, edge relaxation 연산을 한다.

Edge relaxation

현재 방문한 edge $e$(=v→w)가 더 짧은 경로를 제공(=distTo[w] > distTo[v] + e.weight)한다면,

다음과 같이, distTo[w]와 edgeTo[w]를 수정한다. (distTo[w] =distTo[v] + e.weight, edgeTo[w] = v)

 

edge relaxation 연산은 optimality condition에 맞게 수정해주는 연산이다.

Correctness of algorithm

edge 개수가 유한할 경우, 유한 번의 edge relaxation 연산으로, optimality conditions을 충족시킬 수 있다.

즉, distTo가 최소 경로 길이가 된다.

distTo[v]와 "edgeTo로 만든 s에서 v까지의 경로 길이"가 같기 때문에, edgeTo는 SPT를 의미한다.

---

Dijkstra's algorithm

1. distTo[s] = 0, distTo[v] = ∞로 초기화한다.
2. non-tree vertices 중 distTo가 가장 낮은 vertex v를 선택해, SPT에 삽입한다. (by PQ)
3. v의 모든 edge $e$(=v→w)에 relax 연산을 적용한다. (update)
4. 모든 vertex가 SPT에 삽입될 때까지, 2 ~ 3번을 반복한다.

Correctness of algorithm

"모든 vertex w가 optimality condition(distTo[w] ≤ distTo[v] + e.weight)을 충족함"을 증명하면 된다.

Dijkstra's algorithm은 모든 edge $e$(=v→w)를 한 번씩 방문하는데, 방문할 때만 relax 연산을 수행한다.

부등식 관계(distTo[w] ≤ distTo[v] + e.weight)는 알고리즘이 끝날 때까지 유지된다. 이유는 다음과 같다.

알고리즘이 끝날 때까지, (relax 연산에 의해) distTo[w]는 증가하지 않고, (감소할 수는 있다.)
(s에서 v까지의 최소 경로 길이를 구한 후에, edge $e$를 방문했기에) distTo[v]는 안 변한다.

Prim's algorithm vs Dijkstra's algorithm

둘 다 spanning tree를 계산하는 알고리즘이다.

차이점은 다음 vertex 선정 방법이다.

• prim's algorithm은 트리에서 가장 가까운 vertex를 선정한다.
• dijkstra's algorithm은 source vertex s에서 가장 가까운 vertex를 선정한다.

Dijkstra's algorithm은 non-negative weighted digraph에서만 사용가능하다.

---

Weighted DAGs

Weighted DAGs는 cycle이 없기 때문에 최소 경로를 보다 빠르게 구할 수 있다.

(Weighted DAGs = Weighted digraph which has no cycles)

Algorithm

1. Topological sort로 vertices를 정렬한다.
2. 정렬된 순서대로, vertex v를 pop한 후, SPT에 삽입한다.
3. v의 모든 edge $e$(=v→w)에 relax 연산을 적용한다.
4. 모든 vertex가 SPT에 삽입될 때까지, 2 ~ 3번을 반복한다.

Correctness of algorithm

Dijkstra's algorithm와 증명 과정이 동일하다.

---

Application: seam carving

왜곡 없이 사진 크기 조정하는 문제다.

Modeling (or Abstract)

사진을 Weighted DAGs로 다음과 같이 추상화(abstraction)한다.

• vertex = pixel
• edge = from pixel to 3 downward neighbors
• weight of pixel = energy function of 8 neighboring pixels (정확히 뭔지 모르겠다..)

top-level vertex(=s)에서 bottom-level vertex(=v)까지의 최소 경로(sum of weight)를 구한 후,

최소 경로에 해당하는 pixel을 삭제한다.

---

Longest paths in weighted DAGs

최대 경로 문제는 weight의 부호를 바꾸어 최단 경로 문제로 recast할 수 있다.

Algorithm

1. 모든 vertices의 weight의 부호를 바꾼다.
2. 최단 경로 algorithm을 사용한다.

---

Application: parallel job scheduling 

작업 시간과 우선 순위 제약이 있는 일련의 작업이 있을 때, 모든 작업을 처리하는 최단 시간을 계산하는 문제다.

Modeling (or Abstract)

위 문제를 Weighted DAGs으로 다음과 같이 추상화(abstraction)한다.

• source vertex와 sink vertex를 그래프의 맨 앞 뒤에 배치시킨다.
• 각 작업마다, 2개 vertex를 만든다. (1. begin vertex, 2. end vertex)
• 각 작업마다, 3개 edge를 만든다. (1. begin→ end, 2. source → begin, 3. end → sink)
• 우선 순위 제약에 대한 edge를 만든다.

source vertex에서 sink vertex까지의 최대 경로(=optimal job scheduling)를 구한 후,

최대 경로 길이를 반환한다.

---

Negative weights

Dijkstra's algorithm은 non-negative weighted digraph에서만 사용가능하다.

그렇기 때문에, negative weighted digraph의 최단 경로를 구할 수 있는 알고리즘이 필요하다.

Definition

Negative cycle is directed cycle whose sum of edge weights is negative.

Proposition

A SPT exists iff no negative cycles.

순환 시 경로가 짧아지기에, 최소 경로가 cycle에 갇혀 트리가 존재 하지 않는다.

 

더 나아가, negative cycle이 존재하는 graph의 최단 경로 문제는 현재까지 intractable하다.

Bellman-Ford algorithm

1. distTo[s] = 0, distTo[v] = ∞로 초기화한다.
2. 모든 edge e(=v→w)에 relax 연산을 적용한다.
3. 2번을 V번 반복한다.

Practical Improvement

i번째 반복에서 distTo[v]가 변하지 않을 경우,

i+1번째 반복에서 edge $e$(=v→w)에 relax 연산을 하지 않아도 된다.

i번째 반복에서 distTo[]가 변한 vertices를 저장하여, 연산 횟수를 줄일 수 있다.

---

Performance

algorithm	restriction	typical case	worst case	extra space
Topological sort	no directed cycles	E + V	E + V	V
Dijkstra	no negative weights	$E\log V$	$E\log V$	V
Bellman-Ford	no negative cycles	EV	EV	V
Bellman-Ford improve		E + V	EV	V

---

Finding a negative cycle

만약 negative cycle이 존재할 시, Bellman-Ford agorithm은 negative cycle에 갇힌다.

Proposition

Bellman-Ford agorithm의 V번째 반복에서, distTo[]가 수정될 때 "negative cycle이 존재함"을 알 수 있다.

negative cycle이 존재할 때, edgeTo[]로 cycle를 찾을 수 있다.

---

Application: arbitrage detection

환율 테이블이 주어졌을 때, 차익 기회(=arbitrage opportunity) 존재 여부를 찾는 문제다.

Modeling (or Abstract)

환율 테이블을 Weighted DAGs으로 다음과 같이 추상화(abstraction)한다.

• vertex = currency (e.g., $, ₩)
• edge = transaction (e.g, $ → ₩)
• weight = $-\ln(\text{exchange rate from currency v to w})$

 

Weighted Graph의 negative cycle 존재 여부를 찾는다.