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

다익스트라 알고리즘은 그래프에서의 최단 거리를 구하는 알고리즘이다.

기본적으로 너비 우선 탐색과 비슷한 방법으로 작동한다.

사실, 너비 우선 탐색은 다익스트라에서 모든 간선의 길이가 1인 특수한 경우라고 봐도 된다.

 

다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단경로를 계산한다.

여기선 너비우선탐색과는 다르게, 지금까지 큐에 넣은, 우선순위 큐(Priority Queue를 이용하여) 방문할 정점들 중 가장 거리가 짧은 정점을 골라 그곳을 방문한다.

 

여기서 중요한 점은 bfs에서는 vis check 를 큐에 넣기 직전, 즉 실제로는 방문하지 않았지만, 발견 되었고, 곧 방문할 정점에 표시해 준다. 즉, 큐에 한번이라도 들어가기 위해선 vis check 를 해줘야 다른 정점이 이 정점을 다시 확인하지 않을 수 있다. (하지만 bfs 에서도 vis check 를 큐에 넣기 직전, 큐에서 뺄때 둘 다 모두 가능하다.)

 

하지만 다익스트라는 이렇게 하면 안된다. 

아래 그림과 같은 상황의 그래프일 때, 1번 노드에서 2, 3번 노드로 갈 때 3번의 거리는 10이 된다. 만약 이 상황에서 vis check 를 해버린다면, 더 짧은 거리인 1->2->3 을 놓치게 된다. 따라서 이때는 무조건 큐에서 뺄 때 vis check 를 해줘야 함을 알 수 있다.

 

 

구현은, dist 배열과 vis check 배열 2가지가 있다.

dist 는 처음에 무한의 값으로 초기화 해 준후, 큐에서 뺄때 dist 값들을 갱신시키는 것이다.

여기서 주의할 점은 dist 는 처음에 무한대에서 최단거리로 바뀔때 빼고는 다시는 바뀌지 않는다는 점이고, 이를 이용하면 vis checking 만으로 해결할 수 있다.

 

따라서 큐에서 뺄 때에만 어떤 방법으로든 vis checking 해주고, 큐에 넣어줄 때에는 아무 체킹 없이 그냥 넣어주면 된다.

 

가능한 첫번째 최적화는 큐에 넣기 전, 이미 방문한 정점이면, 이미 어떠한 최단 경로가 이 정점을 방문하기도 전에 큐에 넣어졌었고, 또 빼져, 결국 이미 최단거리를 구한 점이며, 더이상 그 정점으로 갈 필요가 없다는 점을 의미하기 때문에 그냥 무시해도 된다.

두번째 최적화는, dist 배열을 큐에 넣어줄 때마다 갱신하고, 그 갱신된 dist 값을 바탕으로 큐에 넣을 필요가 있는지까지 확인해 주는 방법이다.

 

시간 복잡도는 전체 간선을 모두 방문하고 $O(E)$, 큐의 최대 크기는 간선의 개수 $O(ElogV)$ 이기 때문에, $O(ElogV)$가 된다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int INF = 987654321;

int n, m, s, dist[MAXN+10], par[MAXN+10];
bool vis[MAXN+10];
vector<pii> adj[MAXN+10];

struct Queue
{
    int u, w, par;
    bool operator < (const Queue& p) const { return w>p.w; }
};
priority_queue<Queue> PQ;

//DIST DIJKSTRA
void djk1()
{
    int i, j;
    for(i=1; i<=n; i++) dist[i]=INF;

    PQ.push({s, 0, s});
    while(!PQ.empty())
    {
        Queue T=PQ.top();
        PQ.pop();

        if(dist[T.u]<=T.w) continue;
        dist[T.u]=T.w; par[T.u]=T.par;

        for(pii nxt : adj[T.u])
        {
            if(dist[nxt.first]>nxt.second+T.w) PQ.push({nxt.first, nxt.second+T.w, T.u});
        }
    }

    for(i=1; i<=n; i++)
    {
        if(dist[i]==INF) printf("INF\n");
        else printf("%d\n", dist[i]);
    }
}

//VIS DIJKSTRA
void djk2()
{
    int i, j;

    PQ.push({s, 0, s});
    while(!PQ.empty())
    {
        Queue T=PQ.top();
        PQ.pop();

        if(vis[T.u]) continue;
        vis[T.u]=true; dist[T.u]=T.w; par[T.u]=T.par;

        for(pii nxt : adj[T.u])
        {
            if(!vis[nxt.first]) PQ.push({nxt.first, nxt.second+T.w, T.u});
        }
    }

    for(i=1; i<=n; i++)
    {
        if(!vis[i]) printf("INF\n");
        else printf("%d\n", dist[i]);
    }
}

int main()
{
    int i, j;

    scanf("%d%d%d", &n, &m, &s);
    for(i=0; i<m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});
    }

    djk1();
    djk2();
}