Dijkstra (다익스트라)

1. 최단 경로 알고리즘

말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘에는 크게 3가지가 있다. 다익스트라(Dijkstra) 알고리즘, 플로이드-워셜(Floyd-Warshall), 벨만 포드(Bellman Ford) 알고리즘이 있다. 이 중 다익스트라 알고리즘을 알아보자.

 

2. 다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 여러개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 '음의간선' 이 없을 때 정상적으로 작동한다. 

다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류되기도 하는데 그이유는, 매번 '가장 비용이 적은 노드' 를 선택해서 임의의 과정을 반복하기 때문이다.

- 출발 노드를 설정한다.

- 최단거리 테이블을 초기화한다.

- 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.

- 해당 노드를 거쳐 다른노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

- 위 과정에서 3번과 4번 과정을 반복한다.

 

다익스트라 알고리즘은 크게 두가지로 나눌 수 있다.

방법 1. 구현하기에 쉽지만 느리게 동작하는 코드

방법 2. 구현하기에 조금 까다롭지만 빠르게 동작하는 코드

 

코테를 준비하는 나는 방법 2를 정확하게 구현할 수 있어야한다.

 

3. 코드 구현하기

초기상태는 다음과 같다고 가정하자.

노드번호	1	2	3	4	5	6
거리	0	INF	INF	INF	INF	INF

1. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. 처음에는 1번 노드가 선택된다.

 

2. 이제 1번 노드에서부터 갈 수 있는 노드를 확인한다. 2번,3번,4번 노드가 가능하다. 최소 비용은 차례대로 2(0+2), 5(0+5), 1(0+1) 이다. 2,3,4 노드는 모두 INF(무한)으로 초기화 되어 있기때문에 각각의 값이 무한대보다 작으므로 이 비용으로 설정된다. 따라서 다음과 같이 변한다.

노드번호	1	2	3	4	5	6
거리	0	2	5	1	INF	INF

 

3. 이제 다시 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. 지금은 4번 노드가 선택된다. 4번에서 갈 수 있는 노드는 3번과 5번이다. 4번노드를 거쳐서 3번과 5번으로 가는 비용은 차례로 4(1+3), 2(1+1) 이다. 이 값은 기존의 값보다 작으므로 갱신된다.

노드번호	1	2	3	4	5	6
거리	0	2	4	1	2	INF

 

4. 다음에는 2번 노드가 선택된다. 2번 노드를 거쳐서는 3번으로 갈 수 있다. 4번도 갈 수 있는데 4번노드는 이미 방문한 적 있으므로 다시 가지 않는다. 2번을 거쳐 3번노드를 가는 것은 5(2+3) 의 비용이 든다. 이 값은 원래의 값(4) 보다 크므로 갱신되지 않는다.

노드번호	1	2	3	4	5	6
거리	0	2	4	1	2	INF

 

5. 이번에는 5번 노드가 선택된다. 5번에서는 3번과 6번을 갈 수있다. 5번노드를 거쳐 3번노드로 가는 비용은 3(1+2) 이고, 6번노드로 가는 비용은 마찬가지로 4이다. 두 수 모두다 갱신된다.

노드번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

 

6. 3번노드를 선택하고 동일과정을 반복한다.

 

결론적으로 모든 정점을 방문하는 최소비용을 계산 완료했다. 다익스트라 알고리즘을 진행하면서 한 단계당 하나의 노드에 대한 최단 거리를 "확실히 찾게"된다. 

 

4. 다익스트라 알고리즘의 시간복잡도

노드의 개수가 V 일때, 다익스트라 알고리즘은 O(V^2) 의 시간 복잡도를 가진다.

 

다음 글에는 우선순위 큐를 이용한 속도가 빠른 다익스트라 코드를 보자!