[JAVA] 최단 거리 알고리즘 - 다익스트라 <Dijkstra>

최단 거리 알고리즘 - 다익스트라 <Dijkstra>

다익스트라 알고리즘은 흔히 알고있듯, 최단 거리를 구하는 데 초점이 맞춰진 알고리즘이다.

우리가 아는 유명한 최단 거리 알고리즘이 무엇이 있을까?

아마 BFS가 떠오를 것인데, BFS와의 차이점은 거리(가중치)가 1이 아니라는 점이다.

즉, BFS는 현재 칸에서 다음 칸으로 이동하면 거리(가중치)가 1이 증가하는데 반해 다익스트라는 임의의 가중치가 존재한다.

학문적으로는 가중치가 있는 그래프에서 하나의 시작 정점으로부터 모든 정점들까지의 최단 거리를 구하는 알고리즘이라고 설명할 수 있겠다.

또 다른 이야기를 해보자면, 이전에 업로드했었던 Prim 알고리즘과도 다소 유사한 모습을 보인다.

프림 알고리즘와 다익스트라 알고리즘 모두 PriorityQueue를 사용하고 다소 그리디하게 동작하기 때문이다.

추가로 간선의 가중치가 음수일 때는 다익스트라 알고리즘을 사용하지 못한다. 음수 가중치가 개입되는 순간, 최단 거리라고 생각했던 것이 최단이 아닐 수 있듯, 논리적으로 심각한 문제가 발생하게 된다. 따라서 이러한 상황에서는 벨만-포드 알고리즘을 사용하면 되고, 간선의 양수 가중치만을 가지고 있을 때는 다익스트라 알고리즘으로 쉽게 해결할 수 있다.

다익스트라 알고리즘 동작 원리

1. 임의의 출발 노드를 선택해서 가중치 0으로 시작

2. 현재까지의 최단 거리가 확정되지 않은 노드 중, 가장 짧은 거리를 가진 노드를 선택.

3. 해당 노드와 연결된 인접 노드들의 거리를 확인하고 기존 거리보다 더 짧으면 갱신

4. 모든 노드가 확정될 때까지 2 ~ 3번의 과정을 반복.

핵심 자료 구조

거리 배열 (int dist[]): 시작점에서 각 정점까지의 최소 비용 저장 (dp를 이용해서 갱신함)
방문 배열 (boolean visited[]): 최단 거리가 확정된 노드 체크
우선순위 큐 (PriorityQueue pq): 항상 현재 가장 짧은 거리의 노드를 보장하기 위해서 사용

다른 알고리즘과의 차이점 by GPT

다익스트라	최단 거리 (단일 시작점 → 모든 정점)	가중치 ≥ 0	가장 가까운 정점부터 거리 갱신 (Greedy)	O(E log V)	네비게이션, 네트워크 경로
크루스칼	최소 신장 트리 (MST)	무방향, 가중치 있음	간선을 가중치 순 정렬 + 사이클 방지	O(E log E)	도로 건설, 통신망 비용 최소화
프림	최소 신장 트리 (MST)	무방향, 가중치 있음	정점에서 시작해 최소 간선 확장	O(E log V)	전력망 연결, 네트워크 구축
BFS	그래프 탐색, 최단 거리 (무가중치)	무가중치 그래프	레벨별 탐색 (큐)	O(V + E)	미로 탐색, 소셜 네트워크 탐색

사실 문제를 많이 풀어보진 않았지만, 다소 헷갈리는 내용이 많았다.

느끼기에는 프림 알고리즘과 다익스트라가 매우 유사하게 느껴졌고 크루스칼과도 헷갈리기도 했다.

언제 어떻게 사용해야 하는건지에 대한 기준이 확립되지 않아서 더욱 그렇게 느낀 게 아닐까?

결국 크루스칼/프림 알고리즘은 최소 스패닝 트리를 구성하는 데에 목적이 맞춰져 있다는 걸 명심해야 한다.

모든 정점을 연결하면서 가중치들의 합이 최소가 되게끔 구성하는 것.

그에 반면 다익스트라 알고리즘은 서두에서 이야기 했듯이 최단 거리를 구하는 데 초점이 맞춰져 있다.

시작 정점에서 다른 모든 정점으로의 최단 거리가 저장되어 있다는 것이다!!

헷갈릴 게 하나도 없는데 왜 처음 접했을 때부터 비교적 최근까지 왜 그렇게 헷갈렸는지 알 수가 없다.

이래서 텀을 두고 공부를 해야하나 보다. 복습을 철저히..

코드 전문

