다익스트라 알고리즘 Dijkstra

최단거리를 구할때 BFS를 쓰는 경우가 많은데,

만약 정점 간 거리가 일정하지 않다면, 다익스트라를 쓰면된다 (BFS와 기본로직은 비슷하다)

다익스트라는 시작 정점에서 다른 모든 정점으로의 최단거리를 한 번에 구할 수 있다.

(모든 정점에서 다른 모든 정점은 아닌것에 주의, 이걸 원한다면 플로이드 와샬 알고리즘을 써야한다)

주의할점은 정점간 거리에 음수가 있으면 안된다는 점이다.(negative edge)

이때는 벨만-포드 알고리즘을 써야한다.

근데, negative edge가 안되는 버전이 가장빠르고, 하나의 정점을 두번이상 방문하지 않기는 하는데,

> enqueue, dequeue는 여러번 되는데 첫번째 dequeue만 효과를 가지고 나머지는 무시된다는걸 이해하는게 중요하다. visit 배열을 사용해서 두번째 이후 dequeue를 강제로 무시해도 OK. 무시되지 않는 dequeue를 "방문"이라고 생각하면 하나의 정점을 한 번만 방문하는게 맞다. enqueue/dequeue는 오히려 간선관점에서 O(E)안에 포함된다고 보는게 맞을거 같다.

하나의 정점을 여러번 방문할 수 있게 허용하면 negative edge를 가지는 경우에도 쓸 수 있다.

아래 내 소스에서 min_dist[n.v] != INF 이부분을 min_dist[n.v] < n.w 이렇게 바꾸면, 여러번 방문할 수 있게 허용하는 버전이 된다.

이 답변에서 3번 variant가 되는 것

근데 사실 이렇게 재방문을 허용하게 되면 다익스트라만의 complexity 장점이 사라지는 셈이라,

SPFA를 쓰는게 더 좋은경우가 생기는걸 보았다.

실제로 발생하면 SPFA쪽을 사용하자.

내가 작성한 PS에서 사용하는 다익스트라 로직은 다음과 같다.

(백준 1753 문제의 답안이기도 하다)

근데 여기에 따르면 아래구현은 이미 방문한 정점을 다시 방문시 TLE로 만들 수 있으며

q.pop()한다음에 if(n.w > min_dist[n.v]) continue; 이 코드를 넣어줘야 한다고 한다. 나중에 체크해보자.

#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
bool operator<(node l, node r) { if (l.w == r.w)return l.v > r.v; return l.w > r.w; }
using vi = vector<int>;
using vvn = vector<vector<node>>;
const int INF = INT_MAX / 4;
vi Dijkstra(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    if (base1) max_v++;
    vi min_dist(max_v, INF);  // 거리 무한대로 초기화
    priority_queue<node> q;
    q.push({ start_v, 0 });  // 거리 0으로 시작정점 enqueue
    min_dist[start_v] = 0;   // 시작점 스스로의 거리는 0 (문제에 따라 중요한 경우 있음)
    while (q.size()) {
        node n = q.top(); q.pop();
        for (auto adj : adj_list[n.v]) {
            // min_dist를 통한 visit 처리(enqueue하기 전에 visit처리해주는게 중요하다)
            if (min_dist[adj.v] > n.w + adj.w) {
                min_dist[adj.v] = n.w + adj.w;
                q.push({ adj.v, adj.w + n.w });
            }
        }
    }
    return min_dist;
}
 
int main()
{
    //V:정점개수, E:간선개수, K:시작점
    int V, E, K; scanf("%d%d%d", &V, &E, &K);
    vector<vector<node>> adj_list(V + 1);
    for (int i = 0; i < E; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    vector<int> d = Dijkstra(V, K, adj_list, true);
    for (int i = 1; i <= V; i++)
        if (d[i] == INF)puts("INF");
        else printf("%d\n", d[i]);
    return 0;
}

Tip1

최단거리 이외에 비용등의 추가 constraint가 붙을 경우 min_dist가 현재 1차원 배열인데 2차원으로 차원을 늘리면 풀릴 수 있다. (백준 10217번이 그 예)

참고로 위 소스에서 min_dist는 int min_dist[max_v + 1]; 로 해도 되지만 max_v가 상수가 아닌 변수여서 vector로 해놓은건데,

차원이 늘어나서 int min_dist[max_v + 1][M + 1]; 과 같은 형태가 된다면 vector of vector가 필요하다. 

이때는 약간 복잡해보일수는 있으나, 다음과 같이 코딩하면 된다.

    vector<vector<int>> min_dist(max_v + 1, vector<int>(M+1, INF));
 

최대값을 상수값으로 적는대신 변수값으로 가변적으로 세팅할 수 있는 장점(이때문에 문제마다 최대값에 따라 101, 2001등 수정할 필요가 없어진다) 이외에, 덤으로 초기값을 INF로 별도 loop없이 편하게 줄 수 있는 장점도 있다.

경로추적

경로추적이 필요한 경우에는 아래 소스처럼 from 배열을 하나 운영하면 된다. 이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 4;
struct node { int v, w; };
bool operator<(node l, node r){if(l.w==r.w)return l.v>r.v; return l.w>r.w;}
int n, m, s, e;
typedef vector<vector<node>> vvn;
typedef vector<int> vi;
vector<int> Dijkstra(int max_v, int start_v, vvn& adj_list, vi& from) {
    vector<int> min_dist(max_v + 1, INF);
    priority_queue<node> q;
    q.push({ start_v, 0 });
    min_dist[start_v] = 0;
    while (q.size()) {
        node n = q.top(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (min_dist[adj.v] > n.w + adj.w) {
                min_dist[adj.v] = n.w + adj.w;
                q.push({ adj.v, adj.w + n.w }), from[adj.v] = n.v;  // 경로 기록
            }
        }
    }
    return min_dist;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    vvn adj_list(n + 1);
    vi from(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    scanf("%d%d", &s, &e);
    vi d = Dijkstra(n, s, adj_list, from);
    printf("%d\n", d[e]);
    if (s == e) {
        printf("1\n%d\n", s);
        return 0;
    }
    deque<int> dq;
    while (e != s && from[e] != -1)dq.push_front(e), e = from[e];
    dq.push_front(s);
    printf("%d\n", dq.size());
    for (auto a : dq)printf("%d ", a); puts("");
 
    return 0;
}

복잡도

BFS의 복잡도가 $O(E+V)$ 인데 반해서 다익스트라의 복잡도는 $O((V+E)\times log(V))$이다. 왜 다익스트라가 더 높냐구? 다익스트라는 BFS와 다르게 간선거리를 고려해야하므로, priority queue를 써야하고 그에 따라 $log(V)$가 추가되는 것.BFS는 그냥 queue를 쓰므로 $O(1)$. 

보통은 아무리 sparse해도 정점이 간선보다 많은 경우는 문제로 잘 안주어진다 따라서 $E >= V$인 경우가 대부분이고 이렇게 되면 복잡도가 $O(E \times log(V))$이다. 이것 때문에 다익스트라 복잡도를 보통 이걸로 얘기하는 것. 트리의 경우는 $E=V-1$이지만, dense한 그래프의 경우 $E \sim V^2$이므로 이 경우는 $O(V^2log(V))$정도로 심플하게 봐도 좋다.