최단경로 - 2

bellman-ford 알고리즘 예시

 

- bellman-ford 알고리즘은 시간복잡도 측면에서 효율적이지 않음 => o(nm)

- 알고리즘을 한번 실행할 때마다 오른쪽 부분에서는 불필요한 계산이 계속 일어남

- v이전에 노드들을 다 갱신한 후 v의 오른쪽 부분을 갱신하면 불필요한 계산을 줄일 수 있음 => Dijkstra 알고리즘

 

Dijkstra 알고리즘

 

- distance가 제일 적은 노드를 기준으로 그 노드와 연결된 노드의 distance를 구한다.

- 처음 distance가 0인 노드를 시작한다.

- distance가 0 인부분은 다신 안봐도 되므로 오른쪽 부분에서만 가장 작은 distance를 찾는다

- distance가 5인 노드가 제일 작으므로 이 노드를 기준으로 연결된 노드들의 distance를 구한다.

- 이제 다음으로 작은 값은 7이므로 7을 기준으로 반복하면 된다.

 

Dijkstra 알고리즘 설명

- 음수 가중치가 없다고 가정

- s로부터의 최단경로의 길이를 이미 알아낸 노드들의 집합 S를 유지. 맨 처음엔 S={}

- Loop invariant : 이미 S에 속한 노드들만 거쳐서 s로부터 u까지 가는 최단경로의 길이

정리 : d(u)가 s영역에서 거리가 제일 작은 값이라면 u로 가는게 최단경로의 길이다.

- u를 s영역에 포함시킨다 그리고 s영역이 변했으므로 v의 d[v]를 수정해줘야 한다.

- 이때, 새롭게 들어온 u를 거쳐서 오는것과 원래 d[v]를 비교했을 때 u를 거쳐오는 것이 더 작다면 d[v]의 값을 바꿔준다.

따라서, 에지 (u,v)에 대해서 relaxation하면 Loop Invariant가 계속 유지된다.

 

수도코드-1

수도코드-2 : 시간복잡도 o(mlogn)

시간복잡도 

- prim의 알고리즘과 동일함

- 우선순위 큐를 사용하지 않고 단순하게 구현할 경우 o(n^2)

- 이진힙을 우선순위 큐로 사용할 경우 o(nlogn + mlogn) = o(mlogn)

- Fibonacci Heap을 사용하면 o(nlogn+m)에 구현가능

 

**위의 그림들은 '영리한 프로그래밍을 위한 알고리즘 강좌'에서 가져왔습니다.