BOJ 1916 - 최소비용 구하기

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_1916 {
	
	public static class Vertex implements Comparable<Vertex>{
		int idx;
		int weight;
		
		public Vertex(int idx, int weight) {
			this.idx = idx;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.weight, o.weight);
		}
	}

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        ArrayList<Vertex>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
        
        for (int i = 0; i < M; i++) {
        	st = new StringTokenizer(br.readLine());
        	
        	int start = Integer.parseInt(st.nextToken());
        	int end = Integer.parseInt(st.nextToken());
        	int weight = Integer.parseInt(st.nextToken());
        	
        	graph[start].add(new Vertex(end, weight));
        }

    	st = new StringTokenizer(br.readLine());
    	
    	int start = Integer.parseInt(st.nextToken());
    	int end = Integer.parseInt(st.nextToken());
    	
    	int[] dist = new int[N + 1];
    	Arrays.fill(dist, Integer.MAX_VALUE - 100_000);
    	
    	PriorityQueue<Vertex> pq = new PriorityQueue<>();
    	boolean[] visited = new boolean[N + 1];
    	
    	pq.add(new Vertex(start, 0));
    	dist[start] = 0;
    	
    	while (!pq.isEmpty()) {
    		Vertex cur = pq.poll();
    		
    		if (visited[cur.idx]) continue;
    		visited[cur.idx] = true;
    		
    		for (Vertex next : graph[cur.idx]) {
    			if (dist[next.idx] > dist[cur.idx] + next.weight) {
    				dist[next.idx] = dist[cur.idx] + next.weight;
    				pq.add(new Vertex(next.idx, dist[next.idx]));
    			}
    		}
    	}
    	
    	System.out.println(dist[end]);
    	
    }
}

코드 해설

다익스트라 문제들 중에서 비교적 간단한 문제이고 개념을 익히기 좋은 문제인 것 같다.

	public static class Vertex implements Comparable<Vertex>{
		int idx;
		int weight;
		
		public Vertex(int idx, int weight) {
			this.idx = idx;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.weight, o.weight);
		}
	}

우선, 정점 클래스를 정의해주었다.
- 해당 정점 클래스의 필드로는 idx(정점의 번호), weight(현재 노드에 이르기까지 계산된 가중치의 합)
- PriorityQueue를 위해 구현해준 compareTo 메서드
추가로, 왜 여기선 시작 정점과 도착 정점을 담지 않고 정점의 idx를 필드로 가지고 있을까?
- 다익스트라 알고리즘의 동작 과정이 특정 정점을 기준으로 점점 확장해나가는 형태이기 때문.
- 시작 정점에서 그 다음 정점.. 그 다음 정점.. 쭉 확장되면서 나아감.
- 크루스칼 알고리즘의 경우에는 간선에 포커스를 맞춘 알고리즘이기에 시작 정점과 도착 정점이 필요하기 때문에 Edge 클래스를 정의해주었음.
- 프림 알고리즘의 경우에는 임의의 정점에서 이웃된 정점들 중 가장 가중치가 작은 정점들을 선택해나가기 때문에 다익스트라와 마찬가지로 현재 정점의 정보만을 가진 Vertex 또는 Node 클래스를 정의해준 것.
  - 프림 알고리즘 게시글을 보면 정점의 정보를 to로 정의해주었는데, 사실상 현재 정점의 idx과 다른 의미로 사용한거지만 로직 상으로는 동일한 의미를 가짐.
  - 또 엄밀히 따지자면 다익스트라 알고리즘에서도 두가지 의미로 사용됨.
  - 문맥 1 (그래프 저장: graph[u].add(new Vertex(v, w)))
    - - idx = 도착 정점 v
      - weight = 그 간선의 가중치 w (edge weight)
    - 문맥 2 (우선순위큐에 넣을 때: pq.add(new Vertex(v, dist[v])))
      - idx = 해당 정점 v
      - weight = 그 정점까지의 누적 최단거리(현재 후보값) dist[v] (tentative distance)
    - 즉 같은 Vertex 타입을 사용하지만 weight의 의미가 컨텍스트에 따라 달라짐 (edge weight vs. accumulated distance).

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        ArrayList<Vertex>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
        
        for (int i = 0; i < M; i++) {
        	st = new StringTokenizer(br.readLine());
        	
        	int start = Integer.parseInt(st.nextToken());
        	int end = Integer.parseInt(st.nextToken());
        	int weight = Integer.parseInt(st.nextToken());
        	
        	graph[start].add(new Vertex(end, weight));
        }

우선 인접 리스트 또는 인접 행렬을 선언해주고 각자의 방식에 맞게 초기화 작업을 진행해준다.
이어서 M번동안 그래프의 연결 정보를 갱신해준다.
이 문제에서는 무방향 그래프가 아니기 때문에 graph[start]에만 .add 해준 것.

	int start = Integer.parseInt(st.nextToken());
    	int end = Integer.parseInt(st.nextToken());
    	
    	int[] dist = new int[N + 1];
    	Arrays.fill(dist, Integer.MAX_VALUE - 100_000);
    	
    	PriorityQueue<Vertex> pq = new PriorityQueue<>();
    	boolean[] visited = new boolean[N + 1];
    	
    	pq.add(new Vertex(start, 0));
    	dist[start] = 0;
    	
    	while (!pq.isEmpty()) {
    		Vertex cur = pq.poll();
    		
    		if (visited[cur.idx]) continue;
    		visited[cur.idx] = true;
    		
    		for (Vertex next : graph[cur.idx]) {
    			if (dist[next.idx] > dist[cur.idx] + next.weight) {
    				dist[next.idx] = dist[cur.idx] + next.weight;
    				pq.add(new Vertex(next.idx, dist[next.idx]));
    			}
    		}
    	}

