다익스트라 알고리즘은 너비 우선 탐색(BFS)와 다이나믹 프로그래밍(Dynamic Programming)을 활용하여 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다.
음의 간선을 포함할 수 없기 때문에 음의 간선이 존재하지 않는 현실 세계에서 사용하기 매우 적합한 알고리즘이다.
다익스트라 알고리즘은 다이나믹 프로그래밍을 활용하는데, 최단 거리는 여러 개의 최단 거리로 이루어져있다는 성질을 이용하기 때문이다.
따라서, 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용한다.
동작 과정
- 출발 정점을 설정한다.
- 출발 정점을 기준으로 연결된 정점의 비용을 저장한다.
- 방문하지 않은 정점들 중에서 최단 거리인 정점을 선택한다.
- 해당 정점을 거쳐서 특정한 정점으로 가는 경우를 고려하여 최소 비용을 갱신한다.
- 3번과 4번 과정을 반복한다.
소스 코드
인접행렬 - O(V^2)
public class Dijkstra_Array {
static int[][] adj;
static int[] dis;
static boolean[] v;
static int N = 6;
public static void main(String[] args) {
adj = new int[N][N];
dis = new int[N];
v = new boolean[N];
// 인접행렬과 최단 거리 행렬의 모든 값을 무한대로 초기화
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
adj[i][j] = Integer.MAX_VALUE;
}
}
Arrays.fill(dis, Integer.MAX_VALUE);
// 시작 정점, 끝 정점, 간선 가중치 입력
input(0, 1, 7);
input(0, 2, 9);
input(0, 5, 14);
input(1, 2, 10);
input(1, 3, 15);
input(2, 3, 11);
input(2, 5, 2);
input(3, 4, 6);
input(4, 5, 9);
dijkstra(0);
}
private static void input(int i, int j, int w) {
adj[i][j] = w;
adj[j][i] = w;
}
private static void dijkstra(int node) {
// 시작 정점 초기화
dis[node] = 0;
v[node] = true;
// 연결 정점과의 거리 갱신
for(int i = 0; i < N; i++) {
if(!v[i] && adj[node][i] != Integer.MAX_VALUE) {
dis[i] = adj[node][i];
}
}
// 정점이 N개 있을 때 반복수는 N-1번이면 된다.
for(int i = 0; i < N-1; i++) {
int min = Integer.MAX_VALUE;
int minIdx = -1;
// 연결된 정점 중에서 최소 거리인 정점 찾기
for(int j = 0; j < N; j++) {
if(!v[j] && dis[j] < min) {
min = dis[j];
minIdx = j;
}
}
// 방문 체크
v[minIdx] = true;
// 현재 선택한 정점을 통해 갈 수 있는 정점과의 거리 갱신
for(int j = 0; j < N; j++) {
// 아직 방문하지 않았으면서 연결되어있는 정점
if(!v[j] && adj[minIdx][j] != Integer.MAX_VALUE) {
// 현재 선택한 정점을 통해 가는 거리가 바로 가는 거리보다 짧으면 갱신
if(adj[minIdx][j] + dis[minIdx] < dis[j]) {
dis[j] = adj[minIdx][j] + dis[minIdx];
}
}
}
}
System.out.println(Arrays.toString(dis));
}
}우선순위 큐 - O(ElogV)
public class Dijkstra_PQ {
static class Edge implements Comparable<Edge> {
int next, weight;
public Edge(int next, int weight) {
this.next = next;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
static PriorityQueue<Edge> pq = new PriorityQueue<>();
static int[][] adj;
static int[] dis;
static boolean[] v;
static int N = 6;
public static void main(String[] args) {
adj = new int[N][N];
dis = new int[N];
v = new boolean[N];
// 인접행렬과 최단 거리 행렬의 모든 값을 무한대로 초기화
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
adj[i][j] = Integer.MAX_VALUE;
}
}
Arrays.fill(dis, Integer.MAX_VALUE);
// 시작 정점, 끝 정점, 간선 가중치 입력
input(0, 1, 7);
input(0, 2, 9);
input(0, 5, 14);
input(1, 2, 10);
input(1, 3, 15);
input(2, 3, 11);
input(2, 5, 2);
input(3, 4, 6);
input(4, 5, 9);
dijkstra(0);
}
private static void input(int i, int j, int w) {
adj[i][j] = w;
adj[j][i] = w;
}
private static void dijkstra(int node) {
// 시작 정점 초기화
pq.offer(new Edge(0, node));
dis[node] = 0;
v[node] = true;
// 연결 정점과의 거리 갱신
for(int i = 0; i < N; i++) {
if(!v[i] && adj[node][i] != Integer.MAX_VALUE) {
dis[i] = adj[node][i];
pq.offer(new Edge(i, adj[node][i]));
}
}
// 정점이 N개 있을 때 반복수는 N-1번이면 된다.
while(!pq.isEmpty()) {
// 노드 최솟값 꺼내기
Edge e = pq.poll();
int minIdx = e.next;
// 방문 체크
v[minIdx] = true;
// 현재 선택한 정점을 통해 갈 수 있는 정점과의 거리 갱신
for(int j = 0; j < N; j++) {
// 아직 방문하지 않았으면서 연결되어있는 정점
if(!v[j] && adj[minIdx][j] != Integer.MAX_VALUE) {
// 현재 선택한 정점을 통해 가는 거리가 바로 가는 거리보다 짧으면 갱신
if(adj[minIdx][j] + dis[minIdx] < dis[j]) {
dis[j] = adj[minIdx][j] + dis[minIdx];
pq.offer(new Edge(j, dis[j]));
}
}
}
}
System.out.println(Arrays.toString(dis));
}
}[참고]
