다익스트라(Dijkstra)

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

다익스트라 알고리즘은 그리디한 방식을 통해 한 점에서 다른 모든점까지의 최단 경로를 구하는 알고리즘입니다. 다만 경로의 길이가 음수인 경우는 최단 경로를 구할 수 없습니다. 경로의 길이가 음수인 경우 최단거리를 구하는 알고리즘은 벨만 포드(Bellman-Ford) 알고리즘이 있습니다.

처음 고안된 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌습니다.

이후 우선순위 큐를 이용한 개선된 알고리즘을 통해 O(ElogV)의 시간복잡도를 가지게 되었습니다.

다익스트라 알고리즘 계산 과정

다음은 예제 그래프를 통해 다익스트라 알고리즘이 시작점에서 다른 모든점까지의 최단경로를 구하는 방식입니다.

빨간색 노드는 현재 위치의 노드를 의미하며, 파란색 노드는 우선순위 큐에 존재하는 노드, 녹색노드는 연산이 끝난 노드입니다.

 

최초에 시작노드인 1번 노드를 우선순위 큐에 넣습니다.

시작 노드의 거리값은 0으로 그 외의 다른 노드는 모두 무한대의 값으로 저장합니다.

우선순위 큐에는 노드번호와 간선의 길이를 넣게되며, 우선순위 큐는 거리를 오름차순으로 정렬합니다.

현재 노드인 1번노드에 저장된 거리값과 현재노드에서 출발하는 간선의 거리를 바탕으로 연산합니다.

현재노드에 저장된 거리와 현재노드에서 출발한 간선의 길이의 합이 간선이 도착하는 노드의 거리보다 작으면 갱신합니다.

따라서 2번 노드는 10으로, 3번 노드는 30으로, 4번 노드는 15로 갱신합니다. 

이후 갱신된 간선 정보는 우선순위큐에 저장합니다.

1번 노드는 큐에서 제거를 하며 우선순위 큐 내에서 오름차순으로 정렬됩니다.

이후 가장 위에 존재하는 2번 노드가 현재 노드가 됩니다.

현재노드인 2번 노드의 거리에서 5번으로 출발하는 간선의 거리의 합이 5번노드에 저장된 거리보다 작으므로 갱신합니다.

이후 5번 노드를 우선순위 큐에 삽입을 합니다.

2번 노드를 큐에서 제거한 후, 정렬된 큐에서 가장 위에 존재하는 4번 노드가 현재노드가 됩니다.

4번 노드에서 출발하는 2개의 간선정보를 바탕으로 노드의 거리값과 비교합니다.

비교 결과 3번 노드의 거리가 20으로 6번 노드의 거리가 35로 갱신됩니다.

이후 간선의 정보를 우선순위 큐에 삽입합니다.

4번 노드는 큐에서 제거되고, 정렬된 값중 가장 작은 3번 노드가 가장 위에 존재하여 현재노드가 됩니다.

현재노드인 3번에서 출발하는 간선 정보를 바탕으로 거리를 갱신합니다.

6번 노드의 거리는 25로 갱신됩니다.

이후 부터는 거리보다 더 작아지는 경우가 없기 때문에 더이상 갱신되지 않습니다.

다익스트라 알고리즘 예제

백준 1753번 - 최단경로

www.acmicpc.net/problem/1753

1753번: 최단경로

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
 
using namespace std;
typedef pair<int, int> node;
 
int V, E; //V: 정점의 개수, E: 간선의 개수
int sp;
bool visited[20001];
int dist[20001];
vector<node> graph[20001];
priority_queue<node, vector<node>, greater<node> >PQ;
 
void Dijkstra(int p)
{
    PQ.push(node(dist[p], p));
    while (!PQ.empty())
    {
        int curr = PQ.top().second;
        PQ.pop();
        for (node &np : graph[curr])
        {
            int pos = np.first;
            int    dis = np.second;
            if (dist[pos] > dist[curr] + dis)
            {
                dist[pos] = dist[curr] + dis;
                PQ.push(node(dist[pos], pos));
            }
 
        }
    }
 
}
 
int main()
{
    scanf("%d %d %d", &V, &E, &sp);
    for (int i = 0; i < E; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back(make_pair(v, w));
    }
 
    for (int i = 1; i <= V; i++)
        dist[i] = 2e9;
    
    dist[sp] = 0;
    Dijkstra(sp);
 
    for (int i = 1; i <= V; i++)
    {
        if (dist[i] == 2e9)
            printf("INF\n");
        else
            printf("%d\n", dist[i]);
    }
 
    return 0;
}