다익스트라

다익스트라 필요한 이유

다익스트라 알고리즘은, 최단 경로 문제를 해결할 때 많이 사용되는 알고리즘 입니다.

최단 경로를 해결하기 위해서는, DFS, BFS 등을 활용하여 풀 수도 있습니다.

하지만, 특정 조건이 붙는다면 너무 오래 걸리거나 해결 자체가 되지 않습니다.

DFS 가 안되는 케이스

DFS 는 기본적으로 "갈 수 있는 데 까지는 끝까지 갔다가 돌아오기" 라는 재귀적인 탐색을 기반으로 동작합니다.

처음 발견한 경로가 최단 경로라는 보장을 할 수 없습니다.

만약 다음과 같은 맵에서 특정 규칙을 가지고 탐색을 한다면 처음으로 마주치는 경로는 다음과 같을 것 입니다.

탐색 규칙
좌우상하 순서대로 탐색한다
벽(까만색)이 있다면 이동할 수 없다.

위 탐색 규칙을 가지고, 탐색하게 된다면 처음으로 목표까지 도달한 경로는 다음과 같을 것입니다.

방문 후, 돌아온 경로는, 연한 파랑색

목적지 까지 도달이 가능한지는 확인할 수 있었지만, 명확하게 최적화된 길은 아닙니다.

최적화 목표는 다음과 같습니다.

따라서, 현재 시작 지점에서 도달 가능한 모든 경로를 확인하여 비용을 확인하며 진행해야 합니다.

만약 가중치가 다르다고 해도 전혀 문제 될 것 없이 모든 경로를 확인하면 됩니다.

하지만, 모든 경로를 확인하기에 시간복잡도가 지수적으로 O(v!) 까지 증가하게 되어 매우 비효율적인 알고리즘이 됩니다.

❗ 불가능 하다는 것이 아닙니다.
비효율적이라는 것 입니다.

BFS 가 안되는 케이스

BFS 가 안되는 케이스는 가중치가 있는 경우 처리가 되지 않습니다.

모든 경로가 1의 가중치만 적용된다면 최단경로를 보장하지만, 있다면 처리가 되지 않습니다.

논리적으로, BFS 는, 가장 적은 간선을 거친 경로를 최단 경로라고 판단하기 때문에, 가중치가 있는 경우에는 오답을 냅니다.

예시
1->2->3 노드로 이동 시, 비용이 100, 홉수는 3 (A경로)
1->4->5->3 으로 이동 시, 비용은 50, 홉수는 4 (B경로)
BFS는 간선을 기반으로 확인하기 때문에, 비용이 최저인 B경로를 선택하지 않고, A경로를 최적화된 길이라고 판단하게 됩니다.
B경로는 확인조차 하지 않습니다.

다익스트라 알아보기

다익스트라는 위의 소개된 다양한 문제점을 해결하면서 최단 경로 문제를 해결하는 알고리즘 입니다.

다익스트라 알고리즘을 한 줄로 요약하면 "현재까지 알고 있는 가장 짧은 길을 무조건 먼저 선택한다"는 것입니다.

사실 일종의 그리디(Greedy) 알고리즘이라고 할 수 있습니다.

원래 기본적으로 다익스트라는 배열을 사용하여 처리하는게 먼저 출시되었습니다.
하지만, 우선순위 큐로 처리하는 것이 훨씬 더 효율적이기 때문에 해당 방법을 소개합니다.

풀어볼 문제

다음 그래프에서, 1번 정점에서 시작해서 6번 정점까지 가는 최소 비용을 구하시오.

동작 프로세스

시작 지점부터 시작해, 각 정점에 이를 수 있는 최단 거리 테이블을 하나 만들어 둡니다.
내부의 모든 값은 INF 로, 시작 정점은 0으로 초기화 합니다.

다음으로, 최소 비용을 구하기 위한, 우선순위 큐를 생성하고, 시작 정점의 정보를 넣어줍니다.

이후 다음 3가지 단계를 PQ 가 빌 때까지 반복하며 최단 경로를 확정해 나갑니다.

