다익스트라 알고리즘(Dijkstra)

최단경로(shortest path problem)

- 가중치(방향) 그래프 G=(V,E), 즉 모든 에지에 가중치가 있음

- 경로 p=(v0,v1,...vk)의 길이는 경로상의 모든 에지의 가중치의 합

- 노드 u에서 v까지의 최단경로의 길이를 S(u,v)라고 표시하자.

최단경로문제의 유형

- Single-source(one-to-all) : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라. ex)Dijkstra의 알고리즘

- Single-destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라./ single-source문제와 동일

- Single-pair(one-to-one) : 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라

- All-pairs : 모든 노드 쌍에 대해서 최단 경로를 찾아라.

최단경로의 기본 특성

- 최단 경로의 어떤 부분경로도 역시 최단 경로이다.

■ Single-source 최단경로문제

기본연산 : Relaxation

- 대부분의 single-source 최단경로 알고리즘의 기본 구조

1. 초기화

2. 에지들에 대한 반복적인 relaxation

- 알고리즘들 간의 차이는 어떤 에지에 대해서, 어떤 순서로 relaxation을 하느냐에 있음

기본알고리즘

다익스트라 알고리즘

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

- BFS를 기본으로 한다.

- s로부터의 최단경로의 길이를 이미 알아낸 노드들의 집합 s를 유지.

 맨 처음엔 S={공집합}.

- Loop invariant 

: S에 포함되지 않는 u에 대해서 d(u)는 이미 s에 속한 노드들만 거쳐서 s로부터 u까지 가는 최단경로의 길이

- d(u)가 최소인 노드 u(s에 속하지않고)를 찾고, s에 u를 추가

- s가 변경되었으므로 다른 노드들의 d(v)값을 갱신

d(v) = min{d(v),d(u)+w(u,v)}

즉, 에지(u,v)에 대해서 relaxation하면 Loop invariant가 계속 유지됨

계산복잡성

하나의 노드에 대해 다익스트라 알고리즘을 수행하는 경우를 따져보겠습니다. 미방문노드 가운데 거리가 가장 작은 노드에 BFS를 적용합니다. 거리를 가장 작은 미방문노드를 가려내려면 최악의 경우 노드 전체를 모두 따져봐야 하므로 O(|V|)$)$입니다. 선택된 노드의 모든 이웃노드들에 대해 최단경로 정보를 업데이트합니다. 한 노드당 엣지의 기대값은 |E|/|V|입니다.

다익스트라 알고리즘은 이러한 연산을 전체 노드 수만큼 반복하므로 전체적인 계산복잡성은 O(|V|2+|E|)가 됩니다. 보통의 dense graph는 엣지의 수가 노드 수의 제곱만큼 있으므로 간략하게 계산복잡성을 적으면   O(|V|2)이 됩니다.