목차
1. 플로이드-워셜 알고리즘
2. 데이크스트라 알고리즘
2. 벨만-포드 알고리즘
4. 최소 스패닝 트리 알고리즘(with 유니온 파인드 알고리즘)
1. 플로이드-워셜 알고리즘
플로이드-워셜 : 모든 정점으로부터 각 정점까지의 최단 거리를 찾아주는 알고리즘
동작 방식 : 가장 바깥 for문을 중간 정점(거쳐갈 정점) - 중간 for문을 시작 정점 - 마지막 for문을 끝정점으로 생각하고,
시작정점으로부터 끝 정점까지 가는 경우 중 중간 정점을 거쳐 가는 게 빠른지 아니면 그냥 가는 게 빠른지
탐색한다.(3중 for문 -> O(N^3) 알고리즘)
플로이드-워셜은 "각 정점으로부터 모든 정점으로의 최단 거리"를 찾아주는 알고리즘이다.
즉, 시작 정점으로부터 끝 정점까지 가는 경우 중 최단 거리를 탐색하는 데이크스트라, 벨만-포드와 달리,
모든 정점에서 모든 정점까지의 최단 거리를 반환한다.
이 때, 다른 경로 탐색 알고리즘과 달리 N(행)*N(열) 크기의 테이블을 만드는데, i번째 행의 j번째 열은 i번째 정점에서 j번째 정점으로 가는 최단 거리이다.
좀 더 쉽게 설명하면,
| 0 | 1 | 2 | 3 | 4 |
| 3 | 0 | 5 | 6 | 7 |
| 2 | 5 | 0 | 8 | 9 |
| 2 | 3 | 4 | 0 | 10 |
| 8 | 5 | 6 | 1 | 0 |
5개의 정점이 있는 플로이드-워셜 알고리즘이 끝난 후, 이런 5*5 테이블이 만들어졌다고 하자.
저 테이블에서 2번째 행(여기선 1부터 시작한다.)의 3번째 열의 의미는 2번 정점으로부터 3번 정점까지 가는 경로 중 최단 경로의 길이이다.
또, 5번째 행의 2번째 열은 5번 정점으로부터 2번 정점까지 가는 최단 경로의 길이이다.
또한, 자기 자신으로 가는 경우엔 최단 경로의 길이가 0이기 때문에 0이 들어가있다.
이때, 방향 그래프일 경우 최단 경로 테이블의
| 0 | 1 | 2 | 3 | 4 |
| 3 | 0 | 5 | 6 | 7 |
| 2 | 5 | 0 | 8 | 9 |
| 2 | 3 | 4 | 0 | 10 |
| 8 | 5 | 6 | 1 | 0 |
자기 자신으로 가는 경우에 대해 그 왼쪽과 오른쪽이 대칭을 이루지 않을 수 있다.
i번째 정점에서 j번째 정점으로 가는 최단 경로와 j번째 정점에서 i번째 정점으로 가는 최단 경로가 다를 수 있기 때문이다.
그러나 무방향 그래프에서는,
| 0 | 1 | 2 | 3 | 4 |
| 1 | 0 | 5 | 6 | 7 |
| 2 | 5 | 0 | 8 | 9 |
| 3 | 6 | 8 | 0 | 10 |
| 4 | 7 | 9 | 10 | 0 |
위 그림과 같이 자기 자신으로 가는 경우(대각선)에 대해 그 왼쪽과 오른쪽이 대칭을 이룬다.
i번째 정점에서 j번째 정점으로 가는 최단 경로의 길이와 j번째 정점에서 i번째 정점으로 가는 최단 경로가 같기 때문이다.
위의 설명한 내용은 플로이드-워셜의 최종적인 결과이고, 여기에선 동작 과정을 설명한다.
일단 플로이드-워셜을 수행하기 전, 모든 최단 경로 테이블을 특정 INF값(n*(간선의 최대 가중치)로 두는 걸 추천한다.)으로 두고, 연결된 정점들만 그 가중치를 바꿔준다.
ex) i번 노드와 j번 노드가 연결돼 있고, i에서 j로 가는데 가중치 3이 든다. -> 최단 경로 테이블의 i번째 행의 j번째 열을 3으로 둔다.
아까 맨 위에서 설명했듯이, 플로이드-워셜은 3중 for문을 통해 구현할 수 있으며, 가장 바깥 for문을 중간 정점(거쳐가는 정점) -> 두번째 for문을 시작 정점 -> 세번째 for문을 끝 정점으로 지정하고 탐색한다.
이 때, 중간 정점 탐색이라는 말은 시작 정점에서 끝 정점을 현재까지 탐색한 최단 경로로 가는 경우와 현재 중간 정점을 거쳐가는 경우 중 어떤 방법이 더 빠른지 탐색하는 과정이다.
| 0 | INF | 1 | INF | 7 |
| INF | 0 | INF | INF | INF |
| INF | INF | 0 | INF | 2 |
| INF | INF | INF | 0 | INF |
| INF | INF | INF | INF | 0 |
즉, 이 최단 경로 테이블이 있다고 하고, 1번에서 5번 정점으로 가는 최단 경로를 구해보자.
처음엔 1번 정점에서 5번 정점으로 가는 최단 경로가 7로 돼있었지만, 중간 정점이 3, 시작 정점이 1, 끝 정점이 5일 때, 최단 경로가 갱신된다.
한 번 확인해보자.
˚ 1 -> 5 : 가중치 7
˚ 1 -> 3, 3 -> 5 : 가중치 (1+2)=3
위에서 보다시피 가중치가 갱신된다.
최단 경로가 갱신될 때는 그냥 시작 정점으로부터 끝 정점으로 가는 최단 경로를 갱신해주면 된다.(중간 정점은 저장해주지 않아도 된다.).
그리고 시작 정점과 끝 정점이 연결 됐으므로, 다음에 다른 경로를 탐색할 때 시작 정점을 중간 노드로 하고, 끝 정점과 연결된 정점을 구하거나, 끝 정점을 중간 노드로 하고, 시작 정점과 연결된 정점을 구하는 과정을 반복할 수 있다.
이를 N번 반복하면 모든 최단 경로 테이블이 갱신된다.
다음은 방향 그래프에서의 플로이드-와샬 의사 코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1000000007
#define vl vector<vector<int>>
#define vi vector<int>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
int n, m; // n -> 정점의 개수, m -> 간선의 개수
cout<<"정점의 개수 입력(번호는 1부터 시작) : ";
cin>>n;
cout<<"간선의 개수 입력 : ";
cin>>m;
vl table(n+1, vi(n+1));
for(int i=1;i<=n;i++)
fill(table[i].begin()+1, table[i].end(), INF);
while(m--){
int s, e, v; // s -> 시작 정점, e -> 끝 정점, v -> 가중치
cout<<"간선 정보 입력(시작 정점, 끝 정점, 가중치) : ";
cin>>s>>e>>v;
table[s][e]=v;
}
for(int i=1;i<=n;i++){
table[i][i]=0; //자기 자신으로 가는 최단 경로는 0이다.
for(int j=1;j<=n;j++){
if(i==j||table[i][j]==INF) // 시작정점과 중간 정점이 같거나, 연결돼있지 않으면 패스
continue;
for(int k=1;k<=n;k++){
if(k==i||k==j||table[j][k]==INF) //시작 정점과 끝 정점이 같거나, 끝 정점과 중간 정점>이 같거나, 중간 정점과 끝 정점이 연결돼있지 않으면 패스
continue;
table[i][k]=min(table[i][k], table[i][j]+table[j][k]); //중간 정점을 거쳐 가는 거리의 최솟값 갱신
}
}
}
while(1){
cout<<"최단 경로를 알고 싶은 두 정점을 알려주세요. : ";
int s, e;
cin>>s>>e;
if(table[s][e]==INF)
cout<<"두 정점 사이에 길이 없습니다!!\n";
else
cout<<"최단 경로의 길이 : "<<table[s][e]<<'\n';
}
}다음은 아까 예시로 들었던 사례이다.
원래 4였던 거리가 (1+2)=3으로 잘 갱신된 걸 확인할 수 있다.
2. 데이크스트라 알고리즘
데이크스트라 알고리즘 : 한 정점과 모든 정점 사이의 최단 경로를 구할 때 쓰이며, 현존하는 최단 경로 알고리즘 중 가장 빠르다고 알려져 있다.
인공위성 등 경로탐색이 필요한 프로그램에서 이 알고리즘으로 최단 경로를 찾는다.
동작 방식 : 가중치가 가장 작은 간선을 먼저 탐색하며 최단 거리를 갱신해 나간다.
벨만-포드 알고리즘과 데이크스트라 알고리즘은 앞의 플로이드 알고리즘과 달리, 한 정점에서 모든 정점으로의 최단 경로를 반환한다.
즉, 2차원 행렬 형태가 아닌, 1차원 배열 형태의 최단 경로 테이블을 반환한다.
방금 말했듯이 데이크스트라 알고리즘은 1차원 배열 형태의 최단 경로 테이블을 반환한다.
따라서 어떤 시작 정점으로부터 나머지 정점까지 가는 최단 경로가 구해지는데, 한 번 예시를 들어 설명해보자.
| 0 | 3 | 2 | 5 | 1 | 7 | 8 | 2 | 4 |
위 테이블은 1번 정점으로부터 다른 모든 정점까지의 최단 경로이다.
ex) 1번 정점으로 부터 4번 정점까지의 최단 거리 : 4번째 열에 들어있는 값
1번 정점이 시작 정점인 이유는 자기 자신으로 갈 때 필요한 가중치가 0이기 때문이다.
여기서부턴 데이크스트라 알고리즘의 동작 과정을 설명한다.
일단 위애서 설명한 최단 경로 테이블의 모든 인덱스를 INF(절대 나올 수 없는 큰 수)로 채운다.
그 다음 시작 정점의 인덱스를 0으로 채우고 알고리즘을 시작한다.
데이크스트라는 시작 정점부터 시작해, 그와 연결된 모든 정점들을 확인하며 알고리즘을 수행한다.
이렇게 연결된 정점들을 확인할 때에는 가중치가 작은 간선부터 탐색한다.
예를 들어, 1에서 3으로 가는데 그 가중치가 5이고, 1에서 2로 가는데 가중치가 3이면, 1에서 2로 가는 경로를 먼저 탐색하고, 그 다음에 1에서 3으로 가는 경로를 탐색한다.
이렇게 가중치가 작은 간선부터 탐색하면 다음에 다시 이 정점으로 가는 경로를 탐색할 때 현재 경로로 가는 것보다 전에 탐색한 경로로 가는 가중치가 더 작을 확률이 높기 때문에 그 정점으로 가는 가중치를 갱신하고, 다시 그 정점에서 가는 경로를 탐색할 횟수가 줄어든다.
구체적인 작동 방식은,
시작 정점을 인자로 준 재귀 함수를 호출해 그 정점과 연결된 모든 간선을 탐색하고, 거기에서 가장 작은 가중치를 갖는 간선부터 탐색하며 또 그 정점과 연결된 간선을 탐색하는 과정을 반복해 최단 경로를 갱신해 나간다.
한 번 방향 그래프에서의 데이크스트라를 의사 코드로 나타내보자.
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define vi vector<int>
#define vp vector<pair<int, int>>
#define vv vector<vector<pair<int, int>>>
#define pii pair<int, int>
#define INF 1000000007
using namespace std;
vi table; // 최단 경로 테이블
vv tree; // 정점간 연결 정보 저장
bool comp(pii a, pii b){ // 간선의 가중치가 작은 순으로 정렬
if(a.second==b.second)
return a.first<b.first;
return a.second<b.second;
}
void dijkstra(int nd){
for(int i=0;i<tree[nd].size();i++) // 현재 정점과 연결된 모든 정점 탐색 및 배열 저장
if(table[nd]+tree[nd][i].second<table[tree[nd][i].first]){ // 현재 경로로 가는 것이 이전 경로로 가는 것보다 가중치가 작다면
table[tree[nd][i].first]=table[nd]+tree[nd][i].second; // 가중치값 갱신
dijkstra(tree[nd][i].first);
}
}
int main(){
ios_base::sync_with_stdio(0);
int n, m, first; // n -> 정점의 개수, m -> 간선의 개수, first -> 시작 정점
cout<<"정점의 개수 입력(번호는 1부터 시작) : ";
cin>>n;
cout<<"간선의 개수 입력 : ";
cin>>m;
cout<<"시작 정점 입력 : ";
cin>>first;
table.resize(n+1);
tree.resize(n+1);
fill(table.begin(), table.end(), INF); // 시작 정점을 제외한 최단 경로 테이블을 INF로 채움
table[first]=0;
while(m--){
int s, e, v; // s -> 시작 정점, e -> 끝 정점, v -> 간선의 가중치
cout<<"간선의 정보 입력(시작 정점, 끝 정점, 가중치) : ";
cin>>s>>e>>v;
tree[s].push_back(make_pair(e, v));
}
for(int i=1;i<=n;i++)
sort(tree[i].begin(), tree[i].end(), comp); // 가중치가 더 적은 순으로 정렬
dijkstra(first); // 시작 정점부터 경로 탐색 시작
while(1){
int e;
cout<<"시작 정점으로부터의 최단 경로를 알고 싶은 정점 입력 : ";
cin>>e;
if(table[e]==INF) // 두 정점 사이에 경로가 없다면
cout<<"시작 정점과 "<<e<<"번 정점 사이에 경로가 없습니다!\n";
else
cout<<table[e]<<'\n';
}
}위의 dijkstra 재귀함수를 보면 현재 탐색 중인 정점과 연결된 정점 중, 그 정점들을 잇는 간선의 가중치가 더 적은 순으로 정렬된 트리에서 정점을 하나씩 탐색하는 걸 볼 수 있다.
이게 데이크스트라의 작동 원리이며, 작동 원리를 이해했다면 우선순위큐를 이용해 훨씬 더 빠른 데이크스트라를 구현할 수 있다.
우선순위큐는 힙 형태의 자료구조로, 여기서는 간단히 이 자료구조 안에 들어간 원소에서 원하는 값을 빼내는 데 log 시간이 걸린다는 것만 일러두겠다.(여기서는 가중치가 더 작은 값이 필요하니 가장 작은 값을 빼낸다.)
재귀가 아닌 while문으로 구현한 데이크스트라는 현재 정점과 연결된 정점 중에서 가중치가 가장 작은 값을 빼는 것이 아닌, 우선순위큐에 저장된 모든 정점들 중에서 가장 가중치가 작은 값을 빼내는 것이기 때문에 계속 모든 경우에서 가중치가 작은 간선부터 고려해주어 재귀함수보다 비교가 안 될 정도로 빠르다.
여기에 더하면 재귀 함수로 구현한 것보다 while문으로 구현한 코드가 훨씬 빠른 것처럼, 우선순위큐를 이용해 구현한 코드가 재귀함수로 구현한 것보다 더 빠르다.
다음 코드는, 우선순위큐로 구현한 데이크스트라의 의사 코드이다.
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <functional>
#define vi vector<int>
#define vp vector<pair<int, int>>
#define vv vector<vector<pair<int, int>>>
#define pii pair<int, int>
#define INF 1000000007
using namespace std;
vi table; // 최단 경로 테이블
vv tree; // 정점간 연결 정보 저장
void dijkstra(int nd){
priority_queue<pii, vp, greater<pii>> pq; // 우선순위큐 자료구조 선언(더 작은 값을 먼저 뽑아냄)
fill(table.begin(), table.end(), INF); // 최단 경로 테이블 INF로 채우기
table[nd]=0;
pq.push(make_pair(0, nd));
while(!pq.empty()){
int pf=pq.top().second; // pf -> 현재 가중치가 가장 작은 간선의 정점 뽑아내기
pq.pop();
for(int i=0;i<tree[pf].size();i++){
int ncost=table[pf]+tree[pf][i].second; // ncost -> 현재 정점에서 다음 정점으로 갔을 때의 가중치
int nf=tree[pf][i].first; // nf -> 다음 정점
if(ncost<table[nf]){ // 최단 거리 테이블의 다음 정점번째 인덱스에 들어있는 값이 ncost보다 클 때 갱신해줘야됨
table[nf]=ncost; // 가중치값 갱신
pq.push(make_pair(tree[pf][i].second, nf)); //우선순위큐에 가중치 + 다음 정점 넣기
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
int n, m, first; // n -> 정점의 개수, m -> 간선의 개수, first -> 시작 정점
cout<<"정점의 개수 입력(번호는 1부터 시작) : ";
cin>>n;
cout<<"간선의 개수 입력 : ";
cin>>m;
cout<<"시작 정점 입력 : ";
cin>>first;
table.resize(n+1);
tree.resize(n+1);
while(m--){
int s, e, v; // s -> 시작 정점, e -> 끝 정점, v -> 간선의 가중치
cout<<"간선의 정보 입력(시작 정점, 끝 정점, 가중치) : ";
cin>>s>>e>>v;
tree[s].push_back(make_pair(e, v));
}
dijkstra(first); // 시작 정점부터 경로 탐색 시작
while(1){
int e;
cout<<"시작 정점으로부터의 최단 경로를 알고 싶은 정점 입력 : ";
cin>>e;
if(table[e]==INF) // 두 정점 사이에 경로가 없다면
cout<<"시작 정점과 "<<e<<"번 정점 사이에 경로가 없습니다!\n";
else
cout<<table[e]<<'\n';
}
}이런 식으로 훨씬 빠른(O(E + V log V)여기서 E는 간선의 개수, V는 정점의 개수) 안에 동작하는 데이크스트라 알고리즘을 구현할 수 있다.
한편, 이 알고리즘은 간선의 가중치가 음수가 되는 경우가 있을 때 사용할 수 없다. 데이크스트라는 가중치가 작은 간선을 계속 우선순위큐에 넣어가며 탐색하는데, 가중치가 음수가 되는 경로를 재방문할 수 있을 때, 가중치가 무한히 줄어들어 프로그램이 끝나지 않는다.
따라서 이 알고리즘은 음수가 되는 가중치가 없는 상태에서 써야한다.
3. 벨만-포드 알고리즘
벨만-포드 : 시작 정점으로부터 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
간선의 가중치가 음이 될 수 있을 때, 데이크스트라 대신 사용한다.
동작 과정 : 벨만-포드 알고리즘에선 모든 간선을 정점의 개수-1만큼 탐색하며, 최단 경로 테이블을 갱신한다.
따라서 시간 복잡도는 O(VE)이다.(V : 정점의 개수, E : 간선의 개수)
아까 설명한 데이크스트라는 시간복잡도가 O(V log E)인데, 벨만-포드 알고리즘을 사용하는 이유는 뭘까?
바로 간선의 가중치가 음이 있고, 그 음의 가중치 때문에 음의 사이클이 생길 때 이 알고리즘을 사용한다.
음의 사이클 ex)
˚ 1 -> 3 : 가중치 1
˚ 3 -> 5 : 가중치 2
˚ 5 -> 1 : 가중치 -5
이런 식이면 계속 최단 거리가 작아지기 때문에 프로그램이 끝나지 않는다.
벨만-포드 알고리즘은 언제나 모든 간선을 정점의 개수-1만큼 탐색하기 때문에 음의 사이클이 있어 간선의 가중치가 계속 작아지더라도 특정 상한에서 반복문이 끝난다.
벨만-포드 알고리즘은 앞에서도 말했듯이 모든 간선을 정점의 개수-1만큼 탐색한다.
예를 들어,
˚ 3 -> 4 : 가중치 4
˚ 2 -> 3 : 가중치 2
˚ 1 -> 2 : 가중치 1
이런 형태의 정점을 4개 가지고 있는 그래프가 있고, 1번 정점으로부터 4번 정점까지 가는 최단 경로를 알아내야 한다.
일단 시작 정점을 제외한 다른 모든 정점으로 가는 최단 거리를 INF(절대 나올 수 없는 가중치)로 잡고, 시작 정점으로 가는 가중치를 0으로 둔다.
그 다음 각 간선을 확인한다.
˚첫 번째 반복
˚ 3 -> 4로 가는 간선은 아직 시작 정점에서 3까지 가는 경로가 탐색되지 않았기 때문에 갱신을 확인하지 않는다.
˚ 2 -> 3로 가는 간선도 아직 시작 정점에서 2까지 가는 경로가 탐색되지 않았기 때문에 갱신을 확인하지 않는다.
˚ 1 -> 2로 가는 간선에선 최단 경로 테이블의 1번 열에 있는 값이 0이기 때문에 INF가 아니라서 최단 경로 갱신을 확인한다.(어떤 열에 있는 값이 INF라면 아직 시작 정점에서 그 정점으로 가는 경로가 나오지 않았다는 뜻이기 때문에 갱신하면 안 된다.)
가중치 1은 INF보다 작기 때문에 최단 경로를 갱신한다.
즉, 2번 열에 있는 값을 (0(시작 정점에서 1번 정점까지 가는데 드는 가중치)+1(1번 정점에서 2번 정점까지 가는데 드는 가중치))=1로 맞춰준다.
˚두 번째 반복
˚ 3 -> 4로 가는 간선은 아직 시작 정점에서 3까지 가는 경로가 탐색되지 않았기 때문에 갱신을 확인하지 않는다.
˚ 2 -> 3로 가는 간선에선 최단 경로 테이블의 2번 열에 있는 값이 1이기 때문에 INF가 아니라서 최단 경로 갱신을 확인한다.
가중치 (1(시작정점에서 2번 정점까지 가는데 드는 가중치)+2(2번 정점에서 3번 정점까지 가는데 드는 가중치))=3이 INF보다 작기 때문에 최단 경로를 갱신한다.(즉, 3번 열에 있는 값을 3으로 바꿔준다.)
˚ 1 -> 2로 가는 간선에선 1의 가중치가 INF가 아니기 때문에 갱신을 시도하려 했으나, 2로 가는 가중치는 이미 1로, 갱신했을 때보다 크지 않기 때문에 가중치를 갱신하지 않는다.
˚세 번째 반복
˚ 3 -> 4로 가는 간선에선 최단 경로 테이블의 3번 열에 있는 값이 3이기 때문에 INF가 아니라서 최단 경로 갱신을 확인한다.가중치 (3(시작 정점에서 3번 정점까지 가는데 드는 가중치)+4(3번 정점에서 4번 정점까지 가는데 드는 가중치))=7이 INF보다 작기 때문에 최단 경로를 갱신한다.(즉, 4번 열에 있는 값을 7로 바꾼다.)
˚ 2 -> 3로 가는 간선에선 2의 가중치가 INF가 아니기 때문에 갱신을 시도하려 했으나, 3로 가는 가중치는 이미 3으로, 갱신했을 때보다 크지 않기 때문에 가중치를 갱신하지 않는다.
˚ 1 -> 2로 가는 간선에선 1의 가중치가 INF가 아니기 때문에 갱신을 시도하려 했으나, 2로 가는 가중치는 이미 1로, 갱신했을 때보다 크지 않기 때문에 가중치를 갱신하지 않는다.
이렇게 간선을 확인하는 과정을 정점의 개수만큼 반복하면 최단 경로가 갱신된다.
정점의 개수만큼만 반복해도 최단 경로가 갱신되는 이유는, 최단 경로이고, 음의 사이클이 존재하지 않는다면 같은 정점을 다시 방문할 일은 없기 때문이다.
즉, 최단 거리는 두 정점이 연결되어있다고 가정하면, 최악의 경우에도 최대 n-2개의 중간 정점으로 연결돼있다.
그럼 이제 음의 사이클을 확인해보자.
아까 진행했던 반복을 한 번 더 진행한다.
즉, 지금은 네 번째 반복이 될 것이다.
만일 이 과정에서 최단 경로가 한 번 더 갱신이 된다면, 그건 이미 최단 경로가 다 구해진 상태에서 더 최단 경로가 나타난다는 뜻이기 때문에 음의 사이클이 발생한다는 뜻이다.
이렇게 음의 사이클을 확인하고 대처할 수 있다.
다음은 무방향 그래프에서의 벨만-포드 알고리즘의 의사 코드이다.
#include <iostream>
#include <vector>
#include <utility>
#include <cstdlib>
#include <algorithm>
#define INF 1000000007
#define vi vector<int>
#define vpi vector<pair<pair<int, int>, int>>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
int n, m, first; // n -> 정점의 개수 m -> 간선의 개수 first -> 시작 정점의 번호
cout<<"정점의 개수 입력(번호는 1부터 시작) : ";
cin>>n;
cout<<"간선의 개수 입력 : ";
cin>>m;
cout<<"시작 정점 입력 : ";
cin>>first;
vi get_min(n+1);
fill(get_min.begin()+1, get_min.end(), INF); // 최단 경로 테이블에 들어있는 모든 값 INF로 채우기
get_min[first]=0; // 최단 경로 테이블의 시작 정점 번째의 값을 0으로 채우기
vpi linked;
while(m--){
int s, e, v;
cout<<"간선의 정보 입력(시작 정점, 끝 정점, 가중치) : ";
cin>>s>>e>>v;
linked.push_back(make_pair(make_pair(s, e), v));
}
for(int i=0;i<n;i++) // 최단 경로 갱신 코드(n번 반복하는 이유는 음의 사이클까지 확인하기 위해서
for(int j=0;j<linked.size();j++){
int start=linked[j].first.first;
int end=linked[j].first.second;
int value=linked[j].second;
if(get_min[start]==INF) // 간선의 역방향쪽 정점의 최단 거리가 INF일 때 패스
continue;
if(i==n-1&&get_min[end]>get_min[start]+value){ //n-1번을 다 반복했는데도 불구하고 최단 경로가 더 갱신되면 음의 사이클이 있는 것으로 간주
cout<<"음의 사이클이 있어 최단 경로를 구할 수 없습니다!!\n";
exit(0);
}
get_min[end]=min(get_min[end], get_min[start]+value);
}
while(1){
int e;
cout<<"시작 정점으로부터의 거리를 알고 싶은 정점의 번호를 입력하세요 : ";
cin>>e;
if(get_min[e]==INF) //최단 경로가 INF라면
cout<<"두 정점 사이에 길이 없습니다!!\n";
else
cout<<"두 정점 사이의 최단 거리 : "<<get_min[e]<<'\n';
}
}
정상적으로 작동하는 걸 확인할 수 있다.
4. 최소 스패닝 트리 알고리즘(with 유니온 파인드 알고리즘)
최소 스패닝 트리 : 모든 정점을 잇는 트리 중에서 그 합이 가장 작은 경우를 찾는 알고리즘이다.
동작 방식 : 두 정점을 잇는 모든 간선을 가중치 순으로 정렬한 후, 가중치가 가장 작은 간선 중에서 사이클이 생기지 않도 록하는 간선을 뽑아내며, 정점의 개수-1개의 간선을 뽑아낸다.
최소 스패닝 트리 알고리즘은 앞의 경로 탐색 알고리즘과 달리, 모든 정점을 한번에 잇는 트리(사이클이 없는) 중에서 그 가중치의 합이 가장 작은 트리를 리턴한다.
여기서부턴 최소 스패닝 트리의 동작 원리에 대해 서술한다.
아주 간단하다.
그냥 모든 간선을 가중치에 대해 오름차순 정렬한 후, 거기에서 뽑았을 때 사이클이 생기지 않는, 가장 작은 가중치를 갖는 간선을 한개씩 뽑아내고, 정점의 개수-1개의 간선을 뽑아낸 후 프로그램을 종료한다.
이렇게 생각하는 건 간단하지만, 사이클 찾는 걸 어떻게 할지 모르겠다.
사이클이 생기면 간접적으로 연결된 정점을 또 연결하기 때문에 제대로 된 "최소" 스패닝 트리를 만들기 위해선 사이클을 아주 짧은 시간에 찾을 수 있는 알고리즘을 알아야 한다.
이 때 쓰는 알고리즘이 바로 유니온 파인드 알고리즘이다.
유니온 파인드는 '분리 집합'이라는 뜻인데, 정점이 분리되어있는지 연결되어있는지 빠른 시간에 안에 찾아낼 수 있기 때문이다.
유니온 파인드에선 1차원 배열로 각 인덱스에 각 정점의 최종 부모 정점의 번호를 저장하고, 두 정점을 잇는 간선을 뽑아낼 때 최종 부모노드가 같으면 이미 연결돼있다는 뜻이므로, 뽑아내지 않는 식으로 구현할 수 있다.
또, 어떤 두 정점을 잇는 간선을 뽑았을 때는, 한 정점의 최종 부모가 다른 한 정점의 최종 부모를 가리키게 하면 달라진 최종 부모를 잘 처리할 수 있다.
다음은 유니온 파인드를 이용한 최소 스패닝 트리 구현이다.
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#define vi vector<int>
#define vp vector<pair<int, pair<int, int>>>
using namespace std;
vi pr;
int find(int a){ // 최종 부모 정점을 찾는 코드
if(pr[a]==a) return a; // 부모가 자기 자신이면 현재 정점을 리턴한다
else return pr[a]=find(pr[a]); // 현재 정점의 최종 부모 정점은 현재 정점의 부모 정점의 최종 부모 정점과 같기 때문에 탐색을 하면서 자신의 최종 부모 정점을 갱신해나간다
}
int main(){
ios_base::sync_with_stdio(0);
int n, m; // n -> 정점의 개수, m -> 간선의 개수
vp links; // 간선을 저장할 배열
cout<<"정점의 개수 입력 : ";
cin>>n;
do{
cout<<"간선의 개수 입력 : ";
cin>>m;
if(m<n-1)
cout<<"간선의 개수가 충분하지 않습니다!\n";
}while(m<n-1); // 최소 스패닝 트리에서 필요한 간선의 개수는 n-1개이므로, 그것보다 적은 수의 간선의 개수가 들어오면 안 된다.
pr.resize(n+1);
for(int i=1;i<=n;i++) // 각 정점의 최종 부모 정점을 자기 자신으로 설정
pr[i]=i;
while(m--){ // 간선 입력 받기
int s, e, v;
cout<<"간선의 정보 입력(시작 정점, 끝 정점, 가중치) : ";
cin>>s>>e>>v;
links.push_back(make_pair(v, make_pair(s, e)));
}
sort(links.begin(), links.end(), less<>()); // 간선을 가중치에 대한 오름차순으로 정렬
int res=0, cnt=0; // res -> 최소 스패닝 트리 가중치의 총 합, cnt -> 현재까지 사용된 간선의 개수
for(int i=0;i<links.size()&&cnt<n-1;i++){
int a=links[i].second.first, b=links[i].second.second;
if(find(a)==find(b)) // 두 정점의 최종 부모 정점이 같다면 -> 이미 연결돼있는 정점이란 뜻이므로 패스
continue;
if(pr[a]>pr[b]) // 노드 번호가 더 작은 쪽에 더 큰 쪽 정점을 병합
pr[pr[a]]=pr[b];
else
pr[pr[b]]=pr[a];
res+=links[i].first;
cnt++;
}
if(cnt<n-1) // 사용한 간선의 개수가 n-1개보다 작으면 최소 스패닝 트리 구성에 실패했다는 뜻임
cout<<"입력하신 간선만으로는 최소 스패닝 트리를 구성할 수 없습니다!\n";
else
cout<<"최소 스패닝 트리의 가중치함 : "<<res<<'\n';
}이런 식으로 최소 스패닝 트리를 구할 수 있다.
참고로 위의 알고리즘은 크루스칼 알고리즘이라 하고, 정점의 개수가 많고 간선의 개수가 적을 때 사용한다.
프림이라는 또 다른 방법이 있는데 이는 그래프 탐색과 많이 유사하며, 크루스칼 알고리즘과 반대되는 최적의 경우에 사용한다.
여기선 프림 알고리즘의 동작 과정을 설명한다.
어차피 모든 정점을 지나긴 해야 하기 때문에 한 정점에서 시작해서 자신과 연결된 가장 가중치가 적게 연결된 정점을 선택하고 현재까지 선택된 정점 중에서 가중치가 가장 적게 연결된 간선의 정점을 선택하고, 또 현재까지 선택된 정점과 연결된 간선 중에서 가중치가 가장 적은 간선의 정점을 선택하고.. 이 과정을 반복하다보면 모든 정점이 한 선으로 연결된 최소 스패닝 트리가 나온다.
이렇게 다양한 최단 경로 알고리즘의 동작 과정과 그 용도를 알아보았고, 이렇게 많은 최단 거리 알고리즘 중에서 적절한 시기에 적절한 알고리즘을 사용하면 그냥 완전 탐색으로 최단 거리를 찾았을 때보다 적게는 몇 배, 많게는 몇 천만배까지 차이가 나기도 한다.