Dijkstra 알고리즘이란 무엇인가?

다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘 : 하나의 정점에서 다른 모든 정점들의 최단 경로를 구한다.

다익스트라 알고리즘의 기본 로직 : 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신하는 것이다.

정점을 잇기 전까지는 시작점을 제외한 정점들은 모두 무한 대 값을 가진다.

1. 다익스트라 알고리즘 기본 로직

시작점 : 5번 정점

• 5번 노드를 제외한 나머지 정점들이 가지는 최단 경로는 아직 연결되지 않았으므로 무한대이다.

1) 경로가 가장 짧은 정점을 고른다.

• 시작 점, 5번 노드와 연결되어 있는 노드는 2, 4번 노드이다.
• 2번 노드
  • dist[2] = min(dist[2], dist[5] + adj[5][2])
  • min(INF, 4) = 4
• 4번 노드
  • dist[4] = min(dist[4], dist[5] + adj[5][4])
  • min(INF, 2) = 2

경로가 가장 짧은 정점을 고른다.

가장 짧은 거리를 가지고 있는 노드는 4번 노드이다.

• 4번 노드와 인접 노드 : 2, 3번 노드
• 2번 노드(정점)
  • dist[2] = min(dist[2],dist[4] + adj[4][2]) = 3
• 3번 정점
  • dist[3] = min(INF, 3) = 3

숫자적으로 앞에 있는 2번 경로를 꺼내고 인접 정점을 비교한다.

인접 정점은 1번 노드로 간선 가중치는 3이다.

• 2번 노드와 인접 노드 : 1번 노드
• 1번 노드(정점)
  • dist[1] = min(dist[1], dist[2] + adj[2][1]) = 6

다음으로, 최단 경로가 3을 꺼내고 인접 정점을 비교한다.

• 3번 노드와 인접 노드 : 4번 노드
• 4번 노드(정점)
  • dist[4] = min(dist[4], dist[3] + adj[3][4]) = 2
  • dist[4] = 2 이고, dist[3] + adj[3][4] = 5 이므로

dist[4]가 더 작으므로 그대로 유지된다.

마지막으로 남은 정점은 1이다.

1을 꺼내고 인접 정점을 비교한다. 인접 정점은 3과 4이다.

• dist[4] = min(dist[4], dist[1]+adj[1][4])

• dist[4] = 2, dist[1] + adj[1][4] = 9

dist[4]가 더 작으므로 그대로 유지한다.

• dist[3] = min(dist[3], dist[1] + adj[1][3])

• dist[3] = 3, dist[1] + adj[1][3] = 12

dist[3]이 더 작으므로 그대로 유지한다.

모든 정점 방문했을 때 결과

2. 우선순위 큐(힙구조)를 이용한 다익스트라 알고리즘

최소 힙을 사용하면 가장 작은 경로를 가진 정점이 나오도록 구현한다.

힙 구조를 이용하면 빠른 시간 내에 구현이 가능하다.

모든 정점들을 힙(우선순위 큐)에 넣는다.

위 표에서

• i는 정점 인덱스
• d는 최단 거리
• p는 이전 정점

d를 기준으로 최소 힙으로 구성한다.

힙에서 가장 위에 있는 값을 꺼낸다.

현재 표를 보면 인덱스가 5이고 최소 거리가 0인 값이다.

기존에 있던 dist[5]와 d를 비교한다.

dist[5]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.

현재 둘다 0이므로, 5 주변의 인접 정점을 계산하고 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.

• dist[2] = min(dist[2], dist[5] + adj[5][2], dist[4] = min(dist[4], dist[5] + adj[5][4]))

힙에서 가장 위에 있는 값을 꺼낸다.

인덱스가 4이고 최소 거리(d)가 2인 값이다.

기존에 있던 dist[4]와 d를 비교한다.

dist[4]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.

dist[4] = 2 이고, d는 2이므로 같다.

4 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.

• dist[2] = min(dist[2], d + adj[4][2])
• dist[3] = min(dist[3], d + adj[4][3])

힙에서 가장 위에 있는 값을 꺼낸다.

인덱스가 2이고, 최소 거리(d)가 3인 값이다.

dist[2]와 d를 비교한다.

dist[2]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.

dist[2]는 3이고, d는 3으로 같다.

2 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.

• dist[1] = min(dist[1], dist[2] + adj[2][1])

힙에서 가장 위에 있는 값을 꺼낸다.

인덱스가 3이고 최소 거리(d)가 3인 값이다.

기존에 있던 dist[3]와 d를 비교한다.

