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

Dijkstra Algorithm :

Dynamic programming을 이용한 대표적인 최단경로(Shortest path) 탐색 알고리즘. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 이 때 음의 Edge는 포함할 수 없음(현실 세계에선 음의 Edge가 존재 하지 않기 때문에 다익스트라는 현실에서 사용하기 매우 적합함). / 음의 가중치가 없는 그래프의 한 정점(vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 / 에츠허르 다익스트라 라는 사람이 고안한 알고리즘이라함. / 그래프 방향의 유무는 상관없으나 간선(Edge)들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없음. 음의 가중치를 가지는 간선이 있으며 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용. / 그래프 내에 가중치의 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단경로는 구성할 수 없음. / 다익스트라 알고리즘이 하나의 노드로부터 최단경로를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘이다. / 다익스트라 알고리즘을 확장시킨 알고리즘 = A*(에이스타)알고리즘

다익스트라의 원래 알고리즘은 두 꼭짓점간의 가장 짧은 경로를 찾는 알고리즘이지만, 일반적인 변형은 한 꼭짓점을 소스 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 최단 경로 트리 만드는 알고리즘.

다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유 '최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문'. -> 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있음. 기본적으로 다익스트라는 하나의 최단거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용함. 

 

작동 과정 :

1. 출발 노드 설정

- 모든 꼭짓점을 미방문 상태로 표시. 미방문 집합이라는 모든 미방문 꼭짓점의 집합을 만든다.

2. 출발 노드를 기준으로 각 노드의 최소 비용 저장

- 모든 꼭짓점에 시험적 거리 값을 부여. 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정함. 초기점을 현재 위치로 설정.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택

- 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 시험적 거리를 현재 꼭짓점에서 계산. 새로 계산한 시험적 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. (예를 들어, 현재 꼭짓점 A의 거리가 6이라고 표시되있고, 인접 꼭짓점 B로 연결되는 변의 길이가 2라고 한다면, A를 통한 B까지의 거리는 6+2=8이 된다. 이전의 B까지의 거리가 8보다 컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둠) -> 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신

4. 만약 현재 꼭짓점에 인접한 모든 미방문 꼭짓점까지의 거리를 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 미방문 집합에서 제거. 방문한 꼭짓점은 이후에는 다시 방문하지 않음.

5. 두 꼭짓점 사이의 경로를 찾는 경우 - 도착점이 방문한 상태로 표시되면 멈추고 알고리즘 종료.

완전 순회 경로를 찾는 경우 - 미방문 집합에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면 이는 출발점과 미방문 집합 사이에 연결이 없는 경우이므로 멈추고 알고리즘 종료.

아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 "현재 위치"로 선택하고 3번으로 되돌아감.

 

모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데, 이때 제대로 구현된 우선순위 큐를 활용한다면 비용을 줄일 수 있음.

 

사용 예 :

인공위성 GPS 소프트웨어, 도로 교통망, 큐브 풀기, 네비게이션, 미로 탐색 등