Dayong Blog

🚧공사중🚧

cs /

다익스트라(Dijkstra) 알고리즘 - 최단 경로 찾기 (c++ 구현)

profile

Dayong Lee

·

2023년 7월 18일

자료구조개론 수업에서 다익스트라 알고리즘을 배웠지만 제대로 정리를 안해서 BOJ 1916번 - 최소비용 구하기 문제를 푸는데 어려움을 겪었다. 그래서 이번에 다시 정리해보려고 한다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 책과 학부 수업 내용을 참고했다.

최단 경로 알고리즘?

가중치 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘으로 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 플로이드 워셜 알고리즘이 있다. 이 중 다익스트라 최단 경로 알고리즘을 살펴보려고 한다.

다익스트라 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘은 에츠허르 다익스트라(데이크스트라)가 연구한 알고리즘으로, 특정한 노드에서 다른 노드로 가는 최단 경로를 구해주는 알고리즘이다. 기본적으로 매번 가장 비용이 적은 노드를 선택하기 때문에 그리디 알고리즘으로 분류되고 이전까지 연산 값을 기반으로 최단 거리를 구하기 때문에 다이나믹 프로그래밍으로도 분류된다.

다익스트라가 연구한 알고리즘 중 가장 유명하기 때문에 최단 경로를 빼고 간단하게 다익스트라 알고리즘이라고도 부른다.

다익스트라 알고리즘 동작 과정

동작과정은 다음과 같다.

  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 초기화한다.
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. (그리디)
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하고 최단 거리 테이블을 갱신한다.
  5. 3 ~ 4번을 반복한다.

다익스트라 알고리즘 예제

출발 노드 설정출발 노드 설정

예를들어 위 그래프상에서 1번 노드으로 부터 다른 노드로 가는 최단 경로를 구한다고 하자.

노드123456
최단 거리 테이블0INFINFINFINFINF

먼저 1 -> 1은 0이므로 자기 자신에 해당하는 부분은 0으로 최단 거리 테이블을 세팅하고 나머지는 무한(보통 1e9)으로 초기화한다.

노드123456
최단 거리 테이블0251INFINF

그리고 1번 노드에서 갈 수 있는 노드들을 확인한다. 1 -> 2는 2, 1 -> 3은 5, 1 -> 4는 1이고 기존 INF보다 작기 때문에 해당 값들로 최단 거리 테이블을 갱신한다. 그 후 갈 수 있는 노드 중에서 방문하지 않았으면서 가장 가까운 노드를 선택한다. 따라서 우리는 4번 노드를 선택한다.

노드123456
최단 거리 테이블02412INF

이번에도 4번 노드에서 갈 수 있는 노드들을 확인한다. 4 -> 3는 3, 4 -> 5은 1이므로 1 -> 4의 비용과 합쳐서 최단 거리 테이블을 갱신한다. 이러한 과정을 반복하면 최단 거리 테이블이 완성된다.

다익스트라 알고리즘 구현 (c++)

구현하는 방법은 2가지가 있는데 하나는 단순 배열을 이용하는 방법이고 다른 하나는 우선순위 큐를 이용하는 방법이다.

먼저 단순히 배열을 사용하는 방법은 단계마다 방문하지 않은 노드 중에서 가장 가까운 노드를 선택할 때 선형 탐색을 하기 때문에 O(V^2)의 시간 복잡도를 가지게 되는데 우선순위 큐를 사용하면 가장 가까운 노드를 O(logV)의 시간 복잡도로 찾을 수 있기 때문에 O(ElogV)의 시간 복잡도를 가지게 된다.

c++에는 우선순위 큐가 이미 구현되어 있기 때문에 굳이 배열을 사용할 필요가 없다고 생각한다. 따라서 우선순위 큐를 이용해 구현하는 방법만 알아보도록 하겠다.

