다익스트라 알고리즘

다익스트라 알고리즘?

: 하나의 시작점에서 다른 모든 노드까지의 최단거리/최소비용을 구하는 알고리즘

 = 길이 여러개 있을 떄 가장 짧은 길 찾기

 = 무게가 다른 물건 여러개가 있을 때 무게가 최소가 되도록 담기 등

 

*  그래프

그래프(Graph) : ‘점(노드)’과 ‘선(간선)’으로 이루어진 구조로, 각 간선에는 “비용”이나 “거리”가 붙어 있음

다익스트라는 그중 가중치가 양수인 그래프에서만 사용가능함.
(음수 간선이 있으면 다른 알고리즘인 벨만-포드 써야 함)

 

 

• 방향 그래프: 일방통행 (한쪽 방향만 이동 가능)
  → graph[a].push_back({b, c}); 만 추가
• 무방향 그래프: 양방향 통행
  → graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  둘 다 추가해야 함

예시) 

(1)──2──(2)
 |        |
 4        3
 |        |
(4)──1──(5)

연결 거리

1 ↔ 2	2
1 ↔ 4	4
2 ↔ 3	3
2 ↔ 5	5
4 ↔ 5	1

 

이 그래프들을 저장하는 방법

 

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

graph[1].push_back({2, 2});
graph[2].push_back({1, 2});

graph[1].push_back({4, 4});
graph[4].push_back({1, 4});

graph[2].push_back({3, 3});
graph[3].push_back({2, 3});

graph[2].push_back({5, 5});
graph[5].push_back({2, 5});

graph[4].push_back({5, 1});
graph[5].push_back({4, 1});

graph[a].push_back({b, c});
→ a번에서 b번으로 가는 거리(비용)가 c라는 뜻.

 

 

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

 

1. 출발 노드의 거리를 0으로, 나머지는 모두 무한대(∞)로 설정
2. 현재까지 ‘가장 가까운 노드’를 하나씩 꺼내
3. 그 노드를 거쳐 가는 경로가 더 짧다면 거리 갱신
4. 모든 노드가 확정될 때까지 반복

 

* 코드 구현  (C++)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 1e9

int main() {
    vector<pair<int,int>> graph[6];
    graph[1].push_back({2, 2}); graph[2].push_back({1, 2});
    graph[1].push_back({4, 4}); graph[4].push_back({1, 4});
    graph[2].push_back({3, 3}); graph[3].push_back({2, 3});
    graph[2].push_back({5, 5}); graph[5].push_back({2, 5});
    graph[4].push_back({5, 1}); graph[5].push_back({4, 1});

    int start = 1;
    vector<int> dist(6, INF);
    dist[start] = 0;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int d = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if (d > dist[now]) continue;

        for (auto [next, cost] : graph[now]) {
            int newDist = d + cost;
            if (newDist < dist[next]) {
                dist[next] = newDist;
                pq.push({newDist, next});
            }
        }
    }

    for (int i = 1; i <= 5; i++) {
        if (dist[i] == INF)
            cout << i << "번 노드: 도달 불가\n";
        else
            cout << i << "번 노드까지의 최소 거리: " << dist[i] << '\n';
    }
}

 

실행과정

시작	1	[0, ∞, ∞, ∞, ∞]	1번 거리 0
1번 탐색	2,4 갱신	[0, 2, ∞, 4, ∞]	1→2(2), 1→4(4)
2번 탐색	3,5 갱신	[0, 2, 5, 4, 7]	2→3(3), 2→5(5)
4번 탐색	5 갱신	[0, 2, 5, 4, 5]	4→5(1)로 더 짧음
끝	-	[0, 2, 5, 4, 5]	완료 ✅

 

 

실행결과

1번 노드까지의 최소 거리: 0
2번 노드까지의 최소 거리: 2
3번 노드까지의 최소 거리: 5
4번 노드까지의 최소 거리: 4
5번 노드까지의 최소 거리: 5

 

즉:

• 1 → 2 (2)
• 1 → 4 (4)
• 1 → 2 → 3 (2+3=5)
• 1 → 4 → 5 (4+1=5)

 

구현 방식에 따른 시간 복잡도

배열만 사용	O(V²)
우선순위 큐 사용 (힙)	O(E log V)