dist[3]이 더 작으면 연산하지 않고, 같거나 크면 연산한다.

dist[3]는 3이고, d는 3으로 같다.

2 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.

• dist[4] = min(dist[4], dist[4] + adj[4][2])

현재 dist[4]는 2이므로 계산 값보다 작으므로 큐에 넣지 않는다.

힙에서 가장 위에 있는 값을 꺼낸다.

인덱스가 2이고 최소 거리(d)가 4인 값이다.

dist[2] = 3보다 d = 4가 더 크므로 계산하지 않는다.

힙에서 가장 위에 있는 값을 꺼낸다.

인덱스가 1이고 최소 거리가 7인 값이다.

dist[1]와 d를 비교한다.

dist[1]는 7이고, d는 7로 같다.

1 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.

• dist[4] = min(dist[4], dist[1] + adj[1][4])
• dist[3] = min(dist[3], dist[1] + adj[1][3])

둘 다 기존의 dist[i]보다 크므로 큐에 넣지 않는다.

큐에 남아있는 정점들은 전부 d가 INF로 dist[i]보다 크므로 계산하지 않는다.

3. 소스

3-1) 리스트 기반를 이용한 다익스트라 알고리즘

#include<iostream>
#include<vector>
using namespace std;
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;

vector<pair<int, int> > graph[100001]; // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열

bool visited[100001]; // 방문한 적이 있는지 체크하는 목적의 배열 만들기

int d[100001]; // 최단 거리 테이블 만들기

int getSmallestNode() // 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환.
{
    int min_value=INF;
    int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)

    for(int i=1; i<=n; i++)
    {
        if(d[i] <min_value && !visited[i])
        {
            min_value = d[i];
            index = i;
        }
    }

    return index;
}

void dijkstra(int start)
{
    d[start]=0;
    visited[start]= true;

    for(int j=0; j<graph[start].size(); j++)
    {
        int adjindex = graph[start][j].first;
        d[adjindex] = graph[start][j].second; // 최단거리 테이블에 초기값 세팅
    }

    for(int i=0; i<n-1; i++)
    {
        int now = getSmallestNode();
        visited[now]=true;

        for(int j=0; j<graph[now].size(); j++)
        {
            int cost = d[now] + graph[now][j].second;
            if(cost<d[graph[now][j].first])
            {
                d[graph[now][j].first]=cost;
            }
        }
    }
}

int main()
{
    cin >> n >> m >> start;
    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;  // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({b, c});
    }

    // 최단 거리 테이블을 모두 무한으로 초기화
    fill_n(d, 100001, INF);

    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++)
    {
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF)
        {
            cout << "INFINITY" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else
        {
            cout << d[i] << '\n';
        }
    }
    return 0;
}

3-2) 우선순위 큐를 이용한 다익스트라 알고리즘

#include <stdio.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;

vector<pair<int, int> > graph[100001]; // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
int d[100001]; // 최단 거리 테이블 만들기

void dijkstra(int start)
{
    priority_queue<pair<int,int>>pq; // 거리, 노드 인덱스

    pq.push({0,start}); //시작 노드로 가기위한 최단 경로는 0으로 설정하여, 큐에 삽입.
    d[start]=0;

    while(!pq.empty())
    {
        int dist = -pq.top().first; //현재 노드까지의 비용
        int now = pq.top().second; // 현재 노드
        pq.pop();

        if(d[now]<dist) // 이미 최단경로를 체크한 노드인 경우 패스
            continue;

        for(int i=0; i<graph[now].size(); i++)
        {
            int cost = dist+graph[now][i].second; // 거쳐서 가는 노드의 비용을 계산
                                                  // 현재노드까지 비용 + 다음 노드 비용
            if(cost<d[graph[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[graph[now][i].first]=cost;
                pq.push(make_pair(-cost,graph[now][i].first));
            }
        }
    }
}

int main(void)
{
    cin >> n >> m >> start;

    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({b, c});
    }

    // 최단 거리 테이블을 모두 무한으로 초기화
    fill(d, d + 100001, INF);

    // 다익스트라 알고리즘을 수행
    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++)
    {
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF) {
            cout << "INFINITY" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else {
            cout << d[i] << '\n';
        }
    }
}

정리하면, 다익스트라 알고리즘을 구현할 때

1. 구현하기 쉽지만 느리게 동작하는 코드를 이용할 때는 리스트 기반을 사용한다.
2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드를 이용할 때는 우선순위 큐 기반을 사용한다.

참고자료

• https://hsp1116.tistory.com/42
• https://yabmoons.tistory.com/364
• https://hub1234.tistory.com/33