다익스트라, 벨만-포드, 플로이드-워셜

그래프 문제를 보다 보면, 특정 노드 a에서 노드 b까지의 경로를 구하는 문제가 자주 보인다. 이런 그래프에서 경로를 구하는 문제에 주로 사용하는 알고리즘이 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이다.

다익스트라는 그래프에 음의 가중치를 갖는 에지가 없을 때 주로 사용한다. 시작 노드에서 특정 경로를 이동해 노드 n에 도착했을 때의 비용을 cost[n]으로 나타낼 때, n에 연결된 i번째 에지 e_i와 e_i에 연결된 노드 n_i에 대해, n_i를 방문하지 않았다면 cost[n_i]가 cost[n] + e_i보다 작을 때 기존 경로를 시작 노드에서 n까지의 경로 + e_i로 갱신하면 더 적은 비용으로 n_i까지 이동할 수 있다. 이 과정을 알려진 경로가 존재하지 않을 때부터 시작해서 더 이상 갱신할 수 있는 경로가 없을 때까지 반복한다면 시작 노드부터 모든 노드로의 최단 경로와 그 비용을 알아낼 수 있다.

typedef pair<int, int> edge;

#define _cost first
#define _node second

int dijkstra(int s, int e) {
    int cost[MAX_N + 1];
    priority_queue<edge, vector<edge>, greater<edge>> q;

    fill_n(cost, node + 1, INF);
    cost[s] = 0;

    q.push({0, s});

    while (!q.empty()) {
        edge e = q.top();
        q.pop();
        
        if (e._cost > cost[e._node]) continue;

        for (auto e_ : graph[e._node]) if (cost[e_._node] > e._cost + e_._cost)
            q.push({cost[e_._node] = e._cost + e_._cost, e_._node});
    }

    return cost[e];
}

다익스트라를 사용할 경우 그래프에 음의 가중치를 가진 에지가 존재한다면, 해당 에지를 이용할 때마다 비용이 줄어드므로 무한 루프에 빠질 가능성이 있다. 이 때문에 고안된 것이 벨만-포드 알고리즘으로, 노드의 개수가 N개일 때 모든 노드를 각각 한 번씩 방문한다고 하면 에지를 N - 1개 사용하게 되므로 에지를 최대 N - 1개를 사용해 얻을 수 있는 최단 경로와 그 비용을 구한다. 이 이후 다시 한번 에지를 사용해 갱신 가능한 비용이 존재한다면, 그 경로는 무한히 비용 갱신이 가능하고 언젠가 비용이 음수로 변할 것이므로 그 이상 탐색하지 않는다.

typedef pair<int, int> edge;

#define _cost first
#define _node second

bool push(int node) {
    bool ret = false;
    int cost_;

    q.pop();

    for (edge e : v[node]) {
        cost_ = cost[node] + e._cost;

        if (cost[e._node] <= cost_) continue;

        cost[e._node] = cost_;
        q.push(e._node);

        ret = true;
    }

    return ret;
}

bool bellman_ford() {
    int size = q.size();

    for (int i = 1; i < N; i++) {
        while (size--) push(q.front());
        size = q.size();
    }

    while (size--) if (push(q.front())) return true;
    return false;
}

다익스트라와 벨만-포드가 한 노드에서 모든 노드로의 경로를 계산한다면, 플로이드-워셜 알고리즘은 모든 노드에서 모든 노드로의 비용을 계산한다. 플로이드-워셜에선 노드 i에서 노드 j로의 비용 cost[i][j]을 경유지 k를 이용해 갱신하는데, 만일 costi][j]가 cost[i][k] + cost[k][j]보다 작다면 노드 i에서 j로 갈 때 기존 경로가 아닌, i에서 k까지 이동한뒤 다시 k에서 j까지 이동하는 것이다. 이 과정을 i, j, k 세 값에 대해 for 루프를 돌리는데, 이 때 중요한 건 i -> j -> k 순으로 루프를 돌리는 것이 아니라 k -> i -> j 순으로 루프를 돌려야 알고리즘이 정상적으로 작동하게 된다.

for (k = 0; k < n; k++)
    for (i = 0; i < n; i++) for (j = 0; j < n; j++)
        graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

https://www.acmicpc.net/problem/1753

1753번: 최단경로

https://www.acmicpc.net/problem/1865

1865번: 웜홀

https://www.acmicpc.net/problem/11404

11404번: 플로이드