Shortest path
최단 경로 문제는 그래프를 이용한 문제에서 매우 흔히 보이는 유형입니다. 그럼 최단 경로의 정의는 무엇일까요? 최단 경로란 말 그대로 가장 짧은 경로를 뜻합니다. 정점들 사이에 가중치가 있다고 가정하였을 때, 그 가중치의 합이 최소가 되는 경로를 뜻하는 것이죠. 이러한 최단 경로에는 아래와 같이 다양한 종류가 있습니다.
- 시작점을 기준으로 도착점까지의 최단 경로
- 시작점을 기준으로 다른 모든 정점까지의 최단 경로
- 모든 정점 사이의 최단 경로
- 음의 가중치를 갖는 간선이 있는 경우의 최단 경로
이러한 다양한 종류들에 대해 각각 적용하기 알맞은 알고리즘들이 존재합니다.
- (1) -> Priority Queue를 이용한 BFS
- (2) -> Dijkstra Algorithm
- (3) -> Floyd-Warshall Algorithm
- (4) -> Bellman-Ford Algorithm
이번주는 2,3,4번에 대해 자세히 알아보았습니다.(1번의 경우는 이미 다뤘었기 때문입니다.)
Dijkstra Algorithm
Dijkstra Algorithm은 출발점을 기준으로 다른 모든 정점까지의 최단 경로를 구해주는 알고리즘입니다. 이 알고리즘은 아래와 같은 과정으로 진행됩니다. 그리고 해당 알고리즘을 구현할 때 Priority Queue를 사용하면 거리에 정점을 갱신하기 위해 거리를 비교하는 과정을 생략할 수 있으므로 더 편하게 구현할 수 있습니다.
- 시작 정점 결정하고 해당 정점을 현재 위치로 선택
- 시작 정점을 제외한 모든 정점까지의 거리를 매우 큰 수로 설정
- 현재 위치에서 갈 수 있는 모든 정점을 확인하고 더 짧은 경로로 이동할 수 있다면 거리를 갱신
- 아직 방문하지 않은 정점 중, 가장 가까운 거리에 있는 정점을 현재 정점으로 선택
- 거리와 현재 정점을 갱신하며 모든 정점을 방문할 때까지 반복
Dijkstra Algorithm Code
#include<bits/stdc++.h>
using namespace std;
struct EDGE {
int to, w;
};
vector<EDGE> adj[101010];
bool operator < (EDGE e1, EDGE e2) {
return e1.w > e2.w;
}
vector<int> Dijkstra(int st, int v) {
vector<int> ans(v + 1);
vector<int> chk(v + 1);
fill(ans.begin(), ans.end(), 1e9);
priority_queue<EDGE> q;
q.push({ st, 0 });
ans[st] = 0;
while (q.size()) {
auto cur = q.top(); q.pop();
int x = cur.to, w = cur.w;
if (chk[x]) continue;
chk[x] = 1;
for (auto nx : adj[x]) {
if (ans[nx.to] > w + nx.w) {
ans[nx.to] = w + nx.w;
q.push({ nx.to, w + nx.w });
}
}
}
return ans;
}
int main() {
adj[0].push_back({ 1, 2 });
adj[0].push_back({ 2, 3 });
adj[0].push_back({ 3, 6 });
adj[1].push_back({ 0, 2 });
adj[1].push_back({ 3, 3 });
adj[1].push_back({ 5, 7 });
adj[2].push_back({ 0, 3 });
adj[2].push_back({ 3, 1 });
adj[2].push_back({ 4, 2 });
adj[3].push_back({ 0, 6 });
adj[3].push_back({ 1, 3 });
adj[3].push_back({ 5, 1 });
adj[3].push_back({ 4, 3 });
adj[4].push_back({ 2, 2 });
adj[4].push_back({ 3, 3 });
adj[4].push_back({ 6, 5 });
adj[5].push_back({ 1, 7 });
adj[5].push_back({ 3, 1 });
adj[5].push_back({ 6, 1 });
adj[6].push_back({ 5, 1 });
adj[5].push_back({ 4, 5 });
vector<int> answer = Dijkstra(0, 6);
int i = 0;
for (auto element : answer) {
cout << i++ << ": ";
cout << element << endl;
}
return 0;
}
Floyd-Warshall Algorithm
Floyd-Warshall Algorithm은 모든 정점들에 대하여 최단거리를 구해주는 알고리즘입니다. 이 알고리즘을 구현할 때는 다른 알고리즘들처럼 인접 리스트가 아닌 인접 행렬을 사용합니다. 해당 알고리즘은 가장 간단하게 구현할 수 있는 최단 거리 알고리즘이라고 합니다. 알고리즘의 핵심 아이디어는 간단합니다. 두 정점 u, v의 경로 사이에 k가 추가되었을 경우, (u,v)의 경로와 (u,k)+(k,v)의 경로를 비교하여 더 작은 값으로 갱신해주는 것입니다. 단 구현할 때 주의해야할 점은 이동할 수 없는 간선은 매우 큰수로 초기화해줘야하고, 정점 사이에 간선이 여러 개가 존재할 경우, 그 중 가중치가 가장 작은 간선만 유지시켜줘야합니다. 그리고 이 알고리즘의 경우 경로 탐색시 조금 특이한 방식을 사용해야합니다. 거리가 갱신되었을 경우 u,v 경로에서 k를 방문하여 간다는 것을 기록하여 주는 것입니다. 아래의 코드로 구현과 함께 보는 것이 더 쉽게 이해가 갑니다.
Floyd-Warshall Algorithm Code
#include<bits/stdc++.h>
using namespace std;
int adj[505][505];
int path[505][505];
const int inf = 1e9;
void FloydWarshall(int v) {
for (int k = 1; k <= v; ++k)
for (int i = 1; i <= v; ++i)
for (int j = 1; j <= v; ++j) {
int next = adj[i][k] + adj[k][j];
if (adj[i][j] > next) {
adj[i][j] = next;
path[i][j] = k;
}
}
}
void PrintPath(int u, int v) {
if (path[u][v] == u)
printf("%d ", u);
else
PrintPath(u, path[u][v]);
printf("%d ", v);
}
int main() {
memset(adj, 0x3f, sizeof(adj));
adj[1][2] = 1;
adj[1][4] = 10;
adj[2][3] = 2;
adj[2][4] = 6;
adj[3][4] = 2;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
path[i][j] = i;
FloydWarshall(4);
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (adj[i][j] == 1061109567)
cout << 'X' << " ";
else
cout << adj[i][j] << " ";
}
cout << endl;
}
cout << "Path: ";
PrintPath(1, 4);
return 0;
}
Bellman-Ford Algorithm
Bellman-Ford Algorithm은 출발점을 기준으로 다른 모든 정점까지의 최단 경로를 구해주는 알고리즘입니다. 이 알고리즘은 Dijkstra Algorithm에 비해 시간은 오래 걸리지만, 음수 가중치가 포함되어도 최단 경로를 구할 수 있고, 음수 사이클 또한 찾을 수 있다는 장점이 있습니다. 해당 알고리즘을 구현할 때는 인접리스트를 사용하지 않고, 간선 정보만 저장하여 사용합니다. 아래와 같은 과정으로 진행됩니다.
- 시작 정점을 선택
- 시작 정점을 제외한 모든 정점까지의 거리를 매우 큰 수로 설정
- 모든 간선을 확인하며, 간선의 출발점까지의 거리가 무한대(매우 큰 수)가 아니고, 출발점을 거쳐 도착점으로 이동하였을 때의 거리가 이미 저장되어 있는 도착점까지의 거리보다 짧다면 거리를 갱신 (Relaxation)
- 이 과정을 V-1번 반복 (V개의 정점)
- V번 반복해서 V번째의 갱신이 일어나는 경우, 음수 사이클이 존재
여기서 왜 V번 반복했을 때 갱신이 일어나면 음수 사이클이 존재하는 것일까? V개의 정점으로 이루어진 경로에서 간선의 최대 갯수는 V-1일 것입니다. 아마 V-1번 도는 최악의 경우는 1 -> 2 -> 3 -> 4가 최단 경로일 경우 간선을 3->4, 2->3, 1->2 순으로 Relaxation을 진행하는 경우가 있을 것입니다. 이 경우 1->2, 2->3, 3->4 순으로 Relaxation이 일어나 최악의 경우인 3번의 사이클을 돌게 됩니다. 그리고 조금만 여러 예시를 생각해보면 해당 알고리즘을 한번 수행할 때마다 최소 1개 이상의 출발점으로부터의 최단거리를 구한 노드가 생기는 것을 알 수 있다. 따라서 일반적인 경우 V번째 과정에서는 Relaxation이 일어날 수 없습니다. 상식적으로 A -> B로 가는 최단 경로는 A에서 B로 가는 모든 간선을 통과한 V-1 이상이 될 수는 없기 때문이죠. 즉, 알고리즘을 더 진행했을 때 Relaxation이 일어나는 경우는 음수 사이클이 존재하는 경우 밖에 없습니다.
Bellman-Ford Algorithm Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EDGE {
ll from, to, w;
};
vector<EDGE> edges;
const ll inf = 1e9;
vector<ll> BellmanFord(int v, int st) {
vector<ll> res(v + 1);
fill(res.begin(), res.end(), inf);
res[st] = 0;
for (int i = 1; i <= v; ++i) {
for (int j = 0; j < edges.size(); ++j) {
ll s = edges[j].from, t = edges[j].to, w = edges[j].w;
if (res[s] != inf && res[t] > res[s] + w) {
if (i == v) {
res[0] = -1;
return res;
}
res[t] = res[s] + w;
}
}
}
return res;
}
int main() {
edges.push_back({ 1, 2, -2 });
edges.push_back({ 1, 3, 3 });
edges.push_back({ 1, 4, -6 });
edges.push_back({ 2, 4, 3 });
edges.push_back({ 2, 6, 7 });
edges.push_back({ 3, 4, 1 });
edges.push_back({ 3, 5, 2 });
edges.push_back({ 4, 5, -3 });
edges.push_back({ 4, 6, -1 });
edges.push_back({ 5, 7, 5 });
edges.push_back({ 6, 7, 1 });
vector<ll> answer = BellmanFord(7, 1);
int i = 0;
for (auto element : answer) {
if (i == 0) {
i++;
continue;
}
cout << i++ << ": ";
cout << element << endl;
}
return 0;
}
+) 정점 분할
일반적으로는 간선을 통해서 가중치가 부여되지만, 간혹 정점을 통과할 때 가중치가 부여되어야하는 경우가 있을 수 있습니다. 이 경우에서는 정점을 들어오는 정점과 나가는 정점으로 구분하여 그 두 정점을 연결하고 그 간선에 가중치를 부여하여 해결할 수 있습니다.
