- Dijkstra의 알고리즘은 V에서부터 다른 모든 정점들까지 증가하는 거리의 순으로 최단 경로를 찾을 수 있다. 이 알고리즘은 팡의 최소 스패닝 트리 알고리즘에서처럼 정점 V에서 시작하여 새로운 정점들로 도달하는 특정한 에지들을 선택하면서 분기해 나간다. 또한 항상 가장 가까운 거리를 갖는 정점으로의 에지를 선택한다. 그리고, 각 인접 정점에 대해 오직 하나의 후보 에지만을 추적한다.
예를 들어, 어떤 회사에서 1000만원짜리 기계와 100만원짜리 기계중에 하나를 꼭 구입해야 하는 상황에 빠져 있을 때, Greedy는 말그대로 가장 싼것을 택하는 것이다. 1000만원짜리 기계를 써서 1억원이 넘게 벌수 있고, 100만원짜리를 써서, 10만원도 벌지 못한다 하더라도, 우선 뒤를 생각하지 않고 무조건 지금 상황에서의 최적만을 찾는 것이다. 그런 의미에서 Greedy라는 알고리즘은 항상 최적해를 뽑아내지 못하는 경우가 많다. 따라서, Greedy방법으로 최적해를 해결하고자 할 때 사용되는 선택규칙이 궁극적으로 최적해를 구해낸다는 것에 대한 증명이 반드시 뒷받침 되어야 한다.
Dynamic이라는 것은 Divide and Conquer의 반대말이다. Divide and Conquer는 큰 문제를 먼저 작은 문제들로 분할하고 각각 해결해나가는 것인데 반해, Dynamic은 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 똑같은 계산을 반복하는 대신, 그 저장한 결과를 이용하는 방식이다. 따라서 메모리가 많이 필요하다는 것이 Dynamic의 단점이다.
-----------------------------------------------------------------------------------------------------
다익스트라 알고리즘(Dijkstra algorithm)은 네덜란드의 컴퓨터과학자 에츠허르 다익스트라의 이름을 딴, 어떤 간선도 음수 값을 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.
예를 들어, 그래프의 점들이 각각 도시를 나타내고, 연결선들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 다익스트라 알고리즘은 임의의 두 도시 사이의 최단 경로를 찾는다.
다익스트라 알고리즘은 방향이 주어진 가중 그래프(weighted graph) G와 출발점 s를 입력으로 받는다. 그래프 G의 모든 점들의 집합을 V라 하고, 그래프의 간선을 간선의 출발점 u와 도착점 v의 쌍 (u, v)로 표현한다. G의 모든 간선들의 집합을 E라 하고, 간선들의 가중치는 함수 w: E → [0, ∞]로 표현한다. 이때 가중치 w(u, v)는 점 u에서 점 v로 이동하는 데 드는 비용(시간, 거리 등)이 된다. 경로의 비용은 경로 사이의 모든 간선들의 가중치의 합이 된다. 다익스트라 알고리즘은 V의 임의의 점의 쌍 s와 t가 있을 때 s에서 t로 가는 가장 적은 비용이 드는 경로(최단 경로)를 찾는다. 이 알고리즘은 주어진 출발점 s로부터 다른 모든 점까지의 최단 경로를 계산하는 데도 사용할 수 있다.
목차[숨기기] |
[편집] 알고리즘의 개요
다익스트라 알고리즘은 각각의 점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 이 값은 s에 대해서는 0이고, (d[s]=0) 다른 모든 점에 대해서는 무한대(∞) 값으로 놓아 다른 점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
다익스트라 알고리즘은 이완(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지의 링크 (u, v)가 존재할 때, s에서 v까지의 최단경로는 u까지의 최단경로에 에 링크 (u, v)를 연장함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.
이완 연산은 모든 간선 (u, v)에 대해 한번씩 이완이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다.
알고리즘은 과정이 끝날 때까지 점의 집합 S와 Q를 저장한다. S는 d[v]가 최단 경로의 비용임이 이미 알려진 점 v의 집합이고 Q는 나머지 점들의 집합을 가리킨다. S는 공집합에서 시작하여 매 단계마다 Q에서 S로 점들이 하나씩 옮겨 오며, 이때 옮겨 오는 점들은 d[u]가 가장 낮은 값을 갖는 점 u로 정해진다. u가 S로 옮겨 오면, 알고리즘은 u에서 시작하는 모든 간선에 대해 이완 연산을 행한다.
[편집] 수도코드
아래 알고리즘에서 u := Extract_Min(Q)는 점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // 초기화
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set // 알고리즘의 실행
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[v] > d[u] + w(u,v) // (u,v)의 이완
13 d[v] := d[u] + w(u,v)
14 previous[v] := u
만약 모든 v에 대해서가 아니라 특정한 s에서 v까지의 최단 거리만을 알고 싶다면 9번째 행에서 u = t 일때 종료하면 된다.
s에서 t까지의 최단 경로는 다음과 같이 얻을 수 있다.
1 S := empty sequence 2 u := t 3 while defined u 4 insert u to the beginning of S 5 u := previous[u]
이제 S는 s에서 t까지의 최단경로 상에 있는 점들의 목록이 된다.
[편집] 실행 시간
m개의 간선과 n개의 점을 가진 그래프에 대해 대문자 O 표기법으로 다익스트라 알고리즘의 실행시간을 나타낼 수 있다.
가장 간단한 구현으로, Q의 집합을 연결 리스트나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현했을 때 실행 시간은 O(n2) 시간이 된다.
만약 희소 그래프(sparse graph), 즉 n2보다 훨씬 작은 개수의 간선만을 갖는 그래프에 대해서는, 인접 리스트(adjacency list)와 바이너리 힙 또는 피보나치 힙으로 구현한 우선순위 큐(priority queue)를 이용해 다익스트라 알고리즘을 더 효율적으로 구현할 수 있다. 바이너리 힙을 이용하면 실행 시간은 O((m+n)log n) 시간이 되고, 피보나치 힙을 통해 O(m + n log n) 시간까지 개선할 수 있다.
[편집] 관련된 문제와 알고리즘
인터넷 라우팅에서 사용되는 OSPF(Open Shortest Path First) 방식의 프로토콜은 다익스트라 알고리즘이 실제 현장에서 사용되는 좋은 사례이다.
그래프의 가중치가 음수가 아니라고 가정하는 다익스트라 알고리즘과는 달리, 벨만-포드 알고리즘은 음수 가중치를 갖는 그래프에 대해서도 정확하게 동작한다. (단, 그래프에 음수 값을 갖는 순환 경로가 존재하지 않을 때)
목적지까지의 '거리'를 추정할 수 있는 방법이 있을 때, 다익스트라 알고리즘의 변형인 A* 알고리즘은 탐색해야 할 그래프의 크기를 줄이는 방법으로 더 빠르게 경로를 찾을 수 있다.
[출처] 다익스트라 알고리즘(Dijkstra algorithm) - 위키백과|작성자 덱이