Table of Contents
목차
INTRO
다익스트라라는 복잡한 알고리즘을 들어가기전,
관련 기본 개념과 유래를 살펴봄으로써 이해도를 높여보자!
외판원 문제 Travelling Salesman Problem(TSP)
이중에서도 특히 최단 거리를 찾는 문제는 알고리즘 분야에서 유명
- 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 문제
- 즉 최단 거리인 해밀턴 순환을 찾는 문제
- NP-난해 문제로 이론 컴퓨터과학 Theoretical Computer Science 분야의 매우 중요한 문제 중 하나
각 도시의 위치가 표시된 미국 지도가 있다.
각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? (만약 도시가 20개라고 할 때)
- 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 20!
- 20!=2,432,902,008,176,640,000이다.
- 약 240 경 번의 경로를 다녀봐야 가장 짧은 경로를 찾을 수 있음
- 문제는 단순하지만 정답 엄청남
최단 경로(shortest path)
- 그래프는 지도에서 도시를 나타내는 점과 그들 도시 간의 거리를 나타내는 연결선의 값으로 표현됨
- 도시 A에서 도시 B로 가기 위한 방법
1) 첫째, A에서 B로 가는 경로가 있느냐는 점
2) 둘째, A에서 B로 가는 경로가 여러 개 있을 경우 어떤 경로로 가는 것이 가장 짧은 거리인가 하는 점 - 가장 짧은 거리의 경로를 찾는 문제를 최단 경로 문제라 함
- 출발점(source): 주어진 방향 그래프에서 경로의 시작점
- 도착점(destination): 목적지
• 연결선의 값이 두 점 사이의 거리를 나타낼 때, v0가 출발점이라 하면 v0에서 v1까지의 최단 경로는 v0v2v3v1임
• 이때 최단 거리는 10 + 15 + 20 = 45가 됨
• 경로의 길이는 3이지만 v0에서 v1로 직접 가는 거리인 50보다 짧음
• v0에서 각 v1, v2, v3, v4로 가는 최단 경로의 값을 나타냄
다익스트라 알고리즘(Dijkstra algorithm)
- 최단 경로의 거리 문제를 해결할 수 있는 방법
- 시간 복잡도: \(O(N^2)\)
- 우선순위 큐 이용
- 우선순위 큐를 사용 시, 힙에 넣고 뺴는 과정에서 logN의 시간을 사용
- more learn about “Heapq”
- 그리디 알고리즘으로 분류
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
- more learn about Greedy Algorithms
전체 과정
[준비]
- 출발노드 설정하기
- 각 최단거리를 무한대로 초기화
- 방문을 기록하는 체크 테이블을 모두 false로 초기화
[시작]
1) 출발노드를 방문 후 방문 했다고 체크(true)
2) 출발 노드에 연결되어있는 노드들의 최단거리 테이블 갱신
3) 방문 전 노드들 중, 최단거리 테이블의 값이 가장 작은 노드들 선택
4) 더 짧은 거리가 있으면 최단거리 테이블 갱신
[맛보기]
이와 같이 최단경로만 찾는 알고리즘이다
실제 과정
1) 다익스트라 알고리즘은 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.
- S: 방문한 노드 기록
- Min: 노드들 중 최단 노드
- Infinity: 방문하지 않은 노드들 이기 때문에 무한대로 초기화
- 예시에선 노드 1, 즉 D[1]을 시작점으로 잡음
2) 루프를 돌려 이웃노드를 방문하고 거리를 계산
- D[1]에서 갈 수 있는 노드들의 최단 길이를 기록
- 여기선 경우의 수가 1개 밖에 없으니 노드 1과 연결괴어 있는 노드들만 기록
- S: 노드 1을 방문했으니 s{1}
- D[3]: 아직 방문 안했으니 Infinity
3.1) 첫 루프 이후 최단거리 루프를 찾아가며 업데이트 ①
- Min = 2: 방문하지 않은 노드 중, 위에서 가장 가까운 노드가 D[2] = 10 이었음
- D[3]: D[2]를 통해서 갈 수 있다
- D[2]+D[3] = 10+50 = 60
3.2) 첫 루프 이후 최단거리 루프를 찾아가며 업데이트 ②
- Min = 4: 방문하지 않은 노드 중, 위에서 가장 가까운 노드가 D[4] = 30 이었음
- 업데이트
- D[3]: D[2]를 통해서 가는 것 보다 D[4]를 통해서 가는게 더 빠름
- D[4]+D[3] = 30+20 = 50
- D[5]: D[1]를 통해서 가는 것 보다 D[4]를 통해서 가는게 더 빠름
- D[4]+D[5] = 30+60 = 90
- D[3]: D[2]를 통해서 가는 것 보다 D[4]를 통해서 가는게 더 빠름
3.3) 첫 루프 이후 최단거리 루프를 찾아가며 업데이트 ③
- Min = 3: 방문하지 않은 노드 중, 위에서 가장 가까운 노드가 D[3] = 50 이었음
- 업데이트
- D[5]: D[3]를 통해서 가는 것 보다 D[4]를 통해서 가는게 더 빠름
- D[3]+D[5] = 50+10 = 60
- D[5]: D[3]를 통해서 가는 것 보다 D[4]를 통해서 가는게 더 빠름
3.4) 첫 루프 이후 최단거리 루프를 찾아가며 업데이트 ④
- Min = 5: 방문하지 않은 노드 중, 위에서 가장 가까운 노드가 D[3] = 50 이었음
- 여기선 남은게 얘밖에 없음
- 업데이트 할 것 없음
- 확정된 노드
구현
수도 코드
function Dijkstra(Graph, Source):
dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined
create vertex set Q //노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작
for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화
if v ≠ source: // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)
dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 ( 모든 노드들을 초기화하는 값)
prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화
add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가
//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로!
u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거
for each neighbor v of u: // U의 이웃노드들과의 거리 측정
alt ← dist[u] + length(u, v) // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
//= source to U + V to U = source to U
if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈
return dist[], prev[] //계산된 거리값과 목적지를 리턴
출처: 위키피디아
파이썬 구현
import sys
def dijkstra(K, V, graph):
##### 전체 과정 중 [준비] 과정 #######
INF = sys.maxsize
# s는 위의 표와 같이 방문 노드 기록하는 변수
s = [False] * V # 처음은 모두 false로 초기화
# d는 memoization을 위한 array이다. d[i]는 정점 K에서 i까지 가는 최소한의 거리가 저장되어 있다.
d = [INF] * V # 처음은 infinity로 초기화
d[K - 1] = 0
##### 전체 과정 중 [실제] 과정 #######
while True:
m = INF
N = -1
# 방문하지 않은 노드 중 D[]값이 가장 작은 값, 즉 Min을 선택해 그 노드의 번호를 N에 저장
for j in range(V):
if not s[j] and m > d[j]:
m = d[j]
N = j
# 방문하지 않은 노드 중 현재 K 정점과 가장 가까운 노드와의 거리가 INF 라는 뜻은
# 방문하지 않은 남아있는 모든 노드가 A에서 도달할 수 없는 노드라는 의미이므로 반복문을 빠져나간다.
if m == INF:
break
# N번 노드를 '방문'한다.
# '방문'한다는 의미는 모든 노드를 탐색하며 N번 노드를 통해서 가면 더 빨리 갈 수 있는 노드가 있는지 확인 후,
# 더 빨리 갈 수 있다면 해당 노드(노드의 번호 j라고 하자)의 d[j]를 업데이트
s[N] = True
for j in range(V):
if s[j]: continue
via = d[N] + graph[N][j]
if d[j] > via:
d[j] = via
return d
if __name__ == "__main__":
#V는 vertex이고 E는 edge
V, E = map(int, input().split())
#K는 출발노드 입력받음
K = int(input())
INF = sys.maxsize
#그래프를 그려놓는다
graph = [[INF]*V for _ in range(V)]
#좌표입력
for _ in range(E):
u, v, w = map(int, input().split())
graph[u-1][v-1] = w
#다익스트라 알고리즘 실행
for d in dijkstra(K, V, graph):
print(d if d != INF else "INF")