📍 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(a.k.a. 종만북)>으로 공부한 내용을 정리한 게시글입니다.
최단 경로 알고리즘
주어진 두 정점을 연결하는 가장 짧은 경로의 길이
📍 가중치가 없는 그래프에 대한 최단 경로는 BFS(너비 우선 탐색)으로 찾을 수 있음
단일 시작점 알고리즘
하나의 시작점에서 다른 모든 정점까지 가는 최단거리를 구함
모든 쌍 알고리즘
모든 정점의 쌍에 대해 최단 거리를 계산 -> 결과는 V x V 크기의 배열
다익스트라(Dijkstra) 알고리즘
- 단일 시작점 최단 경로 알고리즘(시작 정점 s에서부터 다른 정점들까지의 최단 경로 계산)
- 우선순위 큐를 사용하는 너비 우선 탐색(bfs)
❕ 음수 가중치를 갖는 간선(음수 간선)이 있는 경우 가중치의 합이 음수인 사이클(음수 사이클)이 등장할 수 있어 최단 경로 문제가 제대로 정의되지 않음
구현
int V; // 정점의 개수
vector<pair<int, int>> adj[MAX_V] // (연결된 정점 번호, 간선 가중치)
vector<int> dijkstra(int src) {
vector<int> dist(V, INF); // INF는 무한대
dist[src] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, src));
while(!pq.empty()) {
int cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
// cost는 음수
// 지금 꺼낸 것(dist[here])보다 더 짧은 경로를 알고있다면 무시
if(dist[here] < cost) continue;
for(int i = 0; i < adj[here].size(); ++i) {
int there = adj[here[i].first;
int nextDist = cost + adj[here][i].second;
// 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣음
if(dist[there] > nextDist) {
dist[there] = nextDist;
pq.push(make_pair(-nextDist, there));
}
}
}
return dist; // 각 정점까지의 최단 거리가 들어있는 배열 반환
}📍 우선순위 큐에 거리의 부호를 바꿔서(음수) 넣음
: priority_queue는 가장 큰 원소가 위로 가도록 구성하기 때문에, 거리가 작은 정점부터 꺼내지도록 부호를 바꿈
📍 한 정점에 대한 최단 거리가 갱신될 경우 큐에 중복 원소를 넣음
: 어떤 원소 (cost, u)를 꺼냈는데 dist[u] 가 cost보다 작다면 중복으로 들어간 원소 -> 무시하고 다음 원소를 꺼냄
우선순위 큐를 사용하지 않는 다익스트라 구현
- 정점의 수가 매우 적은 경우
- 간선의 수가 매우 많은 경우
다음에 방문할 정점을 큐에 보관하지 않고 매번 반복문을 이용해 방문하지 않은 정점 중 dist[] 가 가장 작은 값을 찾음
vector<int> dikstra2(int src) {
vector<int> dist(V, INF);
vector<bool> visit(F, false);
dist[src] = 0;
visit[src] = 1;
while(true) {
// 아직 방문하지 않은 정점 중 가장 가까운 정점을 찾음
int here, closest = INF;
for(int i = 0; i < V; ++i) {
if(dist[i] < closest && !visit[i]) {
here = i;
closest = dist[i];
}
if(closest == INF) break;
// 가장 가까운 정점 방문
visit[here] = 1;
for(int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i].first;
if(visit[there]) continue;
int nestDist = dist[here] + adj[here][i].second;
dist[there] = min(dist[there], nextDist);
}
}
return dist;
}벨만-포드(Bellman-Ford) 알고리즘
시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤, 예측값과 실제 최단 거리의 오차를 반복적으로 줄여나가는 방식
- 단일 시작점 최단 경로 알고리즘(시작 정점 s에서부터 다른 정점들까지의 최단 경로 계산)
- 음수 간선이 있는 그래프에서의 최단 경로도 찾을 수 있음
- 음수 사이클이 있는 경우 알려줌
동작 방식
upper[s] = 0, 나머지 원소는 INF로 초기화
dist[v] <= dist[u] + w(u, v)
- 시작점에서 u와 v까지의 최단 거리
dist[u]와dist[v]에 대해 항상 참upper[v] > upper[u] + w(u, v)인 경우upper[v] = upper[u] + w(u, v)로 줄임 : 완화(relax)- 완화가 성공할 때마다 upper는 줄어들고, 실제 최단 거리에 가까워짐
upper[a] == w(s, a) 이면 a에 대한 최단 경로를 찾은 것(s는 시작점)
모든 간선에 대해 완화를 시도하는 작업을 x번 반복하면 x개 이하의 간선을 사용하는 최단 경로들을 전부 찾을 수 있음
➡️ 모든 간선이 전부 완화가 실패할 때까지 반복하면 모든 최단 경로를 찾을 수 있음 == |V| - 1번
음수 사이클 판정
|V|번 완화 시도
- 음수 사이클이 없는 경우
|V| - 1번의 반복으로 모든 최단 거리를 찾아내므로, 마지막 반복의 완화는 전부 실패 - 음수 사이클이 있는 경우
|V|번째 반복에서도 항상 완화가 한 번은 성공
구현
int V; // 정점의 개수
vector<pair<int, int>> adj[MAX_V];
// 음수 사이클이 있는 경우 텅 빈 배열 반환
vector<int> bellmanford(int src) {
vector<int> upper(V, INF);
upper[src] = 0;
bool updated;
for(int it = 0; it < V; ++it) {
updated = false;
for(int here = 0; here < V; ++here) {
for(int i = 0; i < adj[here].size(); i++) {
int there = adj[here][i].first;
int cost = adj[here][i].second;
// (here, there) 간선을 따라 완화 시도
if(upper[there] > upper[here] + cost) {
upper[there] = upper[here] + cost;
updated = true;
}
}
// 모든 간선에 대해 완화가 실패했을 경우 바로 종료(최소 경로)
if(!updated) break;
}
// V번째 순회에 완화가 성공했다면 음수 사이클
if(updated) upper.clear();
return upper;