최단 경로 알고리즘에 대해 공부를 하며, 최단경로를 찾는 문제에서 다익스트라 알고리즘이 많이 사용된다는 것을 알았다.
그래서 공부해본 다익스트라 알고리즘..
다익스트라 최단 경로 알고리즘이란?
- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산해주는 알고리즘
- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.
->why?
왜 다익스트라 최단 경로 알고리즘을 사용하려면 음의 간선이 있으면 안되는 걸까?가중치의 합이 음수인 사이클의 발생 가능성 때문이다.
위 그래프에서, 시작점을 A라 설정한다면 A에서 D까지 가는 최단경로를 생각해보자.
A-B-C-D로 갈 경우 거리는 60이 된다.
그러나, 간선 CA의 가중치가 음수인 것을 이용하면 다음과 같은 경로가 나올 수 있다.
A-B-C-A-B-C-D
위와 같이 사이클을 한번 지나게 된다면?
기존 거리 60의 경로보다 작은 10이 된다.
사이클을 한번 더 돈다면,(A-B-C-A-B-C-A-B-C-D) -40이 된다.
가중치의 합이 음수인 사이클이 발생한다면, 최단 경로가 음의 무한대로 발산하게 된다.
이렇듯, 음수 간선이 존재하면 음수 사이클이 존재할 가능성이 있기 때문에, 다익스트라 외에 다른 알고리즘을 사용하는 것이 타당하다.
->ex) 벨만-포드 알고리즘
다시 돌아와 다익스트라 최단 경로 알고리즘을 보자면,
- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.
* 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문입니다.
다익스트라 최단 경로 알고리즘의 동작과정
- 출발 노드를 설정한다
- 최단 거리 테이블을 초기화(모든 노그까지 가기 위한 것은 무제한으로 초기화, 자기 자신에 대한 노드는 0으로 초기화 한다.)
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
->이것으로 인해 그리디 알고리즘임을 알 수 있다.
->특정 노드까지 가는 거리에 대해 최단거리임을 확신가능하다. - 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3번과 4번을 반복한다.
다익스트라 알고리즘의 특징
- 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
- 단계를 거치며 한 번 정리된 노드의 최단거리는 고정되어 더 이상 바뀌지 않음
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾게 됨
- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지 최단거리 정보가 저장됨
다익스트라 알고리즘의 간단한 구현방법
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 방문한 적이 있는지 체크하는 목적의 배열 만들기
bool visited[100001];
// 최단 거리 테이블 만들기
int d[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getSmallestNode() {
int min_value = INF;
int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
void dijkstra(int start) {
// 시작 노드에 대해서 초기화
d[start] = 0;
visited[start] = true;
for (int j = 0; j < graph[start].size(); j++) {
d[graph[start][j].first] = graph[start][j].second;
}
// 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for (int i = 0; i < n - 1; i++) {
// 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
int now = getSmallestNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드를 확인
for (int j = 0; j < graph[now].size(); j++) {
int cost = d[now] + graph[now][j].second;
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][j].first]) {
d[graph[now][j].first] = cost;
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({b, c});
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill_n(d, 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}->위처럼 구현할 경우 시간복잡도는 O(v^2)가 됨
->만약 노드의 수가 10,000개를 넘어가는경우...?
->이렇게 노드의 수가 많아진다면 우선순위 큐 자료구조를 사용하는 것이 시간복잡도를 줄일 수 있다.
우선순위 큐를 사용한 다익스트라 알고리즘 구현
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
int n,m,start;
//각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
//다익스트라는 간선의 가중치가 양수인 경우만 가능
vector<pair<int, int>>graph[100001];
int d[100001];
void dijkstar(int start){
priority_queue<pair<int, int>>pq;
//시작 노드로 가기 위한 최단 경로는 0으로 설정 후, 큐에 삽입
pq.push({0,start});
d[start]=0;
while(!pq.empty()){
int dist=-pq.top().first;//현재 노드까지 비용
int now=pq.top().second;//현재 노드
pq.pop();
//이미 처리된 적 있는 노드라면 무시
if(d[now]<dist) continue;
//현재 노드와 연결된 다른 인접 노드들 확인
for(int i=0;i<graph[now].size();i++){
int cost=dist+graph[now][i].second;
if(cost<d[graph[now][i].first]){
d[graph[now][i].first]=cost;
pq.push({-cost,graph[now][i].first});
}
}
}
}
int main(){
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
cin>>n>>m>>start;
//모든 간선 정보 입력
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
//a번 노드에서 b번 노드로 가는 비용이 c
graph[a].push_back({b,c});
}
//최단 거리 테이블을 모두 무한으로 초기화
fill(d, d+100001, INF);
//모든 노드로 가기 위한 최단 거리를 출력
for(int i=1;i<=n;i++){
//도달할 수 없는 경우 , 무한이라 출력
if(d[i]==INF){
cout<<"INFINITY"<<"\n";
}
else{
cout<<d[i]<<"\n";
}
}
return 0;
}
위처럼 구현할 경우 시간 복잡도는 O(ElogV)가 된다.
