| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
Dijkstra Algorithm그래프의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.
에츠허르 다익스트라가 고안한 알고리즘이다. 첫 발상 이후 꾸준히 개선되어왔고 구체적인 구현과 시간 복잡도는 하단의 구현 문단 참고.
어떠한 구현이든 그래프 방향의 유무는 상관 없다. 어떠한 구현이든 음수 사이클이 존재한다면 사용할 수 없다. 구현에 따라 음수 간선(幹線, Edge)이 있을 때도 정상 동작하는 구현이 있고 그렇지 않은 구현이 있다. 구체적인 설명은 이 역시 하단의 구현 문단 참고. 음수 사이클이 존재할 때 혹은 음수 간선을 허용하는 특정 구현을 쓰기 싫을 때는 벨먼-포드 알고리즘, SPFA 등이 사용 가능하다.
다익스트라 알고리즘이 하나의 노드로부터 최단경로(one-to-all)를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리(all-to-all)를 구하는 알고리즘이다. 각 노드마다 다익스트라 알고리즘을 적용해 모든 노드쌍들에 대한 최단거리를 구할 수도 있지만 구현이 복잡한데다가 시간복잡도는 동일하니 플로이드-워셜 알고리즘을 쓰는 게 낫다.
다익스트라 알고리즘을 확장시킨 알고리즘이 A* 알고리즘이다. 이 외에도 바로 위에서 언급한 벨만-포드 알고리즘이나 플로이드-워셜 알고리즘도 다익스트라 알고리즘에서 영향을 받았고, 경로탐색 시 가장 기초적이면서 보편적으로 쓰이는 도구인 만큼 프로그래밍을 배우는 사람이라면 반드시 이해하고 넘어가야 하는 중요 개념이다.
2. 알고리즘의 실질적 이용
가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 고로 실질적 이용 예가 얼마나 많은지에 대해 더 이상의 자세한 설명은 생략한다.예를 들어 현실 세계를 도시가 노드이고 도로가 간선인 그래프로 간주한다면, 내비게이션처럼 두 도시를 잇는 가장 빠른 길을 찾는 문제를 이 알고리즘으로 해결[1]할 수 있다. 또한 미로탐색 알고리즘, 라우팅에서의 OSPF 방식의 프로토콜, 공업입지론에서 최소 운송비 지점을 구할 때도 이용할 수 있다. 약간 어려운 예시로는 루빅스 큐브를 푸는 프로그램을 다익스트라 알고리즘으로 만들 수 있는데 이건 A* 알고리즘 문서 참고.
3. 알고리즘
다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다)- 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.[2][3]
- 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
- A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B][4]와 d[B][5]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.
- 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
- A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
- A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
- "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
- 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.
이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.
7번 단계에서 거리가 가장 짧은 노드를 고르는 것은 공짜가 아니다. 모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데, 이때 제대로 구현된[6] 우선순위 큐를 활용한다면 이 비용을 줄일 수 있다. 최단거리를 갱신할 때 우선순위 큐에도 <위치, 거리>의 쌍을 넣어주고, 거리가 가장 짧은 노드를 우선순위 큐를 이용해 고르면 된다. 이진 힙을 이용해 구현한 우선순위 큐의 경우 삽입/수정에 O(lg N) 출력에 O(lg N)이므로, 배열을 사용할 때의 삽입/수정에 O(1), 출력에 O(N)(모든 노드 순회)보다 저렴하다. 우선순위 큐 구현에 피보나치 힙을 사용한 경우 삽입/수정은 평균적으로 O(1), 출력에는 O(lg N)이 걸려 이론적으로 더 나은 시간복잡도를 얻을 수 있다. 단 현실 세계에서는 이진 힙이 훨씬 간단하여 연산에 소요되는 시간이 빠르기 때문에, 엣지의 개수가 적은 경우에는 이진 힙을 사용하는 것이 더 나을 수 있다.
3.1. 의사코드
Graph는 모든 노드와 노드 간의 거리, 이웃노드에 관한 정보를 포함한다.Source는 출발할 노드를 의미한다.prev[(node)]는 출발지까지 가장 빠르게 갈 수 있다고 계산된 이웃 노드를 가리킨다. 즉, 출발지부터 목적지까지의 경로가 아니라, 목적지부터 출발지까지의 경로를 기록한다.dist[(node)]는 출발지부터 현재 node까지의 cost 값을 의미한다.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[] // 계산된 거리값과 목적지를 리턴
3.2. 3가지 구현
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 참고.V는 정점(vertex)의 총 개수이고 E는 간선(edge)의 총 개수이다.
- 배열 내에서 선형탐색 + 배열 내에 중복 정점 허용하지 않음
다익스트라가 처음 고안한 알고리즘이다. [math(O(V^2+E))]의 시간복잡도를 가졌다. 음수 간선을 허용하지 않는다. 인터넷에서 설명과 구현을 쉽게 찾아볼 수 있다.
시간복잡도에 대한 설명은 다음과 같다. 각 반복문마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 [math(O(V^2))]의 시간이 필요하다. 왜냐하면 언젠가 나올 모든 노드 ([math(O(V))])에 대해 원소 V개가 들어간 배열에서 선형탐색을 하며 최소값을 추출([math(O(V))])하기 때문이다. 또한 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 [math(O(E))]의 시간이 필요하다. 왜냐하면 각 노드마다 모든 이웃을 확인하는 것은 결국 모든 edge를 확인하는 것과 같고 [math(O(E))], 원소 V개가 들어간 거리 배열과 방문여부 배열(혹은 집합)을 수정([math(O(1)))])해야 하기 때문이다.
- 우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용하지 않음
다익스트라의 첫 고안 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나왔다. [math(O(VlogV+ElogV))]의 시간복잡도를 가졌다. 음수 간선을 허용하지 않는다. 인터넷에서 알고리즘에 대해 찾으면 나오는 대부분의 설명은 이 설명이지만, 구현은 이 구현이 아니니까 유의해야 한다.
시간복잡도에 대한 설명은 다음과 같다. 각 반복문마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 [math(O(VlogV))]의 시간이 필요하다. 왜냐하면 언젠가 나올 모든 노드 ([math(O(V))])에 대해 원소 V개가 들어간 우선순위큐에서 최소값을 추출([math(O(logV))])하기 때문이다. 또한 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 [math(O(ElogV))]의 시간이 필요하다. 각 노드마다 모든 이웃을 확인하는 것은 결국 모든 edge를 확인하는 것과 같고 [math(O(E))], 원소 V개가 들어간 우선순위큐에서 change_key(새로운 비용, 비용이 바뀔 정점) 함수를 이용해 최단 거리를 갱신[math(O(logV))]해야 하기 때문이다.
change_key 함수의 구현은 이진힙 기준으로 쉽게 할 수 있으나 문제는 비용이 바뀔 정점이 우선순위큐 내에 어디에 위치했는지 모른다는 점이다. 선형탐색을 하면 O(N)으로 도루묵이니 해시테이블/딕셔너리로 미리 구해서 O(1)로 써야하는데, decrease_key 연산을 하는 도중 관심사의 정점뿐만 아니라 그 정점과 위치가 바뀌는 정점까지도 바뀌는 위치를 전부 수정해야해서 까다롭다.
- 우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용
[math(O(ElogE+ElogE))]의 시간복잡도를 가졌다. 음수 간선을 허용한다. 인터넷에 찾으면 나오는 대부분의 구현은 이 구현이다.
모든 간선이 양수일 때의 시간복잡도에 대한 설명은 다음과 같다. 이해가 편하게 삽입에 대한 설명을 먼저 하자. 각 노드마다 이웃한 노드의 최단 거리를 넣을 때 [math(O(ElogE))]의 시간이 필요하다. 왜냐하면 각 노드마다 모든 이웃을 확인하는 것은 결국 모든 edge를 확인하는 것과 같고([math(O(E))]), 그러한 모든 경우에서 최단 경로가 갱신되어 원소를 새로 넣을 경우 우선순위큐의 길이는 E가 되는데 이러한 우선순위큐에서 삽입([math(O(logE))])해야 하기 때문이다. 또한 이렇게 원소 E개인 우선순위큐 반복문 내에서 최단 거리를 가지는 노드를 찾는데 [math(O(ElogE))]의 시간이 필요하다. 왜냐하면 언젠가 나올 모든 원소([math(O(E))])에 대해 원소 E개가 들어간 우선순위큐에서 최솟값을 추출([math(O(logE))])하기 때문이다. 이렇게 추출된 값은 E개지만(if dist[Vextracted] == dist_extracted)에 해당되는 값은 V개이기 때문에 구현2에서 말했던 '각 노드의 모든 이웃은 결국 모든 edge이다'라는 가정은 여전히 성립하고 시간복잡도에 영향은 없다. 반대로 말하자면 이러한 조건문을 걸지 않을 경우 시간복잡도가 크게 증가한다.
음수 사이클이 없고 음수 간선이 있을 때의 시간복잡도는 [math(O(2^Vlog2^V+2^Vlog2^V))]이다영어1, 영어2, 한국어1. 이 시간복잡도는 최악일 때의 경우이니 인위적으로 만들지 않은 그래프 혹은 음수 간선이 한두 개 있는 경우는 모든 간선이 양수일 때의 시간복잡도와 비슷하다고 봐도 좋을 것이다.
'다익스트라 알고리즘은 그리디 알고리즘이기 때문에 A->C(비용+4) 대신 A->B(비용+3)을 선택 후 B를 방문처리하게 된다. 현재는 나쁘지만 미래에는 좋은 결과를 불러오는 A->C(비용+4)&C->B(비용-5) 경로(비용-1)를 선택하지 않게 되고 올바른 해를 도출할 수 없게 된다'라는 설명은 이 구현에서는 들어맞지 않게 된다. 중복 정점을 허용하기 때문에 그리디 알고리즘이 아니라 (가지치기가 빡빡한) 백트래킹으로 볼 수 있고 따라서 A->B(비용+3)부터 알고리즘을 다시 시작하게 되고 올바른 해를 도출할 수 있다.
2번째 구현과 3번째 구현 모두 삽입/수정에 O(1), 출력에 O(logn)이 걸리는 피보나치 힙을 사용할 경우 개선될 수 있고 그래프가 희소한 경우에만 1번째 구현보다 빠르다.
3.3. 그림 설명
예를 들어, 다음과 같은 네트워크가 존재한다고 가정하자. 먼저, A 라우터의 목표는 F까지의 최단 거리 계산이며, 수단으로는 다익스트라 알고리즘을 활용한다. 이때, 각 데이터의 의미는 다음과 같다.- S = 방문한 노드들의 집합
- d[N] = A → N까지 계산된 최단 거리
- Q = 방문하지 않은 노드들의 집합
1. 다익스트라 알고리즘은 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.
초기화가 실행된 후의 그래프.
- 출발지와 출발지의 거리는 확인해볼 필요도 없이 당연히 0 값을 가진다는 것을 알 수 있다. 출발지를 A로 설정했기 때문에, d[A]=0이 된다. (A노드를 아직 방문한 것은 아니다.)
- 출발지를 제외한 모든 노드들도 아직 확인되지 않았기에, d[다른 노드]=무한이 된다.
- Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.
- S는 방문한 노드가 아직 없으므로 공집합 상태이다.
2. 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.
첫 루프를 마치고 난 뒤의 그래프.
- 가장 먼저, 거리가 최소인 노드(d[N]이 최소값인 노드 N)를 Q(방문하지 않은 노드의 집합)에서 제거하고, 그 노드를 S(방문한 노드의 집합 및 최소 경로)에 추가한다. 이는 즉, 노드 N을 '방문한다'는 의미가 된다.
- 이후, 방문한 노드 N과 연결된 모든 이웃 노드와의 거리를 측정하여 d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)이 계산된다. 새로 계산된 값이 기존에 저장된 값보다 작은 경우에만 d[N]을 갱신한다.
- 예를 들어 초기화 직후의 첫 루프에서 시작 정점으로부터의 거리가 최소인 노드는 A이므로(자기 자신), 노드 A를 방문하여 Q에서 제거하고 S에 추가하게 된다. 다만, 지금은 첫 번째 루프만을 끝낸 상태이므로, 단순히 0 + (이웃 노드와 출발지 사이의 거리값) = (출발지와 이웃 노드 간의 거리값)이 각 이웃 노드까지의 거리값으로 기록된다(무한보다 작기 때문에). 따라서, d[B] = 10, d[C] = 30, d[D] =15로 값을 갱신한다.
3. 첫 루프 이후의 그래프의 상태가 업데이트되는 방식
두 번째 루프를 마치고 난 뒤의 그래프.
이제 루프가 반복적으로 작동하는 방법을 설명한다. 밑의 그림들 또한 루프 안에서 알고리즘이 진행되는 순간들을 반복 설명한다.
- 이전에 설명했듯이, 방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것으로 선택된다. 따라서, Q = {B, C, D, E, F} 중 B가 d[B] = 10으로 제일 작은 값을 가지므로, B를 방문하여 S에 추가하고 Q에서 제거한다.
- 이제, B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다. B의 이웃 노드는 E뿐이므로, d[E] 값이 무한에서 d[B]+(B로부터 E까지의 거리값 20) = 30 으로 업데이트된다.[7] 여기서 d[B] 값을 더하는 이유는 출발지부터 해당 노드까지의 거리값을 재기 위해서다.
4. 더 빠른 경로를 발견한 경우
- 세 번째 루프에서 선택·방문되는 노드는 D이다. 두 번째 루프를 마친 후 Q의 원소 중에서 제일 낮은 d[N] 값을 가진 것이 D이기 때문이다. 따라서 세번째 루프를 마친 뒤인 위의 그림에서도 S에 D가 추가되어 있는 것을 볼 수 있다.
- 이제 D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트한다. 이 때 d[C]의 값은 A를 방문할 때 이미 계산되어 30으로 저장되해어 있었으나, D를 방문하여 C와의 거리를 확인해 보니 20으로 더 짧은 최단 경로가 발견되었다! 그러므로, d[C]의 값을 30에서 20으로 변경한다.
- d[F]의 경우에도 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 변경한다.
5. 또 다른 반복 루프 상황
- Q = {C,E,F} 중 d[C] = 20으로 거리가 가장 짧은 C를 방문하여, S는 {A, B, D, C}가 되었다.
- 다시 이웃 노드와의 거리 계산을 해보니, 이번에는 (A→D) + (D→F) = 15 + 20 = 35보다, (A→D) + (D→C) + (C→F) = 15 + 5 + 5 = 25로 더 작은 값을 가지는 것이 발견되었다. d[F] = 25로 업데이트한다.
이 일련의 과정이 반복되어 Q가 공집합이 되었다면, 남아 있는 데이터로 추론하여 최단 거리를 결정한다.
마지막 루프 이후,
- S = {A, B, D, C, F, E} (방문한 순서대로 정렬)
- d[A] = 0
- d[B] = 10
- d[C] = 20
- d[D] = 15
- d[E] = 30
- d[F] = 25
- Q = ∅
[1] 실제로는 노드와 간선이 너무 많기 때문에 인공지능 기법이 필요하다.[2] C++의 경우
std::numeric_limits::max, Python의 경우 타입에 따라 sys.maxint나 sys.float_info.max 등을 사용하면 안전한 값을 구할 수 있다. math.inf도 있다.[3] 참고로 자주 사용되는 int의 경우 2,147,483,647이 양의 최대값으로, 이걸 16진수로 표현하게 되면 0x7FFFFFFF이다. F가 7개. 이걸로도 모자랄 것 같으면 64비트 정수 타입을 쓰거나 아예 실수 타입을 써야 한다. 또한 INF값에 더하기 등의 특정 연산을 수행할 경우 오버플로로 인해 오작동할 수 있으니 이를 고려한 INF값과 적절한 자료형을 정하는 것이 좋다. 거리가 너무 커지는 경우 문제 자체에서 특정 수로 나눈 나머지를 출력하라는 식으로 오버플로를 예방하기도 한다.[4] A를 거쳐서 B로 가는 최단 거리[5] 현재까지 알려진 B까지의 최단 거리[6] 우선순위 큐는 값을 받아 지정된 우선순위대로 내보낸다는 사양이 정의되어있을 뿐, 시간/공간 복잡도는 정의하지 않는다. 다만 제대로 구현된 경우 로그시간이 걸리는 것이 일반적.[7] 30은 무한값보다 당연히 작으므로 업데이트가 되는 것이다.