Dijkstra Algorithm

활용

최단거리 문제를 해결하는 가장 대표적인 알고리즘이다.
특정 정점에서 모든 정점으로의 최단거리를 구할 수 있다.
음의 가중치가 존재하지 않을 때 사용 가능하다는 특징이 있다.

구체적으로 어떤 원리로 동작하는지, 나는 아래 블로그를 통해 제대로 이해할 수 있었다.
왜 음의 가중치가 존재할 때, 사용할 수 없는지도 잘 설명되어 있다.

• 참고 블로그

이 알고리즘을 만든 '다익스트라'라는 사람은 20분만에 머릿속으로 떠올렸다는데...
굳이 좌절하지말고 열심히 익히자.. 알고나면 다 똑같다.

---

구현

무방향 그래프에 대해서 정점의 개수 n과 간선의 개수 m이 주어지고
간선에 대한 정보가 시작 정점, 도착 정점, 가중치 순으로 m개가 주어졌을 때
1번 정점에서 시작하는 다익스트라 알고리즘의 예시를 구현하면 아래와 같다.
정점의 개수는 최대 100개, 가중치는 정수로 최대 1000이라고 가정한다.

두 가지 구현 방법이 있다.

1. 배열

#include <iostream>
#include <vector>
#define INF 100000
using namespace std;
vector<pair<int, int> > map[101];

int main()
{
    int n, m, a, b, c;
    cin >> n >> m;
    vector<int> dist(n+1);
    vector<int> ch(n+1);
    for (int i = 1; i <= m; ++i) {
        cin >> a >> b >> c;
        map[a].push_back(make_pair(b, c));
    }
    dist[1] = 0;
    
    for (int i = 1; i <= n; ++i) {
    	int min = 0;
        for (int j = 1; j <= n; ++j) {
            if (ch[j] == 0 && dist[j] < dist[min]) {
                min = j;
            }
        }
        ch[min] = 1;
        for (int j = 0; j < map[min].size(); ++j) {
            int next = map[min][j].first;
            int cost = map[min][j].second;
            if (dist[next] > dist[min] + cost) {
                dist[next] = dist[min] + cost;
            }
        }
    }
    if (dist[n] == INF) cout << -1 << endl;
    else cout << dist[n] << endl;
    return 0;
}

그래프의 정점 및 간선 데이터는 크게 인접 리스트와 인접행렬로 정리할 수 있는데, 시간 복잡도 측면에서 인접 리스트가 훨씬 유리하다. 인접리스트를 STL vector를 활용해서 동적할당으로 구현하고 싶은데.. 아직 그 방법은 알아내지 못했다.

배열로 구현했을 때의 시간 복잡도 $= O(n^2)$

알고리즘 문제를 풀다보면 배열로 구현했을 경우, 시간초과가 나는 경우가 많다.
그리 빠르지 않다는 것인데, 왜 그런지는 아래 블로그에 잘 설명되어 있다.

• 참고 블로그

---

2. 우선순위 큐

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int> > map[101];

class Info {
public:
    int node;
    int cost;
    
    Info(int a, int b) {
    	this->node = a;
        this->cost = b;
    }
    bool operator<(const Info &rhs) const {
    	return this->cost > rhs.cost;
    }
};
priority_queue<Info> pq;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> dist(n+1, INF);
    for (int i = 1; i <= m; ++i) {
        cin >> a >> b >> c;
        map[a].push_back(make_pair(b, c));
    }
    dist[1] = 0;
    pq.push(Info(1, 0));
    
    while (!pq.empty()) {
        int node = pq.top().node;
        int cost = pq.top().cost;
        pq.pop();
        if (dist[node] < cost) continue;
        for (int i = 0; i < map[node].size(); ++i) {
            int nextNode = map[node][i].first;
            int nextCost = map[node][i].second;
            if (dist[nextNode] > dist[node] + nextCost) {
                dist[nextNode] = dist[node] + nextCost;
                pq.push(Info(nextNode, dist[nextNode]));
            }
        }
    }
    cout << dist[n] << endl;
    return 0;
}

클래스를 정의한 것은 우선순위 큐의 우선순위를 커스터마이징하기 위함이다.
연산자 오버로딩을 통해서 가중치를 기준으로 작은 값이 우선순위를 갖도록 했다.
클래스를 정의하지 않더라도 우선순위 큐의 파라미터를 잘 활용하면
원하는 대로 우선순위를 매길 수 있긴하다.

우선순위 큐로 구현했을 때의 시간 복잡도 $= O(E*logN)$

E는 간선의 수, N은 정점의 수를 의미한다. 기본적으로 로그이므로 배열을 활용한 구현보다는
훨씬 빠르게 동작함을 알 수 있다.

시간 복잡도를 나름대로 정리했으나, 이런 것들은 대체 어떻게 계산되는지
아직 완벽하게 이해되지는 않는다. 좀 더 깊은 공부가 필요하다...