우선순위 큐에서 비용(거리)가 가장 작은 원소를 선택, 만약 거리가 최단 거리 테이블에 있는 값보다 크다면 넘어가기
현재 정점과 이웃한 정점 들에 대해 가중치를 활용하여 최단 거리를 계산하여 현재의 최단 거리를 비교 후, 업데이트
최단 거리 테이블에 업데이트 하였다면, PQ 에 추가

문제 해결해보기

문제를 풀어본다면, 다음과 같이 작성될 것 입니다.

❗ 우선순위 큐에서 POP 된 Item 들은, 모두 삭제 처리 되지만, 알아보기 쉽게 누적해둡니다.

❗ 실제로 구현해보면 POP 된 Item 들은 모두 삭제됩니다.

1번 과정 (초기화)
최단 거리 테이블과 우선순위 큐를 만들고, 초기화 합니다.
시작 정점인 1번 정점만 최단 거리 테이블의 값을 0 으로 초기화 하고, 1번 정점의 정보를 우선순위 큐에 넣어줍니다.

2번 과정 (탐색)
우선순위 큐에서 비용이 가장 작은 Item 을 꺼내옵니다.
현재 1번 정점에 비용 0
현재, 꺼내온 정점의 비용과 최단 거리 테이블을 비교하여, 더 크면 패스
현재, 1번 정점의 비용 0, 최단 거리 테이블에서 1번 정점의 비용도 0이므로 해당 없음.
꺼내온 정점에서, 이동 가능한 정점을 모두 탐색 합니다.
현재 비용과 다음 이동할 경로까지 의 비용(가중치)를 합산해서, 비용을 계산합니다.
현재 1번 정점에서 2, 3, 4번 정점으로 이동 가능하며 각각 추가되는 가중치는 7, 10, 5 입니다.
이때, 이동할 정점의 최단 거리 테이블에 해당 이동 정점의 이동 비용이 더 작다면 패스합니다.
2, 3, 4번 정점으로 이동할 수 있고, 정점 들은 모두 ∞ 이기 때문에, 해당 되지 않습니다.
최단 거리 테이블에 계산한 비용들을 업데이트 하고, 우선순위 큐에 추가해줍니다.

3번 과정 (탐색)
우선순위 큐에서 비용이 가장 작은 Item 을 꺼내옵니다.
현재, 4번 정점에 비용 5
꺼내온 정점의 비용과 최단 거리 테이블을 비교하여, 더 크면 패스
현재, 4번 정점의 비용이 5, 최단 거리 테이블의 4번 정점의 비용 또한 5이므로 해당 없음.
이동 가능한 정점들에 대해 비용을 계산합니다.
3번 정점으로 이동 가능하고, 현재 비용 5 에 3의 추가 비용. 즉, 8의 비용 계산
이동할 정점의 최단 거리 테이블의 값과 비교하여 업데이트 및 우선순위 큐 추가
현재 계산한 비용은 8, 3번 정점의 기존 최단 거리는 10 이므로, 업데이트 및 우선순위 큐 추가

4번 과정 (탐색)
우선 순위에 따라, 가장 작은 Item 을 꺼내오고, 위의 과정 동일하게 진행
선택된 Item 은, 2번 정점에 7의 비용
2->5 번 정점까지 11의 비용이 소모되니, 총 비용은 (7 + 11) = 18
이때, 5번 정점은 기존 ∞ 이므로, 업데이트 및 우선순위 큐 추가

5번 과정 (탐색)
우선순위에 따라, 3번 정점과 8 비용을 가져와서 처리한다.
5번 정점의 최단 거리 테이블의 값과 비교했을 때 현재 값이 (8 + 3) = 11 로 더 작기 때문에, 업데이트 한다.

6번 과정 (탐색 및 일찍 취소)
우선순위에 따라, 3번 정점과 비용 10을 꺼내온다.
이때 3번 정점의 최단 거리는 이미 8 이므로, 해당 작업은 취소되며 아무 처리도 하지 않는다.

