알고리즘
다익스트라 알고리즘 완벽 가이드: 2차원 행렬부터 우선순위 큐까지, 자바 구현으로 배우는 최단 경로 찾기
Renechoi
2025. 4. 26. 18:08
1.다익스트라?
- 가중치(weight)가 부여된 방향 없는 혹은 방향 있는 그래프에서, 특정 시작 정점(start)으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
- 에츠허르 다익스트라가 고안하였다.
- 특징
- 간선의 가중치가 음수가 아닐 때만 사용 가능
- 우선순위 큐(Priority Queue)를 활용해 효율적으로 구현
2. 그래프 기본 개념
- 정점(Vertex): 그래프를 구성하는 노드
- 간선(Edge): 정점과 정점을 연결하는 선, 가중치(weight)를 가짐
- 경로(Path): 한 정점에서 다른 정점으로 이동하는 과정
- 최단 경로(Shortest Path): 여러 경로 중 가중치 합이 가장 작은 경로
graph LR
A((A)) --2--> B((B))
A((A)) --5--> C((C))
A((A)) --7--> F((F))
B((B)) --1--> C((C))
B((B)) --2--> D((D))
C((C)) --3--> D((D))
C((C)) --4--> E((E))
D((D)) --1--> E((E))
D((D)) --2--> F((F))
E((E)) --3--> F((F))
3. 가장 빠른 길을 찾아보자
위와 같은 마을 지도를 놓고 이제 생각해보자.
A 건물에서 출발해 F 건물까지 가는 길 중에서 “가장 빠른 길(거리 합이 가장 작은 길)”을 어떻게 찾을 수 있을까?
3.1. ‘가장 가까운 곳부터’ 찾아가는 방식
다익스트라 알고리즘의 가장 큰 아이디어는 “가장 가까운 곳부터” 하나씩 살펴보면서, 그곳에서 연결된 길을 통해 갈 수 있는 다른 곳까지의 거리를 갱신해 나가는 방식이다.
1) 처음 출발 지점(A)에서 시작
- 처음에는 A에서 A로 가는 거리는 당연히 0이고,
- A에서 다른 건물(B, C, D, E, F)로 가는 거리는 아직 모르니까 “무한대(∞)”라고 기록해둔다.
- 예를 들면,
건물 거리(처음) A 0 B ∞ C ∞ D ∞ E ∞ F ∞
graph LR
%% ─── 정점 스타일 정의 ───
classDef settled fill:#2ecc71,color:#ffffff,stroke-width:2px;
classDef frontier fill:#f39c12,color:#ffffff,stroke-width:2px;
classDef unseen fill:#dcdcdc,color:#666666,stroke-width:1px;
%% ─── 정점 선언 (거리 표시) ───
A((A: 0)):::settled
B((B: ∞)):::unseen
C((C: ∞)):::unseen
D((D: ∞)):::unseen
E((E: ∞)):::unseen
F((F: ∞)):::unseen
%% ─── 간선 가중치 ───
A --2--> B
A --5--> C
A --7--> F
B --1--> C
B --2--> D
C --3--> D
C --4--> E
D --1--> E
D --2--> F
E --3--> F
2) 가장 가까운 건물을 선택
- A만 방문한 상태이니, 당연히 “A”가 가장 가까운 건물이다.
- 이제 A와 직접 연결된 다른 건물(위 그림에서 B, C, F)의 거리값을 A를 거쳐 가는 거리로 갱신해보자.
- 예를 들어, A에서 B로 가는 직접 거리(간선 가중치)가 2이므로, B에 기록되는 값은 이전까지의 거리(∞)와 비교해서 더 작은 값인 2가 된다.
- 마찬가지로 C는 5, F는 7이 된다.
건물 거리(업데이트 후) 어떤 경로를 통해 갱신됐나? A 0 (시작점) B 2 A → B C 5 A → C D ∞ 갱신 X E ∞ 갱신 X F 7 A → F
graph LR
%% ─── 스타일 ───
classDef settled fill:#2ecc71,color:#ffffff,stroke-width:2px;
classDef frontier fill:#f39c12,color:#ffffff,stroke-width:2px;
classDef unseen fill:#dcdcdc,color:#666666,stroke-width:1px;
%% ─── 정점 (거리) ───
A((A: 0)):::settled
B((B: 2)):::frontier
C((C: 5)):::frontier
D((D: ∞)):::unseen
E((E: ∞)):::unseen
F((F: 7)):::frontier
%% ─── 간선 ───
A --2--> B
A --5--> C
A --7--> F
B --1--> C
B --2--> D
C --3--> D
C --4--> E
D --1--> E
D --2--> F
E --3--> F
3) 가장 가까운 건물을 찾아가며 거리 갱신 반복
- 이제 A는 방문했다고 표시하고, A를 제외한 나머지 중 “가장 거리값이 작은 건물”을 찾는다.
- 위 표를 보면 B(거리값 2)가 가장 작다.
- B를 “방문”하고, B와 연결된 C, D로 가는 거리를 (A→B까지의 거리) + (B에서 C, D로 가는 추가 거리)로 다시 계산해보자.
- B → C는 가중치가 1이므로,
A→B(2) + B→C(1) = 3- 기존 C의 값(5)과 비교하니, 3이 더 작아서 C를 3으로 갱신!
- B → D는 가중치가 2이므로,
A→B(2) + B→D(2) = 4- D의 기존값은 ∞이었으니 당연히 4로 갱신!
건물 거리(갱신 과정) 어떤 경로? A 0 시작점 B 2 A → B (방문 완료) C 3 A → B → C (갱신) D 4 A → B → D (갱신) E ∞ 갱신 X F 7 A → F (이전 유지) - B → C는 가중치가 1이므로,
graph LR
classDef settled fill:#2ecc71,color:#ffffff,stroke-width:2px;
classDef frontier fill:#f39c12,color:#ffffff,stroke-width:2px;
classDef unseen fill:#dcdcdc,color:#666666,stroke-width:1px;
A((A: 0)):::settled
B((B: 2)):::settled
C((C: 3)):::frontier
D((D: 4)):::frontier
E((E: ∞)):::unseen
F((F: 7)):::frontier
A --2--> B
A --5--> C
A --7--> F
B --1--> C
B --2--> D
C --3--> D
C --4--> E
D --1--> E
D --2--> F
E --3--> F- 이제 B도 방문했다고 표시하고, 또 가장 거리값이 작은 건물을 찾는다.
- 현재 C(3), D(4), F(7), E(∞)가 남았으니, C(3)가 가장 작다.
- C를 방문하고, C와 연결된 D, E로 가는 거리를 또 계산한다.
- C → D(가중치 3):
A→B→C(3) + C→D(3) = 6- 기존에 D값은 4, 6과 비교하면 더 작은 값이 4이므로 갱신하지 않는다.
- C → E(가중치 4):
A→B→C(3) + C→E(4) = 7- E값은 ∞였으니 7로 갱신해준다.
건물 거리(갱신 과정) 어떤 경로? A 0 시작점 B 2 A → B (방문 완료) C 3 A → B → C (방문 완료) D 4 A → B → D E 7 A → B → C → E (갱신) F 7 A → F - C → D(가중치 3):
graph LR
classDef settled fill:#2ecc71,color:#ffffff,stroke-width:2px;
classDef frontier fill:#f39c12,color:#ffffff,stroke-width:2px;
classDef unseen fill:#dcdcdc,color:#666666,stroke-width:1px;
A((A: 0)):::settled
B((B: 2)):::settled
C((C: 3)):::settled
D((D: 4)):::frontier
E((E: 7)):::frontier
F((F: 7)):::frontier
A --2--> B
A --5--> C
A --7--> F
B --1--> C
B --2--> D
C --3--> D
C --4--> E
D --1--> E
D --2--> F
E --3--> F
4) 목표 지점(F)까지 거리값을 완성해나가기
- 이어서 아직 방문하지 않은 건물들 중 거리값이 가장 작은 D(4)를 방문한다.
- D에서 갈 수 있는 E와 F에 대해서 거리값을 확인해본다.
- D → E(1): 현재 D까지가 4, 합하면 5. 지금 E의 거리값은 7이니까, 5가 더 작다!
- 따라서 E를 5로 갱신한다.
- D → F(2): D까지가 4였으니, 합하면 6.
- 기존 F의 값은 7이니까, 6이 더 작아서 갱신한다.
건물 거리(갱신 과정) 어떤 경로? A 0 시작점 B 2 A → B (방문 완료) C 3 A → B → C (방문 완료) D 4 A → B → D (방문 완료) E 5 A → B → D → E (갱신) F 6 A → B → D → F (갱신) - D → E(1): 현재 D까지가 4, 합하면 5. 지금 E의 거리값은 7이니까, 5가 더 작다!
graph LR
classDef settled fill:#2ecc71,color:#ffffff,stroke-width:2px;
classDef frontier fill:#f39c12,color:#ffffff,stroke-width:2px;
classDef unseen fill:#dcdcdc,color:#666666,stroke-width:1px;
A((A: 0)):::settled
B((B: 2)):::settled
C((C: 3)):::settled
D((D: 4)):::settled
E((E: 5)):::frontier
F((F: 6)):::frontier
A --2--> B
A --5--> C
A --7--> F
B --1--> C
B --2--> D
C --3--> D
C --4--> E
D --1--> E
D --2--> F
E --3--> F- 마지막으로 E(5) 또는 F(6) 중 더 작은 E(5)를 방문하고, E에서 F로 가는 길(3)을 확인한다.
- E까지 5, E→F가 3이니 합쳐 8인데, 이미 F는 6이니까 갱신할 필요가 없다.
- 결국, F(6)이 우리가 찾은 A에서 F까지의 최단 거리값이 된다.
5) A에서 F로 가는 최단 경로 확인
- F의 최종 거리값이 6이라는 것은, A에서 F로 가는 가장 짧은 길이 6의 거리로 이동할 수 있다는 뜻이다.
- 실제 경로를 추적해보면,
A → B(2) → D(4) → F(6)이런 식으로 찾아낼 수 있다.- (A에서 B까지 2, B에서 D까지 2, D에서 F까지 2 → 총합 6)
graph LR
classDef settled fill:#2ecc71,color:#ffffff,stroke-width:2px;
A((A: 0)):::settled
B((B: 2)):::settled
C((C: 3)):::settled
D((D: 4)):::settled
E((E: 5)):::settled
F((F: 6)):::settled
A --2--> B
A --5--> C
A --7--> F
B --1--> C
B --2--> D
C --3--> D
C --4--> E
D --1--> E
D --2--> F
E --3--> F
4. 알고리즘 구현 핵심 아이디어
다음 단계로는, 앞에서 살펴본 예시(마을 지도)와 다익스트라 알고리즘의 작동 방식을 프로그램 관점에서 어떻게 구현할 수 있는지 생각해볼 차례이다.
“아이디어”라는 것은 곧 구현의 뼈대가 된다고 볼 수 있다. 즉, 코드를 직접 작성하기 전에 “어떻게 구현할지”를 미리 그려보자.
4.1. 아이디어 (위의 예시 기반)
1) 거리 정보를 저장할 자료구조(distance 배열 or map) 준비
- 예시에서 우리는 각 건물(A, B, C, ...)까지 도달하는 최소 거리를 표로 적어두었다.
- 실제 구현에서는 이런 “최소 거리값”을 담아 둘 배열(dist[]) 혹은 Map(딕셔너리) 형태로 준비하면 된다.
- 예)
dist[A] = 0; dist[B] = ∞; dist[C] = ∞; ...
2) 방문 여부(or 정해진 거리) 관리를 위한 표시
- 이미 최단 거리가 확정된 정점(건물)은 재방문하지 않도록 표시해야 한다.
- 이를 위해 “visited[] 배열”을 두거나, 혹은 우선순위 큐에서 꺼냈을 때 이미 더 작은 값으로 갱신된 적이 있으면 무시해버리는 로직을 넣는 식으로 관리할 수 있다.
3) 현재까지의 거리값이 가장 작은 정점을 빠르게 찾아야 함 → 우선순위 큐(Priority Queue)
- 앞의 예시에서는 B(2), C(3)처럼 “가장 거리값이 작은 건물”을 계속 찾아야 했다.
- 만약 단순 배열만 쓰면, 매번 “가장 작은 값을 찾기 위해 전체를 훑어보는” O(V) 과정을 거쳐야 한다.
- 우선순위 큐를 사용하면 “가장 작은 값”을 로그 시간(log V) 정도로 빠르게 꺼낼 수 있어서, 큰 규모의 그래프일수록 훨씬 효율적일 것이다.
4) 그래프 정보(인접 리스트 or 2차원 행렬) 표현
- 예시의 마을 지도에서 “A - B 간선 2”, “B - C 간선 1” 등은 그래프의 간선 정보를 저장해야 알 수 있다.
- 구현 방식은 크게 “인접 리스트(Adjacent List)”와 “인접 행렬(2차원 배열)” 두 가지가 있다.
- 인접 리스트: 각 정점에 연결된 간선(목적지, 가중치) 목록을 저장 → 보통 간선 수(E)가 많지 않은 그래프에 유리
- 인접 행렬: V×V 크기의 행렬에 거리값을 채워넣음 → 그래프가 빽빽하게 연결되어 있거나, 정점이 많지 않을 때 유리
- 다익스트라에서는 보통 인접 리스트 + 우선순위 큐 조합이 가장 널리 쓰인다.
5) 알고리즘 절차
- (1) 시작점의 거리값을 0으로 초기화, 나머지는 ∞로 초기화
- (2) 우선순위 큐에 (시작점, 거리 0)을 넣고 시작
- (3) 큐에서 꺼낸 정점이
- 이미 방문한 적이 있거나(visited)
- dist[]에 기록된 현재 값보다 더 큰 거리로 꺼낸 경우
→ 무시 (더 짧은 경로가 이미 존재하므로)
- (4) 그 정점과 연결된 모든 이웃 정점에 대해,
새 거리 = 현재 정점까지의 거리 + 간선 가중치계산- 만약
새 거리 < 이웃 정점의 기존 dist[]라면 갱신하고 우선순위 큐에 넣음
- (5) 모든 정점에 대해 우선순위 큐가 빌 때까지 (3)~(4) 반복
4.2. 왜 이렇게 하면 최단 거리를 찾을 수 있을까?
1) “가장 짧은 거리부터 믿는다”는 그리디(Greedy) 전략
- 다익스트라 알고리즘은 본질적으로 그리디 알고리즘이다.
- 이미 계산된 가장 짧은 거리는 “앞으로 갱신되더라도 더 짧아질 일은 없다”는 사실을 이용한다.
- 예를 들어, A에서 B까지의 최단 거리가 2로 확정됐다면, 다른 경로로 B를 가려고 해도 결국 그 값(2)보다 더 작은 값이 나올 수 없다는 것이다.
2) 방문한(거리값 확정된) 정점은 ‘더 짧아질 수 없는’ 사실
- 알고리즘 진행 중에 어떤 정점을 “최단 거리 확정(방문)” 처리할 때는,
이미 그 정점까지 도달 가능한 여러 경로 중 가장 짧은 경로를 찾아낸 상태이므로,
이 값보다 더 작은 값이 나오는 경로는 존재하지 않는다(존재했다면, 이미 먼저 계산되었을 테니까).
flowchart LR
A["A: 거리 [확정]"]:::done --> B["B: 거리 2 [확정]"]:::done
B --> C["C: 거리 3 [후보]"]:::candidate
C --> D["D: 거리 ? [미정]"]:::unvisited
style A stroke:#3498db,stroke-width:2px,fill:#85c1e9,color:#ffffff
style B stroke:#2ecc71,stroke-width:2px,fill:#58d68d,color:#ffffff
style C stroke:#f1c40f,stroke-width:2px,fill:#f9e79f,color:#555555
style D stroke:#bdc3c7,stroke-width:2px,fill:#ecf0f1,color:#555555
subgraph 그리디 아이디어
note1(["이미 확정된 노드는<br/>더 짧아지지 않는다"]):::note
end
note1 --> A
note1 --> B
classDef note stroke:#666,fill:#f4f6f7,color:#000,font-size:12px
3) 간선 가중치가 “음수”가 아니어야 하는 이유
- 만약 간선에 음수 가중치가 포함된다면, “나중에 더 짧은 경로가 발견될 수도 있음”이라는 문제가 생긴다.
- 다익스트라의 그리디 전략이 깨지게 되므로, 음수 간선이 있으면 다른 알고리즘(벨만-포드 등)을 써야 한다.
- 이 부분은 밑단에서 추가 섹션으로 다뤄보자.
4) 최종적으로, 모든 정점의 dist[] 배열에는 A(시작점)로부터의 ‘최단 거리’가 기록
- dist[F]가 6이라면, 이는 “A에서 F까지의 최단 경로가 거리 6이다”를 뜻하며, 실제 경로 추적을 해보면 6이라는 합이 된다.
정리하자면, 다익스트라 알고리즘은 “조금씩 확정된 최단 거리”를 기반으로 전체 그래프를 탐색해 가면서,
모든 정점에 대한 최단 거리를 구할 수 있게 해 주는 방법이라고 할 수 있다.
이제 자바 코드 기반으로 구체적인 구현을 살펴보자.
5. 구현 디테일 1: 2차원 행렬 사용
5.1. 인접 행렬(2차원 배열)로 그래프 표현하기
- 인접 행렬이란, 정점(노드) 수를 (V)라고 할 때, (V X V) 크기의 2차원 배열로 간선 정보를 저장하는 방식이다.
- 행렬의 ((i, j)) 값이 0이 아니고 무한대(또는 매우 큰 수)가 아니라면, “정점 i에서 정점 j로 가는 간선”이 존재한다는 의미가 된다.
- 예를 들어, 아래
graph배열은 A, B, C, D, E, F 6개의 정점(건물)이 있다고 할 때의 인접 행렬 예시이다.- A(인덱스 0), B(1), C(2), D(3), E(4), F(5) 로 가정
INF는 이어지지 않은 간선을 의미하는 “매우 큰 값” (실제 코드에선Integer.MAX_VALUEor 9999999 등)
static final int INF = 999999999;
int[][] graph = {
// A, B, C, D, E, F
/*A*/ { 0, 2, 5, INF, INF, 7 },
/*B*/ { 2, 0, 1, 2, INF, INF },
/*C*/ { 5, 1, 0, 3, 4, INF },
/*D*/ {INF, 2, 3, 0, 1, 2 },
/*E*/ {INF,INF,4, 1, 0, 3 },
/*F*/ { 7,INF,INF, 2, 3, 0 }
};- 예를 들어,
graph[0][1] = 2는 A(0)에서 B(1)로의 가중치(거리)가 2라는 의미이며,graph[0][3] = INF는 A에서 D로 가는 직접 길이 없음을 뜻한다.
5.2. 다익스트라 알고리즘 구현 (인접 행렬 버전)
아래 코드는
dist[]배열로 “시작점으로부터의 최소 거리” 정보를 관리visited[]배열로 “이미 최단 거리가 확정된 정점”을 표시- 매 단계마다
visited[]가 아닌 정점 중 “dist 값이 가장 작은 정점”을 찾아서 이웃 거리 갱신
하는 다익스트라 알고리즘 구조이다.
public class DijkstraMatrix {
static final int INF = 999999999;
public static void main(String[] args) {
// 6개의 정점을 가진 예시 그래프 (A=0, B=1, C=2, D=3, E=4, F=5)
int[][] graph = {
// A, B, C, D, E, F
/*A*/ { 0, 2, 5, INF, INF, 7 },
/*B*/ { 2, 0, 1, 2, INF, INF },
/*C*/ { 5, 1, 0, 3, 4, INF },
/*D*/ {INF, 2, 3, 0, 1, 2 },
/*E*/ {INF,INF,4, 1, 0, 3 },
/*F*/ { 7,INF,INF, 2, 3, 0 }
};
// 시작점: A(인덱스 0)
int start = 0;
// 다익스트라 알고리즘 실행
int[] dist = dijkstra(graph, start);
// 결과 출력
// dist[i]는 "시작점 A에서 i번 정점까지"의 최단 거리
char[] vertexName = {'A','B','C','D','E','F'};
for (int i = 0; i < dist.length; i++) {
System.out.println(vertexName[start] + " → " + vertexName[i]
+ " 최단 거리: " + dist[i]);
}
}
/**
* 인접 행렬을 이용한 다익스트라 알고리즘
* @param graph 2차원 배열(인접 행렬)
* @param start 시작 정점 인덱스
* @return dist[] : 시작점으로부터 각 정점까지의 최단 거리 정보
*/
public static int[] dijkstra(int[][] graph, int start) {
int n = graph.length; // 정점(노드) 개수
int[] dist = new int[n]; // 최단 거리 테이블
boolean[] visited = new boolean[n]; // 방문(확정) 여부
// 1. dist 초기화 (시작점은 0, 나머지는 INF)
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
dist[start] = 0;
// 2. 모든 정점을 하나씩 처리
for (int i = 0; i < n; i++) {
// 2-1. 방문하지 않은 정점 중 dist값이 가장 작은 정점(u) 찾기
int u = -1;
int minDistance = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDistance) {
minDistance = dist[j];
u = j;
}
}
// 더 이상 갈 정점이 없으면 탈출
if (u == -1) break;
// 2-2. 찾은 정점(u)를 '방문(확정)' 처리
visited[u] = true;
// 2-3. u 정점과 인접한 모든 정점 v에 대해 최단 거리 갱신
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != INF) {
// 새로 계산된 거리 = u까지 거리 + u→v 간선 비용
int newDist = dist[u] + graph[u][v];
if (newDist < dist[v]) {
dist[v] = newDist; // 더 짧으면 갱신
}
}
}
}
return dist;
}
}
1) dist[] 초기화
dist[start] = 0(자기 자신까지 거리는 0)- 그 외 정점은
INF(아직 거리 알 수 없음)
2) “아직 방문 안 한 정점 중 dist가 최소인 정점” 찾아서 방문 처리
- 예시 그래프에서는 처음에
A가 선택되고, 이후B,C, … 순으로 “가장 짧은” 정점을 하나씩 확정 지음
3) 해당 정점(u)의 이웃 정점들에 대해 dist 갱신
dist[v] = min(dist[v], dist[u] + graph[u][v])- 즉, “u를 거쳐서 v에 가는 경로”가 더 짧다면 그 값으로 갱신
4) 위 과정을 모든 정점에 대해 반복하면, 최종적으로 dist[]에는 시작점으로부터 각 정점까지의 최단 거리가 저장
5.4. 2차원 행렬 방식의 장단점
- 장점
- 인접 행렬 자체가 구조가 단순해서, “간선 존재 여부”를 빠르게 확인하기 편함 (배열 인덱스 접근만으로 O(1) 확인)
- 정점 수가 적고 간선이 매우 많을 경우(빽빽한 그래프)에는 구현이 쉬움
- 단점
- 정점 수가 커질수록 (O(V^2))의 메모리가 필요해짐
- 간선이 드물게 있는 “희소 그래프(Sparse Graph)”에서는 메모리 낭비가 큼
- 다익스트라 수행 시, “모든 정점 중 dist가 최소인 정점”을 찾을 때 매번 O(V) 시간이 걸림
→ 따라서 전체적으로 O(V^2) 소요 (우선순위 큐를 쓰기도 까다로운 편)
그래도 다익스트라를 처음 접하는 분들에게는 2차원 행렬이 구조가 직관적이라 학습용으로 이해하기 쉽다.
6. 구현 디테일 2: 인접 리스트 사용
앞서 살펴본 2차원 행렬 방식은 정점(노드) 개수가 많고 간선(에지)이 비교적 적은 그래프에서는 비효율적일 수 있다.
이번 섹션에서는 인접 리스트(Adjacent List)로 그래프를 표현하고, 이를 기반으로 다익스트라 알고리즘을 어떻게 구현할 수 있는지 알아보자.
6.1. 인접 리스트(Adjacent List)란?
- 각 정점(노드)에 대해 “연결된 간선 목록”을 따로 저장하는 방식이다.
- 예를 들어, 정점 A에서 나갈 수 있는 간선 정보들을
A의 리스트에 저장하고, 정점 B에서 나갈 수 있는 간선 정보는B의 리스트에 저장하는 식이다. - 장점
- 그래프가 “희소(Sparse)”할 때(간선이 적을 때) 메모리를 덜 사용
- 어떤 정점의 “이웃 정점들(neighbors)”에 대해 빠르게 순회 가능
- 단점
- “정점 i에서 j로 가는 간선이 있는지”를 즉시 확인하기는 어려움(행렬처럼
graph[i][j]바로 접근 불가)
- “정점 i에서 j로 가는 간선이 있는지”를 즉시 확인하기는 어려움(행렬처럼
6.2. 인접 리스트 다익스트라 기본 구조
인접 리스트를 활용해 다익스트라 알고리즘을 구현하려면, 보통 다음과 같은 자료구조를 사용한다.
1) List<List<Edge>> graph
graph[u]에는 “정점 u와 직접 연결된 (v, weight)” 정보가 들어 있는Edge객체들의 리스트가 저장- 예)
graph[0]= [(1,2), (2,5), (5,7)] → A(0)에서 갈 수 있는 정점(B=1, C=2, F=5)와 그 가중치(2,5,7)
2) Edge 클래스(또는 구조체)
- 주로
int to; int weight;를 멤버로 가짐 to는 목적지 정점,weight는 간선 가중치(거리)
3) dist[] 배열
- 특정 시작 정점에서 “i번 정점까지의 최소 거리”를 저장
- 초기에는
dist[start] = 0, 나머지는INF(매우 큰 수)
4) visited[] 배열
- “이미 최단 거리가 확정된(더 이상 갱신될 일이 없는) 정점”인지 표시
- (우선순위 큐를 사용할 경우는
visited[]없이도 구현 가능하지만, 우선 여기서는 기본 구조로 설명)
5) 알고리즘 절차
- (1)
dist[start] = 0, 나머지는 INF로 초기화 - (2) “방문 안 한 정점 중 dist가 가장 작은 정점”을 찾음 → 방문 처리
- (3) 그 정점의 “이웃 정점” 리스트를 순회하며, 기존 dist값보다 “새 거리(u까지 거리 + u→v 가중치)”가 더 작으면 갱신
- (4) 모든 정점을 처리할 때까지 (2), (3)을 반복
6.3. 자바 코드 예시 (인접 리스트 + 기본 다익스트라)
import java.util.ArrayList;
import java.util.List;
public class DijkstraList {
static final int INF = 999999999;
// 간선 정보를 담을 클래스 (to: 도착 정점, weight: 간선 가중치)
static class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public static void main(String[] args) {
// 그래프 정점 개수
int n = 6; // A=0, B=1, C=2, D=3, E=4, F=5
// 인접 리스트 준비 (정점 개수만큼)
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 그래프 간선 정보 세팅
// A(0) -> B(1) : 2, C(2) : 5, F(5) : 7
graph.get(0).add(new Edge(1, 2));
graph.get(0).add(new Edge(2, 5));
graph.get(0).add(new Edge(5, 7));
// B(1) -> A(0): 2, C(2): 1, D(3): 2
// (무방향 그래프라면 "B->A"도 추가, 여기서는 방향성 여부에 따라 다름)
graph.get(1).add(new Edge(0, 2));
graph.get(1).add(new Edge(2, 1));
graph.get(1).add(new Edge(3, 2));
// C(2) -> A(0): 5, B(1): 1, D(3): 3, E(4): 4
graph.get(2).add(new Edge(0, 5));
graph.get(2).add(new Edge(1, 1));
graph.get(2).add(new Edge(3, 3));
graph.get(2).add(new Edge(4, 4));
// D(3) -> B(1): 2, C(2): 3, E(4): 1, F(5): 2
graph.get(3).add(new Edge(1, 2));
graph.get(3).add(new Edge(2, 3));
graph.get(3).add(new Edge(4, 1));
graph.get(3).add(new Edge(5, 2));
// E(4) -> C(2): 4, D(3): 1, F(5): 3
graph.get(4).add(new Edge(2, 4));
graph.get(4).add(new Edge(3, 1));
graph.get(4).add(new Edge(5, 3));
// F(5) -> A(0): 7, D(3): 2, E(4): 3
graph.get(5).add(new Edge(0, 7));
graph.get(5).add(new Edge(3, 2));
graph.get(5).add(new Edge(4, 3));
// 시작점을 A(0)이라 하고 다익스트라 실행
int start = 0;
int[] dist = dijkstraList(graph, n, start);
// 결과 출력
char[] name = {'A','B','C','D','E','F'};
for (int i = 0; i < n; i++) {
System.out.println(name[start] + " → " + name[i]
+ " 최단 거리: " + dist[i]);
}
}
/**
* 인접 리스트를 이용한 다익스트라 (우선순위 큐 미사용: O(V^2))
* @param graph 인접 리스트
* @param n 정점 개수
* @param start 시작 정점
* @return dist[] : 시작점으로부터 각 정점까지의 최단 거리
*/
public static int[] dijkstraList(List<List<Edge>> graph, int n, int start) {
int[] dist = new int[n]; // 거리 테이블
boolean[] visited = new boolean[n]; // 방문 여부
// 1. dist 초기화
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
dist[start] = 0;
// 2. 모든 정점을 하나씩 처리
for (int i = 0; i < n; i++) {
// 2-1. 방문하지 않은 정점 중 dist가 가장 작은 정점(u) 찾기
int u = -1;
int minDist = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
// 더 이상 갈 정점이 없으면 중단
if (u == -1) break;
// 2-2. u 정점 방문 처리
visited[u] = true;
// 2-3. u와 인접한 정점들에 대해 거리 갱신
for (Edge edge : graph.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
return dist;
}
}
1) 인접 리스트 생성
List<List<Edge>> graph를 이용해, 각 정점별로 연결된 간선을 List 형태로 저장- 예)
graph.get(0).add(new Edge(1, 2))→ A(0)에서 B(1)로 가중치 2
2) 다익스트라 알고리즘(dijkstraList)
- (1)
dist[]를 무한대로 초기화 후,dist[start] = 0 - (2) 방문 안 한 정점 중
dist[]가 가장 작은 정점을 찾아서visited[u] = true처리 - (3)
graph.get(u)(즉 u의 인접 리스트) 전체를 순회하며,dist[u] + 가중치가dist[v]보다 작다면 갱신
3) 시간 복잡도: O(V^2)
- “방문 안 한 정점 중 최소 dist 정점 찾기”가 매번 O(V)
- 총 V번 반복하므로 O(V^2)
- 이 부분은 다음에 살펴볼 우선순위 큐를 사용하면 O(E log V) 로 최적화가 가능해진다.
6.4. 인접 리스트 방식의 장단점
- 장점
- “그래프가 큰데 간선이 적은” 경우, 메모리를 훨씬 절약할 수 있음
- 어떤 정점에 직접 연결된 간선들만 순회할 수 있어, 갱신 시에도 불필요한 반복이 줄어듦
- 단점
- “정점 i에서 j로 가는 간선이 있는지”를 바로 확인하기 힘듦 (행렬의
graph[i][j]접근이 아님) - 이 자체로는 “방문 안 한 정점 중 최소 dist 정점 찾기”에 O(V) 시간이 들기 때문에, 큰 그래프에서는 여전히 느림 (→ 우선순위 큐 필요)
- “정점 i에서 j로 가는 간선이 있는지”를 바로 확인하기 힘듦 (행렬의
6.5. 우선순위 큐(Priority Queue) 활용
위 코드(인접 리스트 + 단순 선형 검색)는 정점 수가 많은 경우, “다익스트라의 효율적인 구현”이라 하기엔 부족하다.
왜 그럴까? 예를 들어 생각해보자.
6.5.1. 2차원 행렬(인접 행렬)로 구현 시의 문제
- 공간 복잡도: 정점이 V개라면, V×V 크기의 2차원 배열을 만들어야 한다.
- 예: 정점이 10,000개라면, 10,000 × 10,000 = 1억 개의 원소를 저장해야 함
- 메모리 사용량이 매우 커져서 실용적이지 않을 수 있음.
- 시간 복잡도: 매번 “방문 안 한 정점 중 dist가 가장 작은 정점”을 찾기 위해 O(V) 스캔,
그리고 모든 정점에 대해 이 과정을 반복하니 O(V^2)- V가 클수록 연산 시간이 크게 증가
6.5.2. 인접 리스트 + 선형 검색(기본 다익스트라) 시의 문제
- 인접 리스트는 메모리 절약에 좋지만, “가장 짧은 dist 정점 찾기”를 선형 검색으로 처리하면 여전히 O(V)
- 전체 정점을 V번 방문해야 하므로, 최악의 경우 O(V^2)의 시간 복잡도
- 예:
- 정점 수 V가 10만에 가깝다면, 최악의 경우 10만 × 10만 = 100억 정도의 연산이 필요할 수도 있음
- 실제 프로젝트나 대규모 데이터에서는 실행 시간이 너무 오래 걸리는 상황이 발생
이러한 문제를 우선순위 큐를 써서 해결할 수 있을까?
7. 구현 디테일 3: 우선순위 큐 사용
7.1. 왜 우선순위 큐인가?
- 핵심: 매번 “아직 방문하지 않은 정점들 중 가장 짧은 거리를 가진 정점”을 빠르게 추출해야 함.
- 선형 검색 방식:
- 모든 미방문 정점을 훑어야 하므로 O(V)
- V개의 정점을 차례대로 방문하면 O(V^2)
- 우선순위 큐(Min-Heap) 활용:
- “가장 작은 거리값”을 로그 시간(O(log V))에 추출 가능
- 결과적으로 O(E log V)에 가까운 실행 속도를 낼 수 있음 (E = 간선 수)
즉,
- 매번 “가장 짧은 dist”를 가진 정점을 O(log V)로 꺼낼 수 있음
- 간선이 총 E개라 하면, O(E log V)로 다익스트라 알고리즘을 구동 가능
- 실제로 V가 수천~수만 이상일 경우, 우선순위 큐를 사용하는 다익스트라 구현이 훨씬 빠르고 실용적
예시 시나리오:
- V = 1만, E = 10만 정도의 그래프
- 인접 리스트 + 선형 검색: O(V^2) = 1억 연산에 육박 (혹은 경우에 따라 더 클 수도)
- 인접 리스트 + 우선순위 큐: O(E log V) ≈ 10만 × (log(1만)) → 대략 10만 × 13~14 정도 = 130~140만 연산
따라서 전체 알고리즘 복잡도도 O(V^2) → O(E log V) 로 크게 개선된다.
7.2. 자바 코드 예시 (인접 리스트 + 우선순위 큐)
아래 예시는
- “정점 A=0, B=1, C=2, D=3, E=4, F=5”
- “인접 리스트로 그래프를 관리”
- “우선순위 큐를 통해 가장 작은
dist의 정점을 빠르게 추출”
하는 다익스트라 코드이다.
import java.util.*;
public class DijkstraPQ {
static final int INF = 999999999;
// 간선 정보 저장용 클래스
static class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
// 우선순위 큐에 넣을 노드 정보
// dist 값이 작은 순으로 정렬하기 위해 Comparable 구현
static class Node implements Comparable<Node> {
int index; // 정점 번호
int dist; // 시작점부터 해당 정점까지의 거리
public Node(int index, int dist) {
this.index = index;
this.dist = dist;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.dist, other.dist);
}
}
public static void main(String[] args) {
int n = 6; // 정점 개수 (A=0, B=1, C=2, D=3, E=4, F=5)
// 인접 리스트 생성
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 그래프 세팅 (무방향/방향 여부에 맞춰 간선 추가)
// A(0)->B(1):2, C(2):5, F(5):7
graph.get(0).add(new Edge(1, 2));
graph.get(0).add(new Edge(2, 5));
graph.get(0).add(new Edge(5, 7));
// B(1)->A(0):2, C(2):1, D(3):2
graph.get(1).add(new Edge(0, 2));
graph.get(1).add(new Edge(2, 1));
graph.get(1).add(new Edge(3, 2));
// C(2)->A(0):5, B(1):1, D(3):3, E(4):4
graph.get(2).add(new Edge(0, 5));
graph.get(2).add(new Edge(1, 1));
graph.get(2).add(new Edge(3, 3));
graph.get(2).add(new Edge(4, 4));
// D(3)->B(1):2, C(2):3, E(4):1, F(5):2
graph.get(3).add(new Edge(1, 2));
graph.get(3).add(new Edge(2, 3));
graph.get(3).add(new Edge(4, 1));
graph.get(3).add(new Edge(5, 2));
// E(4)->C(2):4, D(3):1, F(5):3
graph.get(4).add(new Edge(2, 4));
graph.get(4).add(new Edge(3, 1));
graph.get(4).add(new Edge(5, 3));
// F(5)->A(0):7, D(3):2, E(4):3
graph.get(5).add(new Edge(0, 7));
graph.get(5).add(new Edge(3, 2));
graph.get(5).add(new Edge(4, 3));
// 시작점을 A(0)이라 하고 다익스트라 실행
int start = 0;
int[] dist = dijkstraWithPQ(graph, n, start);
// 결과 출력
char[] name = {'A','B','C','D','E','F'};
for (int i = 0; i < n; i++) {
System.out.println(name[start] + " → " + name[i]
+ " 최단 거리: " + dist[i]);
}
}
/**
* 인접 리스트 + 우선순위 큐를 이용한 다익스트라 (O(E log V))
*/
public static int[] dijkstraWithPQ(List<List<Edge>> graph, int n, int start) {
// 거리 테이블 (dist)
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[start] = 0;
// 우선순위 큐 (Min-Heap) : Node.dist가 작은 순으로 꺼냄
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0)); // 시작점 (dist=0)
// 방문 여부(optional): 꼭 필요하진 않지만, 불필요한 중복 계산 방지
boolean[] visited = new boolean[n];
while (!pq.isEmpty()) {
// 1. 가장 dist가 작은 정점 꺼내기
Node currentNode = pq.poll();
int u = currentNode.index;
int currentDist = currentNode.dist;
// 이미 방문한 적이 있거나, dist 테이블의 값보다 크면 무시
if (visited[u]) continue;
if (currentDist > dist[u]) continue;
// 2. 현재 정점 u를 방문 처리
visited[u] = true;
// 3. u와 인접한 모든 간선 확인하여 거리 갱신
for (Edge edge : graph.get(u)) {
int v = edge.to;
int cost = edge.weight;
// (u까지 거리 + u→v 비용)이 v의 현재 dist보다 작다면 갱신
if (dist[u] + cost < dist[v]) {
dist[v] = dist[u] + cost;
// 갱신된 거리값으로 우선순위 큐에 넣기
pq.offer(new Node(v, dist[v]));
}
}
}
return dist;
}
}
1) 우선순위 큐(PriorityQueue) 초기화
PriorityQueue<Node>를 사용.Node클래스는Comparable을 구현해,dist가 작은 순서대로 정렬됨.
2) 큐에서 노드를 꺼낼 때
pq.poll()하면, 현재 “가장 짧은 dist”를 가진 정점 정보가 나옴.- 만약 이미
visited[u] = true라면, (즉, 최단 거리가 확정된 정점이라면) 다시 볼 필요가 없으므로 continue.
3) 거리 갱신
dist[v] = dist[u] + cost(더 짧다면)- 갱신된 경우,
pq.offer(new Node(v, dist[v]))- 이렇게 하면, 새롭게 더 짧은 거리값을 가진
v가 우선순위 큐에서 빠르게 추출 가능
- 이렇게 하면, 새롭게 더 짧은 거리값을 가진
4) 복잡도: O(E log V)
- 매 간선마다 최대 한 번씩은 갱신이 일어나고, 갱신 시 우선순위 큐에 삽입(offer) → O(log V)
- 따라서 전체적으로 O(E log V)에 수렴
시퀀스로 살펴보면 아래와 같다.
sequenceDiagram
participant Main as 다익스트라 알고리즘
participant PQ as 우선순위 큐 (Min-Heap)
Main->>PQ: offer(A, dist=0)
Note right of Main: 시작점 A(거리=0)를 큐에 삽입
loop while PQ is not empty
Main->>PQ: poll()
PQ-->>Main: (u, currentDist) 꺼냄 (가장 작은 dist)
alt visited[u] == true or currentDist > dist[u]
Note right of Main: 이미 방문했거나<br/>낡은 정보면 스킵
Main->>PQ: continue
else
Main->>Main: visited[u] = true
Main->>Main: u의 이웃 v들 거리 갱신
alt dist[u] + weight < dist[v]
Main->>PQ: offer(v, dist[v] 갱신)
else
Note right of Main: 갱신 없음
end
end
end
Note over Main: 모든 정점 방문 or PQ empty<br/>→ dist[] 완성!
7.3. 우선순위 큐 방식에서의 방문 배열(visited[]) 사용 여부
- 사용하는 경우
- “이미 최단 거리가 확정된 정점”을 다시 꺼내게 되면, 즉시 스킵할 수 있음
- 불필요한 연산을 어느 정도 줄여줘서 (특히 만약 큐에 중복 데이터가 많이 들어가는 경우) 실질적인 성능이 향상될 수 있음
- 사용하지 않는 경우
- dist 값만 비교해서, “큐에서 꺼낸 dist가 dist테이블에 기록된 값보다 크면 무시”하는 방식으로 구현 가능 (Lazy Deletion 기법)
- 다만, 큐 안에 “낡은(더 이상 유효하지 않은) 정보”가 많아지면, 그만큼
poll()연산 때 불필요한 데이터가 뜯겨나가므로, 성능이 다소 저하될 수도 있음
실제로는 둘 다 자주 쓰이는 방식이다.
7.4. 다익스트라 알고리즘 정리
- 인접 리스트 + 우선순위 큐
- 그래프를 “정점별 간선 리스트”로 저장
- “가장 짧은 dist를 가진 정점”을 우선순위 큐에서 O(log V)에 꺼냄
- 해당 정점의 이웃 간선에 대해 거리 갱신 → 큐에 삽입
- 모든 정점(또는 우선순위 큐가 빌 때)까지 반복
- 시간 복잡도는 일반적으로 O(E log V)가 되어, 큰 그래프에서도 비교적 빠르게 동작
Q. 왜 음수면 안될까?
다익스트라 알고리즘은 기본적으로 “간선 가중치가 모두 0 이상(비음수)”이라는 전제를 깔고 있다.
즉, 간선에 음수(-) 가중치가 있으면, 다익스트라의 그리디 전략이 성립하지 않는다.
왜 그럴까?
1) 다익스트라 알고리즘의 그리디(탐욕적) 성격
- 다익스트라는 “이미 찾아낸 최단 거리”가 절대로 더 줄어들 수 없다는 전제 하에 진행한다.
- 예: A에서 B까지 최단 거리가 5라고 확정했다면, 다른 경로를 더 탐색해도 “5보다 더 작은 값”은 나올 수 없다고 보는 것이다.
- 이 전제는 간선 가중치가 모두 0 이상이라는 조건 덕분에 성립한다.
- 음수 가중치가 없으니, 경로를 더 추가로 거칠수록 거리가 줄어드는 상황이 발생하지 않는다는 것.
- 음수 가중치가 없으니, 경로를 더 추가로 거칠수록 거리가 줄어드는 상황이 발생하지 않는다는 것.
2) 음수 가중치 예시
가령 아래처럼, B에서 C로 가는 간선이 -2의 가중치를 가진다고 해보자.
A --(2)--> B --(-2)--> C
- A에서 B까지 거리 = 2
- B에서 C까지 거리 = -2
- A → B → C 경로 전체 거리 = 2 + (-2) = 0
만약 다익스트라 알고리즘이 A에서 출발해 B(거리=2)를 가장 먼저 최단 거리로 확정지었다면,
- B 방문 시, C에 갱신되는 거리는 2 + (-2) = 0
- 일단 C도 0으로 확정됐다고 치고 넘어갈 수 있음
그런데, 만약 그래프 어딘가를 돌아서 더 큰 음수 간선을 또 만나게 되면,
- 이미 “C=0”이라고 확정해 놓았어도, 실제로는 더 작은(음수) 값으로 갱신될 수 있는 경로가 늦게 발견될 수 있다.
- 다익스트라는 한 번 확정된 값을 “변경 불가”로 처리하므로, 음수 간선 때문에 뒤늦게 더 짧은 경로가 발견되더라도 반영하지 못하게 된다.
또 다른 문제: 음수 사이클(Negative Cycle)
- 만약 음수 간선으로 구성된 순환 경로가 있어, 순환할 때마다 거리가 계속 줄어드는 구조라면, “최단 거리” 자체가 정의되지 않는 경우도 생긴다(무한히 작은 값).
- 다익스트라는 이런 음수 사이클을 감지하지 못하고, 잘못된 최단 거리를 계산할 수 있다.
3) 음수 간선이 있을 땐 다른 알고리즘 사용
- 벨만-포드(Bellman-Ford) 알고리즘
- 음수 간선이 있어도, 음수 사이클이 없는 경우라면 최단 거리를 구할 수 있음
- 음수 사이클이 존재하면 그 사실을 감지 가능
- 시간 복잡도: O(V×E)
- 플로이드-워셜(Floyd-Warshall) 알고리즘
- 모든 정점 쌍 간 최단 거리를 구하는 방식
- 음수 간선이 있어도(음수 사이클 제외) 잘 동작
- 시간 복잡도: O(V³), 주로 정점 수가 크지 않을 때 사용
정리하자면, 다익스트라 알고리즘은 음수 간선이 없는 그래프에서만 동작이 보장되는 그리디 알고리즘이다.
Q. 어디에 사용될까?
다익스트라 알고리즘은 “시작 정점에서 다른 모든 정점까지의 최단 경로”를 찾아내는 데 최적화된 방법이므로, 현실 세계나 컴퓨터 과학 전반에서 매우 폭넓게 사용된다.
1) 네비게이션 및 지도 서비스
- 자동차 네비게이션, 지도 앱(구글 지도, 네이버 지도, 카카오맵 등) 에서 “가장 빠른 길”을 탐색할 때 사용
- 도로망을 그래프로 보고, “도로 구간(간선)의 이동 시간(가중치)”를 활용해 특정 지점에서 다른 지점까지의 최단 경로를 구함
- 실시간 교통 정보가 반영되면, “최단 시간”이 계속 달라지므로, 다익스트라 알고리즘을 적절히 수정하거나 다른 알고리즘(A* 등)과 혼합해 사용하기도 함
2) 게임 개발 (경로 찾기)
- 실시간 전략 시뮬레이션(RTS) 게임, RPG 등에서 “캐릭터가 특정 위치까지 이동할 때 최단 경로를 찾는 문제”
- 지형을 격자나 그래프로 표현하고, 이동 비용(가중치)이 낮은 루트를 탐색
- 다만, 장애물이나 휴리스틱(추정 거리)을 더해 A* 알고리즘 같은 변형을 쓰기도 하지만, 그 기본 메커니즘은 다익스트라와 유사
3) 네트워크 라우팅
- 컴퓨터 네트워크의 라우터(라우팅 프로토콜)에서, 특정 노드를 시작으로 다른 노드까지 “데이터 패킷 경로”를 찾는 데 활용
- 예: OSPF(Open Shortest Path First) 프로토콜은 내부적으로 다익스트라 알고리즘을 사용해 “링크 상태” 정보를 토대로 최단 경로 트리를 구성
- 네트워크 연결 상태(간선)와 대역폭(가중치)에 따라 “최단 전송 경로”를 탐색하는 것이 핵심
4) 지하철/버스 노선도, 물류 배송 경로 최적화
- 지하철 노선도, 버스 노선 망 등에서 “환승 횟수”, “이동 시간” 등을 가중치로 두고, 출발역에서 도착역까지의 최단 소요 시간을 구할 수 있음
- 물류 배송이나 배달 경로 최적화에서도, 거점(정점)과 이동 비용(간선)을 그래프로 모델링한 뒤 다익스트라로 가장 효율적인 경로 계산 가능
5) 그래프 이론 문제 일반
- 각종 알고리즘 문제 풀이 사이트(백준, 프로그래머스 등)에서 주어진 그래프의 최단 경로를 묻는 문제에 다익스트라를 자주 사용
- V, E가 크지 않은 경우엔 2차원 행렬 방식도 쓰이지만, 수만 이상으로 커지면 인접 리스트 + 우선순위 큐 방식이 효율적
- 간선이 음수이면 안 된다는 조건만 주어지면, 다익스트라를 떠올리면 되는 경우가 많음
6) 기타 응용
- 인터넷 지도 API나 GIS(지리정보 시스템), 로보틱스(로봇 경로 계획) 등 “경로 최적화”가 필요한 분야 전반에 쓰임
- 사회 네트워크 분석에서, 특정 노드(사람)로부터 다른 노드(사람)까지의 “최단 연결 고리”를 찾는 등, 경로 기반 분석에도 응용 가능
정리하자면, 다익스트라 알고리즘은 “최단 경로”를 필요로 하는 다양한 서비스와 기술에 폭넓게 적용된다.
반응형