[Java] 다익스트라 알고리즘(최단거리 알고리즘)

다익스트라 알고리즘

다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다.

다익스트라 알고리즘을 구현하는 과정은 다음과 같다.

1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음에는 시작 정점을 방문한다.)
2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.

프로그래머스의 배달 문제의 그래프를 예시로 다익스트라 알고리즘을 설명해보겠다.

• 1번 정점을 시작 정점으로 잡고 1번 정점에서 방문할 수 있는 각 정점까지의 거리를 표시한다.
• 1번 정점에서 방문할 수 없는 정점은 INF(무한대)로 표시해둔다.

• 방문하지 않은 정점 중 가장 거리가 짧은 2번 정점을 방문한다.
• 1번 정점에서 2번 정점을 거쳐 3번 정점을 방문하면 기존 거리(INF)보다 가까워지므로 갱신한다.(INF → 4)
• 1번 정점에서 2번 정점을 거쳐 5번 정점을 방문하면 기존 거리(INF)보다 가까워지므로 갱신한다.(INF → 3)

• 방문하지 않은 정점 중 가장 거리가 짧은 4번 정점을 방문한다.
• 갱신할 정보가 없다.

• 방문하지 않은 정점 중 가장 거리가 짧은 5번 정점을 방문한다.
• 갱신할 정보가 없다.

• 방문하지 않은 정점 중 가장 거리가 짧은 5번 정점을 방문한다.
• 갱신할 정보가 없다.
• 모든 정점을 방문했으므로 종료한다.

위의 과정을 거쳐 모든 정점을 방문하면 최단 거리가 기록되게 된다.

Java를 사용한 다익스트라 알고리즘 구현

다익스트라 알고리즘을 구현하는 방식은 인접 행렬 방식과 우선순위 큐 방식이 있다. 노드의 개수가 n일 때 인접 행렬 방식의 시간 복잡도는 O(n^2) 우선순위 큐 방식은 O(nlogn)의 시간 복잡도를 가진다.

인접 행렬으로 구현한 다익스트라

package graph;

import java.util.Arrays;
import java.util.Scanner;

public class Dijkstra {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int[][] adj = new int[V][V];
		for (int i = 0; i < E; i++) {
			adj[sc.nextInt()][sc.nextInt()] = sc.nextInt();
		}
		int[] D = new int[V];
		Arrays.fill(D, Integer.MAX_VALUE);
		boolean[] check = new boolean[V];

		D[0] = 0;
		for (int i = 0; i < V - 1; i++) {
			int min = Integer.MAX_VALUE;
			int index = -1;
			for (int j = 0; j < V; j++) {
				// 아직 방문하지 않았으면서, 최단 거리라면
				if (!check[j] && min > D[j]) {
					index = j;
					min = D[j];
				}
			}

			for (int j = 0; j < V; j++) {
				// 아직 방문하지 않았으면서 경로가 존재하고, index까지의 거리 + index부터 j까지의 거리가 D[j]보다 작다면
				if (!check[j] && adj[index][j] != 0 && D[index] != Integer.MAX_VALUE
						&& D[index] + adj[index][j] < D[j]) {
					D[j] = D[index] + adj[index][j];
				}
			}
			check[index] = true;
		}
		System.out.println(Arrays.toString(D));
	}

}

우선순위 큐로 구현한 다익스트라

package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Dijkstra_pq {
	
	static class Edge implements Comparable<Edge> {
		int v, weight;

		public Edge(int v, int weight) {
			this.v = v;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.weight, o.weight);
		}

		@Override
		public String toString() {
			return weight + "";
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		List<Edge>[] adj = new ArrayList[V];
		for (int i = 0; i < V; i++)
			adj[i] = new ArrayList<>();
		for (int i = 0; i < E; i++) {
			// 첫번째가 출발지, 두번째가 도착지, 세번째가 가중치ㅋ
			adj[sc.nextInt()].add(new Edge(sc.nextInt(), sc.nextInt()));
		}
		//
		// dijkstra
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] check = new boolean[V];
		Edge[] D = new Edge[V];
		// 0번에서 출발하는걸로.
		for (int i = 0; i < V; i++) {
			// 원하는 출발지
			if (i == 0) {
				D[i] = new Edge(i, 0);
			} else {
				D[i] = new Edge(i, Integer.MAX_VALUE);
			}
			pq.add(D[i]);
		}
		while (!pq.isEmpty()) {
			Edge edge = pq.poll();

			for (Edge next : adj[edge.v]) {
				// check되지 않았으면서, D[next.v]가 D[edge.v] + next.weight 보다 더 크다면 갱신
				if (!check[next.v] && D[next.v].weight > D[edge.v].weight + next.weight) {
					D[next.v].weight = D[edge.v].weight + next.weight;
					// decrease key
					pq.remove(D[next.v]);
					pq.add(D[next.v]);
				}
			}
			check[edge.v] = true;
		}
		System.out.println(Arrays.toString(D));
	}
}