다익스트라 알고리즘 정리

---

title: “다익스트라 알고리즘”

date: 2025-02-18 00:00:00 +0900 author: yejin

categories: [Algorithm, Note] tags: [greedy, shortest path]

math: true

개념

• 최단 경로 알고리즘
  • 한 정점에서 다른 모든 정점까지의 최단 경로 탐색
• 조건
  • 가중치가 있는 그래프(양수)

알고리즘

1. 시작 정점 설정, 최단 거리 초기화(INF)
2. 시작 정점의 거리를 0으로 설정
3. 방문하지 않은 정점 중, 최단 거리인 정점 선택
4. 해당 정점의 인접 정점 탐색
5. 현재 정점을 경유하는 것이 더 짧다면 거리 갱신
6. 모든 정점에 대해 3~5 반복

1. 함수 다익스트라(그래프, 시작 노드)
2.  모든 노드까지의 최단 거리 초기화
3.  시작 노드의 최단 거리 0

5.  while 방문하지 않은 노드가 존재할 때까지
6.      방문하지 않은 노드 중 최단 거리 노드 선택
7.      if 해당 노드의 최단 거리가 INF라면 -> 종료

8.      현재 노드의 모든 인접 노드 순회
9.          새 거리 -> 현재 노드 거리 + 가중치
10.         if 새 거리가 기존 최단 거리보다 짧다면
11.             최단 거리 갱신

12.     현재 노드 방문 처리

C++ 구현

순차 탐색

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;

vector<vector<int>> graph = {
        {0, 10, 0, 30, 100},
        {10, 0, 50, 0, 0},
        {0, 50, 0, 20, 10},
        {30, 0, 20, 0, 60},
        {100, 0, 10, 60, 0}
};

vector<int> dijkstra(int n, int start)
{
    vector<int> dist(n, INF);   // 최단 거리 배열 초기화(INF)
    vector<int> visited(n, 0);  // 방문 처리 배열 초기화(0)

    dist[start] = 0;    // 시작 노드의 거리 설정

    // 모든 노드 순회
    for (int i = 0; i < n; i++)
    {
        int min = -1;   // 최단 거리 노드

        // 방문하지 않은 노드 중 최단 거리인 노드 선택
        for (int j = 0; j < n; j++)
        {
            if (visited[j]) continue;
            if (min == -1 || dist[j] < dist[min])
            {
                min = j;
            }
        }

        // 선택한 노드가 시작 노드와 연결되지 않았을 경우 -> 반복문 종료
        if (dist[min] == INF) break;
        
        visited[min] = 1;	// min 노드 방문 처리

        // 선택한 노드와 인접한 노드의 거리 계산
        for (int j = 0; j < n; j++)
        {
            // 간선이 있고, 최단 거리 갱신 가능
            if (!graph[min][j]) continue;
            if (dist[j] > dist[min] + graph[min][j])
            {
                dist[j] = dist[min] + graph[min][j];
            }
        }
    }

    return dist;
}

int main()
{
    int n = 5;

    vector<int> ans = dijkstra(n, 0);

    for (int i = 1; i < n; i++) 
    {
        cout << "0->" << i << " 최단 거리: " << (ans[i] == INF ? -1 : ans[i]) << "\n";
    }
}

인접한 노드를 탐색하기 위해 n번 탐색, 한 노드에 대해 n번 탐색하므로 시간 복잡도는 \(O(V^{2})\)

우선 순위 큐

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;

vector<pair<int, int>> graph[5];

vector<int> dijkstra(int n, int start)
{
    vector<int> dist(n, INF);   // 최단 거리 배열 (INF)
    priority_queue<pair<int, int>> pq;  // 우선순위큐 사용(최대힙)

    dist[start] = 0;    // 시작 노드 초기화
    pq.push({ 0, start });  // 간선을 먼저 적재(거리 기준으로 정렬됨)

    while (!pq.empty())
    {
        int cur_dist = -pq.top().first; // 음수로 적재된 가중치의 부호 변경
        int cur_node = pq.top().second;
        pq.pop();

        // 최단 거리 비교
        if (cur_dist > dist[cur_node]) continue;

        // cur_node의 인접 노드 순회
        for (auto& neighbor : graph[cur_node])
        {
            int next_node = neighbor.first;
            int weight = neighbor.second;
            int calc = cur_dist + weight;

            // 최단 거리 갱신
            if (calc < dist[next_node])
            {
                dist[next_node] = calc;
                pq.push({ -calc, next_node });  // 최대힙이므로 음수로 변환(최소힙처럼 사용)
            }
        }
    }

    return dist;
}

int main()
{
    graph[0] = { {1, 10}, {3, 30}, {4, 100} };
    graph[1] = { {0, 10}, {2, 50} };
    graph[2] = { {1, 50}, {3, 20}, {4, 10} };
    graph[3] = { {0, 30}, {2, 20}, {4, 60} };
    graph[4] = { {0, 100}, {2, 10}, {3, 60} };

    vector<int> ans = dijkstra(5, 0);

    for (int i = 1; i < 5; i++) 
    {
        cout << "0->" << i << " 최단 거리: " << (ans[i] == INF ? -1 : ans[i]) << "\n";
    }

    return 0;
}

인접 노드 거리를 갱신하기 위해 모든 간선 순회(\(O(E)\)), 거리 갱신마다 우선 순위 큐에 연산(\(O(log N)\))

시간 복잡도는 $$$O(E log V)$이 된다.