[Algorithm] 다익스트라 (Dijkstra) 알고리즘

양영준·2026년 2월 27일

algorithm

Algorithm

목록 보기

5/7

📌 다익스트라 (Dijkstra) 알고리즘

다익스트라 (Dijkstra) 알고리즘은 그래프에서 최단 경로, 최소 비용을 구하는 알고리즘 중 하나로, 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다.

그래프 방향의 유무는 상관 없으나, 간선들의 가중치가 전부 양수인 경우에만 사용할 수 있다.
따라서, 현실 세계에서 적용하기 매우 적합한 알고리즘 중 하나이다.

최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 다익스트라 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)에 해당하는 알고리즘이다.
즉, 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다.

💡 동작 과정

다음과 같은 그래프를 통해 다익스트라 알고리즘의 동작 과정을 살펴보자.

💿 1. 시작 노드 설정

다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이므로, 최단 경로를 구할 하나의 정점을 먼저 설정해야 한다.
정점을 선택하였다면, 각 노드별 최단 거리를 저장하는 1차원 배열을 만든다.

예시로 0번 노드를 시작 정점으로 설정하였다면,

다음과 같은 1차원 배열을 만들고, 시작 노드의 최단 거리를 0으로 지정한다.
이 때 INF 는 무한대로, 현재 노드에서 해당 노드에 도달하지 못한다는 의미로 사용된다.

💿 2. 시작 노드와 인접한 노드의 최소 비용 구하기

시작 노드를 0번 노드로 설정했기 때문에 0번 노드와 연결되어 있는 1, 2, 3번 노드로 가는 최소 비용을 계산한다.

1, 2, 3번 노드 모두 저장되어 있던 최단 거리인 INF 보다 작은 값이 나왔으므로, 3개의 노드 모두 우선 순위 큐에 삽입한다.
이 때, 우선 순위 큐는 해당 지점에 도달하는 최단 거리를 기준으로 오름차순 정렬한다.

우선 순위 큐에는 다음과 같이 저장되어 있게 된다.

💿 3. 비용이 가장 적은 노드를 선택하여 최소 비용 갱신

우선 순위 큐의 맨 앞 원소가 현재 최소 비용이 가장 적은 노드이므로 맨 앞 원소를 pop하여 해당 노드를 기준으로 최소 비용을 갱신한다.

우선 순위 큐의 맨 앞 원소는 1이지만, 해당 원소와 인접한 노드가 시작 노드인 0 밖에 없기 때문에 생략하고 2번 노드를 살펴 보자.

2번 노드와 인접한 노드는 시작 지점인 0번을 제외하고 3, 5번 노드가 있다.
2번 노드에서 3번 노드로 가는 비용은 2 + 3 = 5 로, 기존 최단 비용인 3보다 큰 값이므로 비용을 갱신하지 않는다.
5번 노드로 가는 비용은 2 + 1 = 3 으로. 기존 최단 비용보다 작은 값이기 때문에 갱신을 진행하고 우선 순위 큐에 5번 노드를 삽입한다.

해당 과정을 우선 순위 큐가 빌 때까지 계속해서 반복한다.
우선 순위 큐가 비워졌을 때, 1차원 배열에는 0번 노드에서 각 노드로 가는 최단 거리가 기록되어질 것이다.

💡 구현 코드

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct Compare
{
	bool operator ()(pair<int, int>& a, pair<int, int>& b)
	{
		return a.second > b.second;
	}
};

int main()
{
	freopen("input.txt", "r", stdin);

	int n;
	cin >> n;

	vector<vector<int>> graph(n, vector<int>(n));

	//연결되어 있지 않다면 0을, 연결되어 있다면 가중치를 입력
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n;j++)
		{
			cin >> graph[i][j];
		}
	}

	vector<int> distance(n, INT_MAX);
	priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

	int start;
	cin >> start;

	pq.push({ start, 0 });
	distance[start] = 0;

 	while (!pq.empty())
	{
		int idx = pq.top().first;
		int weight = pq.top().second;
		pq.pop();

		for (int i = 0;i < n;i++)
		{
			//가중치가 0이라면 연결되어 있지 않은 것이므로 넘김
			if (graph[idx][i] == 0)
			{
				continue;
			}

			int nextWeight = weight + graph[idx][i];
			if (distance[i] > nextWeight)
			{
				distance[i] = nextWeight;
				pq.push({ i, nextWeight });
			}
		}
	}

	for (int i = 0;i < distance.size();i++)
	{
		cout << "distance[" << i << "} : " << distance[i] << endl;
	}
}