이후는, 반복이므로 사진만 첨부합니다.

7번 과정

8번 과정
6번에서 연결되는 정점은 없기 때문에 그대로 종료

9번 과정 (일찍 종료)
5번 정점 18의 비용은, 현재 최단 거리 테이블 보다 더 크기 때문에 패스

여기까지 진행되었다면, 최단 거리 테이블에 있는 내용으로 시작 지점에서 각 정점으로 이동할 때 최단 거리를 알 수 있습니다.

즉, 1번 정점에서 6번 정점 까지의 최단 거리는 15 입니다.

자바 코드로 알아보기

변수 안내

TOTAL_NODE_COUNT : 전체 노드 개수. 현 문제에서 6개
dist : 최단 거리 테이블
pq : 우선순위 큐
graph : 정점 간의 간선 정보를 저장 하는 2중 ArrayList
Edge : 정점과 비용을 저장하기 위한 Class

package baekgwa;

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

/**
 * PackageName : baekgwa
 * FileName    : ${NAME}
 * Author      : Baekgwa
 * Date        : 2025-09-11
 * Description : 
 * =====================================================================================================================
 * DATE          AUTHOR               NOTE
 * ---------------------------------------------------------------------------------------------------------------------
 * 2025-09-11     Baekgwa               Initial creation
 */

public class Main {

	public static final int TOTAL_NODE_COUNT = 6;

	public static void main(String[] args) {

		// 연결 그래프 초기화
		ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
		for (int idx = 0; idx <= TOTAL_NODE_COUNT; idx++) {
			graph.add(new ArrayList<>());
		}
		graph.get(1).add(new Edge(2, 7));
		graph.get(1).add(new Edge(3, 10));
		graph.get(1).add(new Edge(4, 5));
		graph.get(2).add(new Edge(5, 11));
		graph.get(3).add(new Edge(5, 3));
		graph.get(4).add(new Edge(3, 3));
		graph.get(5).add(new Edge(6, 4));

		// 다익스트라 처리
		// 시작정점에서의 최소 거리를 저장할 dist 테이블
		int[] dist = new int[TOTAL_NODE_COUNT + 1];
		// 초기값은, 모두 확인안된것을 의미하도록 MAX_VALUE 로 초기화
		Arrays.fill(dist, Integer.MAX_VALUE);
		// 시작 정점은 시작과 동시에 도착 판정
		dist[1] = 0;
		// 이동 비용 기준으로 오름차순. (작은 것 부터)
		PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.getCost() - b.getCost());
		//시작을 startNode 부터 진행
		pq.offer(new Edge(1, 0));

		while (!pq.isEmpty()) {
			Edge now = pq.poll();
			// 현재 노드
			int nowNode = now.getNode();
			// 시작지점 부터, 현재 노드까지 사용한 비용
			int nowCost = now.getCost();

			// 다른 우선순위로 인해 해당 정점까지의 최소비용이 변경되어 더 작은 경우로 가지가 뻗어진 경우, 해당 Edge 는 관리하지 않음.
			if (dist[nowNode] < nowCost)
				continue;

			// 현재 위치에서 갈 수 있는 경로들 모두 탐색
			for (Edge edge : graph.get(nowNode)) {
				int to = edge.getNode();
				int nextCost = edge.getCost() + nowCost;

				// 현재 가는곳이 더 작은 비용을 내고 갈 수 있다면, 추가
				if (dist[to] > nextCost) {
					dist[to] = nextCost;
					pq.offer(new Edge(to, nextCost));
				}
			}
		}

		// 1번 정점부터 6번 정점까지의 최단 거리
        System.out.println("1번 정점부터 6번 정점까지의 최소 비용 : " + dist[6]);
	}

	private static class Edge {
		private int node;
		private int cost;

		public Edge(int node, int cost) {
			this.node = node;
			this.cost = cost;
		}

		public int getNode() {
			return node;
		}

		public int getCost() {
			return cost;
		}
	}
}

1번 정점부터 6번 정점까지의 최소 비용 : 15

다익스트라(dijkstra) 알고리즘