단일 시작점 최단 경로 알고리즘 (다익스트라, 벨만 포드)
가중치 그래프에서 시작 정점 s에서 다른 정점들 사이의 최단 경로를 구해보자!
일단, 시작 정점 s에서 어떤 정점 v사이의 거리를 배열(distance[v])로 나타내 보자.
그러면 distance[s] = 0이라고 표현할 수 있다.
*최단 경로를 구하기 위한 완화 작업(Relax)이란?*
시작 정점 s에서 v로 가는 경로에서, 간선 u->v를 사용하는 것이 이득인지 판단하는 검사이다.
즉, 시작 정점 s에서 v로 가는 기존 경로와 시작 정점 s에서 정점 u를 지나 v로 가는 경로 중 더 짧은 거리를 선택한다는 의미이다. (더 짧아지는 경우 갱신한다.)
 |
 |
distance[v] = min(distance[v], distance[u] + weight(u->v))
//u를 거치는 방법으로 갱신이 일어난 경우 "완화했다"라고 표현한다.
다익스트라 알고리즘
가중치 그래프에서 시작 정점과 다른 정점들 사이의 최단 경로를 구할 수 있는 다익스트라 알고리즘을 알아보자.
우선순위 큐를 이용해서 이웃한 정점 중 가장 거리가 적은 정점(cost가 적은 정점)부터 탐욕적으로 방문하면서 최단거리를 갱신하는 방법이다.
우선순위큐 pq에는 정점의 정보 pair{distance[u](s와 정점 사이의 거리), u(정점의 번호}를 넣는다.
1. 시작 정점을 제외한 모든 정점의 경로(거리) distance[x]를 무한대로 초기화해준다. (방문 안 함)
2. 시작 정점을 pq에 넣어준다. -> (0, s)
3. pq에서 꺼낸 어떤 정점 u에서, u에 대한 모든 이웃 정점 v에 대해 relax를 시도한다.
이때, relax가 일어나면 v에 대한 새로운 정보를 pq에 저장한다.
(**방문되지 않았던 점들을 방문할 때는 항상 relax 된다.)
4. pq에 아무것도 없을 때까지 pq에서 가장 적은 cost를 가진 정점을 꺼내 반복한다.
(**긴 거리는 pq에서 나중에 삭제된다.)
코드는 다음과 같다.
void dijkstra(int s) {
fill(dis, dis + V + 1, INF);
priority_queue<pair<int, int>> pq; //{s와 정점 사이의 거리, 정점의 번호}
distance[s] = 0;
pq.push({ 0,s });
while (!pq.empty()) {
int d = -pq.top().first; // s와 정점 사이의 거리
int u = pq.top().second; // 정점
pq.pop();
if (d > dis[u]) //d가 (시작~정점)보다 더 크면 가지 않는다(느긋한 삭제)
continue;
for (int i = 0; i < adj[u].size();i++) {
int v = adj[u][i].first; // 이웃 정점
int c = adj[u][i].second; //(u->v cost)
if (distance[v] > distance[u] + c) { // relax
distance[v] = distance[u] + c;
pq.push({ - distance[v], v });
}
}
}
}만약 주어진 그래프에 가중치가 음수인 간선이 존재한다면, 다익스트라 알고리즘으로는 최단 경로를 구할 수 없다.
그렇다면 어떻게 최단 경로를 찾을 수 있을까?
벨만-포드 알고리즘
음수 사이클이 존재하는 그래프에 대해 단일 시작점 최단 경로를 구하는 알고리즘이다.
-> 음수 사이클이란, 사이클 내에 음수인 간선이 존재하는 것을 말한다.
다익스트라에서 음수사이클이 존재하면 안되는 이유
-> 음수 사이클이 존재하면, 사이클내에서 최단거리를 갱신할 때 계속 음의 무한대로 발산한다.
- 모든 E개의 간선에 대해 V-1번** 완화 작업을 수행하면, 시작 정점으로부터 모든 정점의 최단경로를 구할 수 있다.
** 최단경로는 항상 V-1개의 간선을 가진다.
만일 V-1번의 완화 작업 후에 아직 완화할 수 있는 간선이 있다면, 음수 사이클이 존재한다는 뜻이다.
(+) 벨만 포드 알고리즘은 그래프의 모든 간선을 살펴보기 때문에, 다익스트라보다는 시간이 오래걸린다.
하지만 음수 사이클이 존재하더라도 절대 무한 루프에 빠지지 않는다는 것을 보장한다!
코드는 다음과 같다.
bool Bellman_Ford(int s) {
fill(dist, dist + v + 1, INF);
dist[s] = 0;
for (int i = 0;i < v-1;i++) {
for (int j = 0;j < edge.size();j++) {
int u = edge[j].second.first;
int v = edge[j].second.second;
long long cost = edge[j].first;
//relax
if (dist[u] != INF && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
}
}
}
//음의 사이클 확인
for (int j = 0;j < edge.size();j++) {
int u = edge[j].second.first;
int v = edge[j].second.second;
long long cost = edge[j].first;
if (dist[u] != INF && dist[v] > dist[u] + cost) { // 아직도 relax가 가능하면 음수사이클
dist[v] = -INF;
return false;
}
}
return true;
}