[알고리즘] Dijkstra

 최단 경로 알고리즘에는 다양한 종류의 알고리즘이 있는데 그 중에서 Dijkstra는 하나의 시작점에서 다른 모든 노드까지의 거리의 최소를 알려준다. Dijkstra 알고리즘을 사용하기 위한 조건으로는 하나의 시작점이 정해져있을 것, 그리고 음수 값을 가진 간선이 없을 것이다. Greedy 적인 방법으로 접근하기 때문에 음수 값의 간선이 존재하면 알고리즘이 성립하지 않는다. 

 자세한 설명들은 다른 블로그에 잘 나와있으니까.. 헷갈릴 만한 개념들만 되짚어보자.

---

 진행 방향은 다음과 같다.

 초기조건 : 일차원 Distance를 저장할 수 있는 배열(이하 Dist[]). 무한대에 비슷한 큰 값을 넣어준다. 

               시작 집합에 시작점을 넣어준다.

 알고리즘 :

1. 시작집합과 연결된 노드 중 가장 거리가 짧은 노드(이하 a)를 찾는다. 음수 간선이 없기 때문에 어떻게 돌아와도 이 노드까지의 거리는 갱신되지 않을 것이다.

2. 그리고 a와 연결된 모든 정점에 대해 Dist[i]값과 Dist[a]+(a와 i사이의 간선크기)를 비교해서 더 작은 값으로 갱신해주면 된다.

3. 그리고 a를 시작집합에 넣어주다.

4. 1부터의 과정을 더 이상 시작집합에 새로 추가될 노드가 없을 때까지 반복한다.

 

물론 코드를 짜는 방식은 때에 따라 달라지지만 대략적인 알고리즘 흐름은 다음과 같다.

 

---

시간복잡도

while을 돌면서 각 노드와 연결된 간선을 모두 확인하기 때문에 E의 시간이 걸림을 알 수 있고, heap dijkstra라면 값을 넣으면 자동으로 log(개수)의 시간으로 정렬해주는데, heap의 크기가 최대로 되면 E가 되기 때문에 시간복잡도는 대략 O(ElogE)임을 알 수 있다. E=N^2가 최대임을 생각하면 O(ElogN)으로도 볼 수 있다.

---

코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 99999999
using namespace std;
int n,e;
int s;
struct tuple2 {
    int node;
    int val;
};
struct pq_tuple {
    int idx;
    int dist;
    bool operator < (const pq_tuple &node) const {
        return dist>node.dist;
    }
};
vector <tuple2> A[20005];
long long dist[20005];
int visited[20005];
priority_queue <pq_tuple> pq;
void dijkstra() {
    dist[s]=0;
    pq_tuple srg;
    int i,j;
    int _min,min_idx;
    srg.idx=s;
    srg.dist=0;
    pq.push(srg);
    while(!pq.empty()) {

        min_idx=pq.top().idx;
        _min=pq.top().dist;
        if(visited[pq.top().idx]==1) {
            pq.pop();
            continue;
        }
        visited[pq.top().idx]=1;
        pq.pop();

        for(i=0;i<A[min_idx].size();i++) {
            if(visited[A[min_idx][i].node]==0 && dist[A[min_idx][i].node]>_min+A[min_idx][i].val) {
                dist[A[min_idx][i].node]=_min+A[min_idx][i].val;
                srg.idx=A[min_idx][i].node;
                srg.dist=_min+A[min_idx][i].val;
                pq.push(srg);
            }
        }

    }
    for(i=1;i<=n;i++) {
        if(dist[i]!=INF) {
            printf("%lld\n",dist[i]);
        } else {
            printf("INF\n");
        }
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&e);
    scanf("%d",&s);
    int i,a;
    tuple2 srg;
    for(i=0;i<e;i++) {
        scanf("%d %d %d",&a,&srg.node,&srg.val);
        A[a].push_back(srg);
    }
    for(i=1;i<=n;i++) dist[i]=INF;
    dijkstra();
    return 0;
}