다익스트라 알고리즘의 개념과 구현(C++)

16 Nov 2017

Reading time ~3 minutes

개요

다익스트라는 노드와 다른 노드까지의 거리(가중치)가 주어졌을 때, 특정 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.
음의 가중치가 없는 그래프여야 하고, 방향그래프, 무방향 그래프 모두 상관없다.

관련 글: python으로 구현한 다익스트라 알고리즘를 참고하시면 python으로 구현한 코드도 확인하실 수 있습니다.

다익스트라 알고리즘

출발 노드의 인덱스를 start라고 하자.
start번째 노드에서 i번째까지 가는 최단경로 배열을 d라고 하자. d[i]는 start->i의 최단경로를 의미한다.
방문한 노드의 배열을 S라고 하자. i번째 노드를 방문했으면 S[i]=true가 된다. 방문했다는 의미는, start번째 노드에서 i번째 노드까지 가는 최단거리가 이미 결정되었다는 뜻이다.

다익스트라 알고리즘의 진행 순서은 다음과 같다.

배열 d를 각각 무한대 값으로 초기화시켜준다. 하지만 start 노드(자기자신)까지의 최단거리는 0 이므로 d[start] = 0으로 초기화 시켜준다.
다음과 같은 루프를 반복시킨다.
1) 배열 d중에서 최소값을 가지고 있는 N번째 노드(단, S[N]은 false)를 ‘방문’한다. 즉, S[N]=true로 초기화 시켜준다.
2) 이 때 방문하지 않은 노드 중에 최소값을 가지고 있는 노드가 거리가 무한대라면(즉, S[N]이 false인 모든 d[N]이 무한대라면), 방문하지 않은 노드들은 전부 절대 ‘방문’ 할 수 없는 노드란 것을 의미하거나 (만약 방문할 수 있었다면 이전의 3) 단계에서 d[N]이 무한대보다는 작은 값으로 업데이트 되었을 것이기 때문이다.), 모든 노드를 방문했다는 의미이기 때문에, 반복문을 빠져나간다.
3) N번째 노드를 ‘방문’하면, 배열 d를 순회하며 ‘N번째 노드를 통해서 가는 거리가 더 짧은 지’ 확인하고, 더 짧다면, 배열 d를 더 짧은 거리(N번째 노드를 통해서 가는 거리)로 초기화 시켜준다.

시간 복잡도

최악의 경우는 모든 노드가 서로 간선에 연결되어 있을 때이다. 배열 d중에서 최소값을 찾는 작업을 V번 반복하고, 배열 d를 순회하는 과정을 V번 반복하기 때문에, 시간 복잡도는 O(V^2)이다.

공간 복잡도

인접 노드의 정보를 표현한 그래프는 V*V행렬에 표현되고, S,d 각각 V만큼의 배열을 가지기 때문에, O(V^2 + 2V)이므로 O(V^2)가 공간 복잡도이다.

개선 가능성

그래프를 인접 행렬이 아닌 인접 리스트를 사용하고, 최소 N번째 노드를 찾는데 우선순위 큐를 사용해서 찾는다면 시간 복잡도를 O(Elog|V|)로 줄일 수 있습니다.
또한 공간복잡도도 인접 리스트를 사용하기 때문에 낭비되는 공간을 줄일 수 있게 됩니다.

소스 코드

#include <iostream>
#include <vector>

#define INF 987654321

using namespace std;

int V, E, K; // 정점의 수, 간선의 수, 시작 정점 번호

vector<vector<int>> graph; // 간선 가중치. 그래프의 인접 리스트.

vector<int> dijkstra()
{
    vector<int> s,d; // 방문 여부, 최단 경로

    s.assign(V,false);
    d.assign(V,INF);
    d[K-1] = 0; //자기 자신까지 가는 거리는 0

    while(true)
    {
        int m = INF, N=-1;

        //최소 N번째 노드를 찾는다.
        for(int j=0;j<V; j++)
        {
            if(!s[j] && (m>d[j]))
            {
                m = d[j];
                N = j;
            }
        }

        // m이 INF라는 얘기는 방문하지 않은 노드들의 d값이 전부 INF라는 뜻입니다.
        if(m == INF)
            break;

        s[N] = true; // N번째 노드를 방문.

        //d를 탐색하며 N번째 노드를 통해서 가는 길이 더 짧은 길이면 d를 더 짧은 길로 업데이트 한다.
        for(int j=0;j<V;j++)
        {
            //j번째 노드가 이미 방문되었다면 d[j]는 이미 결정된 최소값이므로 변경하면 안된다.
            if(s[j]) continue;

            //N번째 노드와 인접 노드들을 돌며, N을 통해서 가는 거리를 via에 저장한다.
            unsigned int via = d[N] + graph[N][j];

            //N을 통해서 가는 거리가 더 짧으면, 그 인접 노드의 d[j](d까지 가는 거리의 최소거리)를 N을 통해서 가는 거리로 바꿔준다.
            if(d[j] > via)
                d[j] = via;
        }
    }
    return d;
}
int main()
{
    cin>>V>>E;
    cin>>K;

    graph.assign(V, vector<int>(V,INF));

    while(E--)
    {
        int u,v,w;

        cin>>u>>v>>w;

        // 가중치 초기화
        graph[u-1][v-1] = w;
        //graph[v-1][u-1] = w; //무방향성 그래프일 경우 다음 코드를 추가한다.
    }

    vector<int> d = dijkstra();

    for(int i=0;i<d.size();i++)
    {
        if(d[i] == INF)
            cout<<"INF"<<endl;
        else
            cout<<d[i]<<endl;
    }

    return 0;
}