최단 경로 알고리즘
그래프에서 노드 간의 가장 짧은 경로를 찾고자 할 때 사용한다.
알고리즘의 종류는 3가지로 문제의 요구사항과 간선에 부여된 가중치의 상태에 따라 효과적인 알고리즘을 골라 사용하면 된다.
1. 다익스트라(Dijkstra)
다익스트라 알고리즘은 특정한 하나의 노드에서 다른 모든 노드로 가는 최단 경로를 구할 수 있다.
간선의 가중치가 0 이상으로 이루어져 있을 때 사용할 수 있다.
매번 가장 적은 비용을 선택해가며 이를 그대로 사용하기에 그리디+DP 문제이다.
작동 과정은 다음과 같다.
① 출발 노드 설정
② 출발 노드를 기준으로 최단 경로 배열 갱신
③ 방문하지 않은 노드 중에서 비용이 가장 적은 노드 선택
④ 해당 노드를 거쳐 다른 노드로 가는 최단 경로 갱신
⑤ 3, 4번을 반복
#include <iostream>
#include <vector>
#include <queue>
#define ll long long
#define pii pair<int, int>
#define INF 0x3f3f3f3f
using namespace std;
vector<pii> node[101]; //node[from][i] = {to, weight}
int d[101]={0,};
int v, e; //v:노드 개수 e:간선 개수
//적은 비용을 우선으로 선택하기 위한 정렬
struct cmp{
bool operator()(pii a, pii b){
return a.second < b.second;
}
};
void dijkstra(int start){
for(int i=1;i<=v;i++) d[i] = INF;
d[start] = 0;
priority_queue<pii, vector<pii>, cmp> pq;
pq.push(make_pair(start, 0));
while(!pq.empty()){
int current = pq.top().first;
int distance = -pq.top().second;
pq.pop();
if(d[current] < distance) continue;
for(int i=0;i<node[current].size();i++){
int next = node[current][i].first;
int nextdistance = distance + node[current][i].second;
if(nextdistance < d[next]){
d[next] = nextdistance;
pq.push(make_pair(next, -nextdistance));
}
}
}
}O((V+E)logV)의 시간복잡도를 가지며 3가지 알고리즘 중에 가장 빠른 시간복잡도이다.
2. 플로이드 워셜(Floyd Warshall)
플로이드 워셜 알고리즘은 모든 노드에서 모든 노드로 가는 최단 경로를 한 번에 구할 수 있다.
그래프에 음수 사이클이 존재하지 않으면 간선이 음의 가중치를 가지더라도 사용할 수 있다.
모든 노드를 거쳐가며 최단 경로를 갱신하기에 DP 문제이다.
거쳐가는 노드를 기준으로 반복문을 돌리며 작동한다.
#include <iostream>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define INF 0x3f3f3f3f
using namespace std;
vector<pii> node[101]; //node[from][i] = {to, weight}
int d[101][101]={0,};
int v, e; //v:노드 개수 e:간선 개수
void floydwarshall(){
for(int i=1;i<=v;i++){
for(int j=1;j<=v;j++){
if(i==j) d[i][j]=0;
else d[i][j] = INF;
}
}
for(int i=1;i<=v;i++){
for(int j=0;j<node[i].size();j++){
d[i][node[i][j].first] = min(node[i][j].second, d[i][node[i][j].first]);
}
}
//k:거쳐가는 노드
for(int k=1;k<=v;k++){
for(int i=1;i<=v;i++){
for(int j=1;j<=v;j++){
if(d[i][k]+d[k][j]<d[i][j]) d[i][j] = d[i][k]+d[k][j];
}
}
}
return ;
}O(V³)의 시간복잡도를 가진다.
3. 벨만 포드(Bellman Ford)
벨만 포드 알고리즘은 특정한 하나의 노드에서 다른 모든 노드로 가는 최단 경로를 구할 수 있다.
간선이 음의 가중치를 가지더라도 사용할 수 있으며 음의 사이클을 감지할 수 있다.
다익스트라 알고리즘은 가장 적은 비용의 노드를 선택하여 최단 경로를 구해가지만 벨만 포드 알고리즘은 모든 간선을 확인하면서 최단 경로를 구해나가기에 완전 탐색 문제이다. (다익스트라 알고리즘의 해를 항상 포함한다.)
작동 과정은 다음과 같다.
① 출발 노드 설정
② 출발 노드를 기준으로 최단 경로 배열 갱신
③ 간선을 하나 선택
④ 선택한 간선을 거쳐 다른 노드로 가는 경로를 계산하여 최단 경로 배열 갱신
⑤ 3, 4번을 반복
#include <iostream>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define INF 0x3f3f3f3f
using namespace std;
vector<pair<pii, int>> edge; //edge[i] = {{from, to}, weight}
int d[101]={0,};
int v, e; //v:노드 개수 e:간선 개수
bool bellmanford(int start){
for(int i=1;i<=v;i++) d[i]=INF;
d[start]=0;
for (int i = 1; i <= v-1; i++){
for (int j = 0; j < e; j++){
int from = edge[j].first.first;
int to = edge[j].first.second;
int cost = edge[j].second;
if (d[from] == INF) continue;
if (d[to] > d[from] + cost) d[to] = d[from] + cost;
}
}
for (int i = 0; i < e; i++){
int from = edge[i].first.first;
int to = edge[i].first.second;
int cost = edge[i].second;
if (d[from] == INF) continue;
//음의 사이클이 존재한다
if (d[to] > d[from] + cost) return true;
}
//음의 사이클 존재하지 않는다
return false;
}O(VE)의 시간복잡도를 가진다.