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

Dijkstra Algorithm 음의 가중치가 없는 그래프의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.

 

- 다익스트라 알고리즘의 최단 경로 문제 해결 과정

 

노드(Node) : 0번 ~ 6번

링크(Link) : 각 노드를 연결하는 선

비용(Cost) :링크 위에 표시된 숫자, 해당 링크를 지나갈때에 소요되는 경비, 비용

 

다익스트라 알고리즘을 통해 0번 노드를 시작접으로 1~6번 노드를 목적지로 하는 최단 경로 6개를 구하는 과정

S : 이미 처리가 완결된 노드의 집합

- 시작 노드인 0번 부터 처리를 시작

D : 0번 ~ 6번 노드에 대한, 시작노드로부터의 소요되는 비용

- 0번 -> 1번 노드 비용 : 5 // 0번 -> 3번 노드 비용 : 1

T : 해당 노드로 가는데 연결된 노드의 번호

- 상단 : 노드 번호 // 하단 : 연결된 노드 번호

 

S 집합에 3번 노드 추가

- D 저장소에 3번 노드에 대한 비용값이 가장 최소이기 때문

3번 노드와 링크로 연결된 2번 노드와 5번 노드에 대한 비용값을 계산

- D 저장소에 기록

시작 노드 0번 노드로부터 2번 노드까지 소요되는 비용 : 3

- 0번 -> 3번 -> 2번 이동 루트에 있는 비용값의 합 = 1 + 2 = 3

시작 노드 0번 노드로부터 5번 노드까지 소요되는 비용 : 2

- 0번 -> 3번 -> 5번 이동 루트에 있는 비용값의 합 = 1 + 1 = 2

 

S 집합에 5번 노드 추가

- 이미 처리가 완료된 노드 이외의 노드 중 5번 노드의 비용이 2로 최소이기 때문

- S 집합에 존재하는지 확인하여 이미 처리가 완료된 노드인지 확인

5번 노드와 링크로 연결된 2번 노드, 3번 노드, 6번 노드에 대한 비용값을 계산

- 2번 노드 : 2 + 2 = 4 (전 단계에서 계산된 비용값 3보다 크므로 무시)

- 3번 노드 : 이미 처리 완료

- 6번 노드 : 2 + 3 = 5 (D 저장소에 기록)

 

S 집합에 2번 노드 추가

- 이미 처리가 완료된 노드 이외의 노드 중 2번 노드의 비용이 2로 최소이기 때문

2번 노드와 링크로 연결된 1번 노드, 3번 노드, 5번 노드, 6번 노드에 대한 비용값을 계산

- 1번 노드 : 3 + 1 = 4 (전 단계에서 계산된 비용값 5 보다 작으므로 D 저장소 값을 변경)

- 3번 노드 : 이미 처리 완료( S 집합 포함 )

- 5번 노드 : 이미 처리 완료( S 집합 포함 )

- 6번 노드 : 3 + 8 = 11 (전 단계에서 계산된 비용값 5보다 크므로 무시)

 

S 집합에 1번 노드 추가

- 이미 처리가 완료된 노드 이외의 노드 중 1번 노드의 비용이 최소이기 때문

1번 노드와 링크로 연결된 0번 노드, 2번 노드, 4번 노드에 대한 비용값을 계산

- 0번 노드 : 이미 처리 완료( S 집합 포함 )

- 2번 노드 : 이미 처리 완료( S 집합 포함 )

- 4번 노드 : 4 + 3 = 7 (D 저장소에 기록)

S 집합에 6번 노드 추가

- 이미 처리가 완료된 노드 이외의 노드 중 6번 노드의 비용이 최소이기 때문

6번 노드와 링크로 연결된 1번 노드, 2번 노드, 4번 노드, 5번 노드에 대한 비용값을 계산

- 1번 노드 : 이미 처리 완료( S 집합 포함 )

- 2번 노드 : 이미 처리 완료( S 집합 포함 )

- 4번 노드 : 5 + 1 = 6 (전 단계에서 계산된 비용값 7 보다 작으므로 D 저장소 값을 변경)

- 5번 노드 : 이미 처리 완료( S 집합 포함 )

 

S 집합에 4번 노드 추가

- 유일하게 처리되지 않은 노드

4번 노드와 링크로 연결된 1번 노드, 6번 노드에 대한 비용값을 계산

- 1번 노드 : 이미 처리 완료( S 집합 포함 )

- 6번 노드 : 이미 처리 완료( S 집합 포함 )

-> 더이상 진행하지 않고 종료

 

T 저장소를 통해 출발 노드인 0번 노드에서 각 노드에 대한 최단 경로 파악

 

1. 0번 노드에서 1번 노드 : (1번 노드)←(2번 노드)←(3번 노드)←(0번 노드)
2. 0번 노드에서 2번 노드 : (2번 노드)←(3번 노드)←(0번 노드)
3. 0번 노드에서 3번 노드 : (3번 노드)←(0번 노드)
4. 0번 노드에서 4번 노드 : (4번 노드)←(6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)
5. 0번 노드에서 5번 노드 : (5번 노드)←(3번 노드)←(0번 노드)
6. 0번 노드에서 6번 노드 : (6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)

 

 

- 수도 코드

 

 

- 시간 복잡도

• n 개의 정점(node)이 있다고 했을 경우
• 주 반복문을 n번 반복하고
• 내부 반복문을 2n 번 반복하므로
• O(n^2) 의 시간복잡도를 가진다.