공부/알고리즘2011. 7. 13. 22:33


Properties of shortest paths

vertax u에서 v로 최소 weight로 가는 path
shortest path의 sub path도 shortest path이다.

Triangle inequality
δ(u, v) ≤δ(u, x) + δ(x, v).
거쳐서 가면 길어진다.

그래프가 음수 weight를 갖는 cycle이 있다면 some shortest paths는 존재하지 않을지도 모른다.
사이클 돌면서 weight가 계속 작아질 수 있으니까 말이다.

Single-source shortest paths

하나의 vertex s∈V가 모든 vertex v ∈ V에 대해 shortest path를 찾기.
만약 모든 edge가 음수가 아니라면 모든 shortest-path weight는 존재한다.
Greedy로 보여줄게.
vertex s부터 시작해서 각 단계마다 s에서 최소로 갈 수 있는 vertex v를 선택해서 s가 속한 집합에 넣는다.
v에 인접한 vertex들의 거리를 수정한다.

Dijkstra’s algorithm

우선순위큐를 가지고 있다. 큐안에는 아직 s로부터 가장 짧은 거리가 정해지지 않은 vertex들이 있다.
큐에 있는 모든 vertex가 시작 vertex s가 속한 집합 S에 포함될 때까지
큐에서 최소값(u)을 뽑아서 S에 포함시킨다.
u의 인접 vertex(v)들에 대해서 u를 통해서 v로 가는 게 원래 가는 방법보다 더 가깝다면 바꿔준다.
우선순위큐의 값이 바뀌게되어서 다시 min heap을 만들어 준다.

Correctness

Greedy라서 맞는지 검증을 해야 한다.
증명 생략

Analysis

 출처 : Introduction to Algorithm
 
모든 edge의 weight가 1이라면 어떻게 될까?
우선순위 큐 대신에 FIFO 큐를 쓸 수 있다.
Breadth-first search와 같다.
O(V+E)


Bellman-Ford algorithm

vertex s∈V 로부터 모든 v∈V에 대한 shortest-path lengths를 찾거나 아니면 negative-weight cycle이 존재하는지 알아내는 방법.

알고리즘
초기화하고, |V|-1 번 모든 edge들을 relax한다. (모든 edge를 relax하고 나면 vertex 하나씩 최소 거리가 정해진다. 가장 긴 simple path는 최대 |V|-1번이다.) 
다 하고 나서 다시 모든 edge (u,v)에 대해서 d[v] > d[u] + w(u,v)가 있는지 찾는다. 음수 사이클이 없으면 d[u]가 최소값이 되어야 된다.
O(VE)

'공부 > 알고리즘' 카테고리의 다른 글

Minimum spanning tree (최소신장트리)  (0) 2011.07.13
Elementary Graph Algorithms  (0) 2011.07.13
Data Structures for Disjoint Sets  (0) 2011.07.11
Greedy Algorithms  (0) 2011.07.11
Dynamic Programming  (0) 2011.07.09


Posted by skyjumps