[알고리즘] 다익스트라(Dijkstra) 알고리즘이란? 다익스트라 c++ 구현

다익스트라(Dijkstra) 알고리즘이란?

다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.

다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능)

 

다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다.

 

1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)
2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.

 

이해가 잘 가지 않는다면 아래 예시를 보면 이해가 빠를 것이다.

 

위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자.

1차원 배열 dist[]에 각 정점까지의 최단거리를 갱신해 나갈 것이다. 초기에는 모두 INF(무한대)로 설정한다.

• 가장 먼저 시작정점을 방문한다.
• 시작 정점에서 방문 할 수 있는 정점들에 대한 거리를 갱신한다.

• 방문하지 않은 정점 중 가장 가중치가 작은 2번 정점을 방문한다.
• 0번 정점에서 2번 정점을 거쳐서 4번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다 ( INF > 11)
• 0번 정점에서 2번 정점을 거쳐서 3번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다 ( 7 > 6 )

• 방문하지 않은 정점 중 가장 가중치가 작은 3번 정점을 방문한다.
• 0번 정점-2번 정점-3번정점을 거쳐서 4번 정점을 가면 기존 거리보다 최단 거리이므로 갱신한다( 11> 10 )

• 방문하지 않은 정점 중 가장 가중치가 작은 4번 정점을 방문한다.
• 갱신할 거리가 없다.

• 방문하지 않은 정점 중 가장 가중치가 작은 1번 정점을 방문한다.
• 갱신할 거리가 없다.
• 모든 정점을 방문했으므로 종료한다.

위와 같은 과정을 거치면 dist 배열에 0번정점부터 각 정점까지의 최단거리가 기록되게 된다.

c++ 다익스트라 구현

다익스트라는 배열을 이용해 구현할 수도 있고, 우선순위 큐를 이용해 구현할 수도 있다.

정점의 개수를 V, 간선의 개수를 E라고 했을 때

배열을 이용하는 경우 시간복잡도는 O(V^2) 이고 우선순위 큐를 이용하는 경우 O(ElogV)이다.

우선순위 큐를 사용하는게 훨씬 빠르고 간단하니 우선순위 큐를 이용한 방법을 살펴보자.

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

#define MAX 100        // 최대 정점의 개수 
#define INF 99999999

using namespace std;
  
vector<int> dijkstra(int start, int V, vector<pair<int,int> > adj[]) {
    vector<int> dist(V, INF);    // 전부 INF로 초기화 
    priority_queue<pair<int, int> > pq;
    
    dist[start] = 0;
    pq.push(make_pair(0, start));    // 시작 정점 방문 

    while (!pq.empty()) {
        int cost = -pq.top().first;    // 방문한 정점의 dist 값 
        int cur = pq.top().second;    // 현재 방문한 정점 
        pq.pop();

        for (int i = 0; i < adj[cur].size(); i++) {    // 현재 방문한 정점의 주변 정점 모두 조사 
            int next = adj[cur][i].first;    // 조사할 다음 정점 
            int nCost = cost + adj[cur][i].second;    // 현재 방문한 정점을 거쳐서 다음 정점을 갈때의 비용 
            if (nCost < dist[next] ) {     // 기존 비용보다 현재 방문한 정점을 거친 비용이 더 싸다면 
                dist[next] = nCost;    // 갱신 
                pq.push(make_pair(-nCost, next));    // pq에 저장 
            }
        }
    }
    
    return dist;
}

int main()
{
    int V,E;
    vector<pair<int, int> > adj[MAX];
    cout << "정점의 개수 입력 : ";
    cin >> V;
    cout << "간선의 개수 입력 : ";
    cin >> E;

    for (int i = 0; i < E; i++) {
        int from, to, cost;
        cout << "그래프 입력 [정점 정점 가중치]: ";
        cin >> from >> to >> cost;
        adj[from].push_back(make_pair(to, cost));    // 양방향 그래프 
        adj[to].push_back(make_pair(from, cost));
    }

    printf("\n===다익스트라 결과===\n");
    vector<int> dist = dijkstra(0, V, adj);
    for (int i = 0; i < V; i++) {
        printf("0번 정점에서 %d번 정점까지 최단거리 : %d\n", i, dist[i]);
    }
    return 0;
}

 

실행결과