Single Source Shortest Path

Single Source Shortest Path에는 Bellman-Ford, DAG, Dijkstra's 알고리즘이 있다.

 

- 1개의 source에 대해서 모든 vertex v로 가는 최단 경로를 찾는 문제이다.

- d[v] = S[s,v] 를 의미한다.

- 초기에 d[v]는 무한대인데 알고리즘을 돌면서 값이 줄어들어 shortest path의 값을 가지게 될 것이다.

- π[v] = 바로 이전 vertex를 의미한다.

- π를 이용해서 shortest-path tree를 만들 수 있다.

 

• 초기화 코드

 

 

모든 V에 있는 vertex까지의 거리를 무한대로 만들어주고 π를 NIL로 초기화해준다.

그리고 시작점인 s의 거리만 0으로 만들어준다.

 

 

 

 

• Relaxation

짧은 길 찾기. 더 짧은 길이 발견되면 바로 환승하는 과정이다.

u는 s와 v 사이에 vertex이고, w는 u와 v 사이의 weight이다.

만일 v까지의 현재 최단 경로 d[v] 보다 d[u]를 거치고 가는게 더 빠르면 relaxation 한다.

 

 

 

---

 

 

Bellman - Ford Algorithm

• 코드

이 알고리즘은 edge weight이 음수여도 가능하다. (negative-weight cycle은 절대 불가)

 

Line 1 : 초기화

Line 2 : |V| - 1 번 반복

Line 3,4 : edge를 하나씩 꺼내가지고 Relaxation

Line 5,6 : 또 edge를 하나씩 꺼내서 Relaxation

Ling 7,8 : Relaxation이 또 되면 negative xycle이 있는 것이기 때문에 False를 반환함

 

=> 이 코드는 모든 edge를 훑는 과정을 |V| - 1 번 반복하기 때문에 Time Complexity는 O(VE) 이다.

 

 

• Example

›

 

 

 

 

---

 

 

DAG

DAG는 Direct Acycle Graph로 방향은 있는데 cychle은 없는 graph를 발한다.

Topological Sort를 이용하여 Bellman-Ford의 V-1번 반복하는 과정을 sorting 후 한 방향으로 relaxationg하면서 한번으로 줄일 수 있다.

Topological Sort는 DFS를 이용하여 모든 vertex의 Finish Time을 다 구한 후에 Finish Time이 큰 순서대로 sorting한다.

 

• 코드

Line 1 -> O(|V|+|E|)

Line 2 -> O(|V|)

Line 4,5 -> O(|E|)

 

=> 이 코드의 Time Complexity는 O(V+E) 이다.

 

 

• Example

0	∞	∞	∞	∞
0	5	7	∞	∞
0	5	7	10	∞
0	5	7	10	16
0	5	7	10	15

 

 

 

---

 

 

Dijkstra's Algorithm

 

negative edge가 없는 경우에만 사용한다. -> 때문에 Bellman-Ford 보다 빠르다.

BFS와 비슷하다 : BFS의 weight이 있는 버전이라고 생각하면된다. BFS를 이용하여 vertex를 priority queue에 넣고 tree를 확장해나간다.

기본적인 design stategy는 Greedy algorithm 이다.

 

• 코드

2개의 Vertex set이 존재해서 S는 최종, Q는 vertex가 담겨져있는 priority queue이다. Q에서 하나씩 꺼내기를 반복하면서 최단거리를 찾고, 꺼낸 vertex를 S에 넣는다.

즉, priority queue에서 하나씩 꺼내면서, 꺼낸 vertex와 근접한 원소를 relaxation 시켜주고 꺼낸 원소를 S에 넣는다.

 

이 코드에서는 priority queue를 구현하는데 걸린 시간이 가장 중요하다.

만약 Binary heap이라면 edge마다 O(lg V)씩 반복하기 때문에 O(E lg V) 가 걸렸을 것이고,

Fibonacci heap이라면 O(V lg V + E) 가 걸렸을 것이다.

 

• Example