start: 시작 정점
end: 도착 정점
dist[]: dp 테이블, 특정 idx까지의 최단 거리를 기록함
- 처음에는 모든 거리를 충분히 큰 수로 초기화
우선순위 큐에 시작 정점(가중치 0 -> 시작 지점이니까 거리가 0)을 추가
시작 정점의 거리를 0으로 초기화(dist[start] = 0)
이후 pq가 빌 때까지 다익스트라 핵심 로직 실행

    	while (!pq.isEmpty()) {
    		Vertex cur = pq.poll();
    		
    		if (visited[cur.idx]) continue;
    		visited[cur.idx] = true;
    		
    		for (Vertex next : graph[cur.idx]) {
    			if (dist[next.idx] > dist[cur.idx] + next.weight) {
    				dist[next.idx] = dist[cur.idx] + next.weight;
    				pq.add(new Vertex(next.idx, dist[next.idx]));
    			}
    		}
    	}

1. Vertex cur = pq.poll();

우선순위 큐에서 현재까지 비용이 가장 작은 정점을 꺼냄.
pq는 weight(현재까지의 비용) 기준으로 정렬되어 있어서 항상 "가장 짧은 거리 후보"가 먼저 나옴.

2. if (visited[cur.idx]) continue;

이미 방문했던 정점이면 다시 처리할 필요 없음
이유: 다익스트라에서는 한 번 최단거리가 확정된 노드는 더 이상 짧은 경로가 나올 수 없기 때문.

3. visited[cur.idx] = true;

현재 꺼낸 정점을 방문 처리 -> "이 정점의 최단거리가 확정되었다"는 뜻.

4. for (Vertex next : graph[cur.idx]) { ... }

현재 정점(cur)과 연결된 모든 인접 정점(next)을 확인.

5. if (dist[next.idx] > dist[cur.idx] + next.weight) { ... }

조건 의미:
- 현재 next.idx까지 기록된 최단거리(dist[next.idx])
- vs. cur까지 오는 최단거리 + cur → next로 가는 간선 비용(next.weight)
- 더 짧은 경로를 찾으면 갱신.

6. dist[next.idx] = dist[cur.idx] + next.weight;

최단거리 배열 갱신.
"현재까지 확인한 것보다 더 싸게(next.idx까지) 갈 수 있다"는 뜻.

7. pq.add(new Vertex(next.idx, dist[next.idx]));

갱신된 경로를 우선순위 큐에 넣음.
나중에 이 next.idx도 꺼내서 그 주변 노드들을 확인하게 됨.

코드 전문

BOJ 1753 - 최단경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_1753 {
	public static class Vertex implements Comparable<Vertex> {
		int idx;
		int weight;
		
		public Vertex(int idx, int weight) {
			this.idx = idx;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		int start = Integer.parseInt(br.readLine());
		
		ArrayList<Vertex>[] graph = new ArrayList[V + 1];
		for (int i = 0; i <= V; i++) graph[i] = new ArrayList<>();
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			graph[u].add(new Vertex(v, w));
		}
		
		int[] dist = new int[V + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[V + 1];
		
		pq.add(new Vertex(start, 0));
		dist[start] = 0;
		
		while (!pq.isEmpty()) {
			Vertex cur = pq.poll();
			if (visited[cur.idx]) continue;
			visited[cur.idx] = true;
			
			for (Vertex next : graph[cur.idx]) {
				if (dist[next.idx] > dist[cur.idx] + next.weight) {
					dist[next.idx] = dist[cur.idx] + next.weight;
					pq.add(new Vertex(next.idx, dist[next.idx]));
				}
			}
		}
		
		for (int i = 1; i <= V; i++) {
			if (dist[i] == Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(dist[i]);
		}
	}
}

코드 해설

로직은 똑같음.

이전 문제는 시작 정점과 끝 정점을 입력 받아서 최종적으로는 끝 정점의 값만을 출력했다면 지금 문제는 dp 테이블의 모든 값들을 출력하는 문제임.

저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[JAVA] 최소 신장 트리 - Prim 알고리즘 <Minimum Spanning Tree - Prim> (0)	2025.09.22
[JAVA] 최소 신장 트리 - Kruskal 알고리즘 <Minimum Spanning Tree - Kruskal> (0)	2025.09.11
[JAVA] 유니온 파인드 알고리즘 <Disjoint Set> (0)	2025.09.05
[JAVA] 위상 정렬 알고리즘 - 정렬 알고리즘 <Topological Sort> (0)	2025.09.04
[C/C++]BFS 알고리즘 - 그래프 탐색 알고리즘 <너비 우선 탐색> <Breadth-First Search> (1)	2023.09.10

'Algorithm' 카테고리의 다른 글

티스토리툴바