1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <queue>
5
6using namespace std;
7#define INF 1e9
8int graph[7][7] = {};
9int dist[7];
10int N = 6;
11
12void dijkstra(int s) {
13 priority_queue<pair<int, int> > pq;
14 pq.push(make_pair(0, s));
15 dist[s] = 0;
16
17 while (!pq.empty()) {
18 int cur = pq.top().second;
19 int cur_dist = -pq.top().first;
20 pq.pop();
21
22 if (dist[cur] < cur_dist) continue;
23
24 for (int i = 1; i <= N; i++) {
25 int next_distance = cur_dist + graph[cur][i];
26 if (next_distance < dist[i]) {
27 dist[i] = next_distance;
28 pq.push(make_pair(-next_distance, i));
29 }
30 }
31 }
32}
33
34int main() {
35 fill(dist, dist + 1001, INF);
36 fill(&graph[0][0], &graph[6][6], INF);
37 graph[1][2] = 2;
38 graph[1][3] = 5;
39 graph[1][6] = 1;
40 graph[2][3] = 3;
41 graph[2][6] = 2;
42 graph[3][2] = 3;
43 graph[3][4] = 5;
44 graph[5][3] = 1;
45 graph[5][4] = 2;
46 graph[6][3] = 3;
47 graph[6][5] = 1;
48 dijkstra(1);
49 for (int i = 1; i <= N; i++) {
50 cout << dist[i] << " ";
51 }
52 return 0;
53}

위 코드는 위에서 다뤘던 예제를 c++로 구현한 코드로 설명하자면 아래와 같다.

  • main 함수 및 전역 변수 설명
    • graph : 그래프를 나타내는 인접 행렬
      • graph[1][2] = 2 : 1번 노드에서 2번 노드로 가는 비용이 2
      • INF는 간선이 없는 경우를 의미
    • dist : 최단 거리 테이블
      • fill 함수를 이용해 모든 값을 무한으로 초기화
  • dijkstra 함수 설명
    • 매개변수 s는 시작 노드를 의미
    • 우선순위 큐 구현체인 priority_queue를 이용해 구현
      • max heap으로 구현되어 있기 때문에 거리의 부호를 바꿔서 넣어주고 꺼낼 때 다시 부호를 바꿔준다.
    • make_pair를 이용해 pair를 만들어 넣어준다.
      • first, second를 이용해 pair 안에 있는 값에 접근할 수 있다.
      • 보통 heap들은 first를 기준으로 정렬하기 때문에 first에 거리를 넣어주고 second에 노드 번호를 넣어준다.
    • 🔥 우선순위 큐가 비어 있을 때까지 다음 과정을 반복한다. 🔥
      • 우선순위 큐에서 가장 가까운 노드를 꺼낸다.
      • 꺼낸 노드와 연결된 노드들을 확인한다.
      • 꺼낸 노드를 거쳐서 가는 비용이 기존에 알고 있던 비용보다 더 작다면 최단 거리 테이블을 갱신하고 우선순위 큐에 넣어준다.
        • 우선순위 큐에 넣어줄 때 거리의 부호를 바꿔서 넣어준다.

동작과정만 잘 이해하면 구현은 어렵지 않은 것 같다.

❌ 주의사항 - 음수 가중치

음수 가중치가 있는 경우에는 일반적으로 다익스트라 알고리즘을 사용하면 안된다. 전통적인 다익스트라 알고리즘은 한 번 방문한 노드는 다시 방문하지 않기 때문에 음수 가중치가 있는 경우에는 최단 거리를 찾을 수 없다.

예를들어 A -> B로 가는 비용이 2, A -> C로 가는 비용이 1, B -> C로 가는 비용이 -10인 경우에는 A -> C -> B로 가는 비용이 -9로 최단 거리가 된다. 하지만 다익스트라 알고리즘은 한 번 방문한 노드는 다시 방문하지 않기 때문에 B를 거쳐 C로 가는 경우를 고려하지 않아서 잘못된 결과를 출력한다.