다익스트라 알고리즘
다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘으로 하나의 최단 거리를 구할 때 이전까지 구했던 정보를 그대로 사용하다. 음의 간선은 존재하지 않기 때문에 적용하기 적합하다. 다익스트라 알고리즘 예시로는 내비게이션, 지하철 노선 검색 등이 있다.
구하는 방법
- 출발 노드를 설정해준다.
- 출발 노드를 기준으로 최소비용의 값을 저장해준다.
- 출발 노드를 제외한 나머지 노드 중 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
- 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 계속해서 갱신해준다
3~4번을 반복하다보면 최단 경로를 구할 수 있다.
같이 구해봅시다!
저는 출발 노드를 A로 설정했습니다! 옆에 있는 표는 최소 비용의 값을 담은 표입니다.
왼쪽서부터 A-E의 최소비용을 담았습니다. A 노드를 기준으로 최소비용의 값을 담아줍니다.
A 노드를 제외한 B-E 노드 중 가장 비용이 적은 B 노드를 선택해줍니다. B 노드를 거쳐 가는 비용이 A 노드에서 가는 비용보다 적다면 갱신시켜줍니다. D 노드는 B 노드를 거쳐 가는 것이 더 비용이 적으니 갱신 시켜줍니다. 이때 C노드에서 가는 경로가 더 저렴할 수 있으니 확정 시킬 수 없어요
B 노드 다음 비용이 적은 C 노드를 선택하여 B 노드와 같이 최소 비용을 갱신하여 줍니다. 이때 D 노드로 가는 모든 경우의 수를 살펴봤으니 최소 비용이 4라고 확신할 수 있습니다.
D 노드를 선택합니다. 이제 드디어 E 노드로 갈 수 있습니다. 최소 비용을 5로 갱신시켜줍니다. 이때 E 노드로 갈 수 있는 방법은 D 노드를 거쳐서 가는 방법 하나이기 때문에 최소 비용이 5인 것을 확신할 수 있습니다.
이렇게 완성된 최소비용은 0, 2, 3, 4, 5 입니다!
코드로 알아봐요
#include <stdio.h>
int number = 5;
int INF = 100000;
int a[5][5] = {
{0,2,3,5,INF},
{2,0,INF,2,INF},
{3,INF,0,2,INF},
{5,2,2,0,1},
{INF,INF,INF,1,0}
};
bool v[5];
int d[5];
int getSmallIndex() {
int min = INF;
int index = 0;
for (int i =0; i <number; i++) {
if(d[i] < min && !v[i]) {
min = d[i];
index = i;
}
}
return index;
}
void dijkstra(int start) {
for(int i =0; i <number; i++) {
d[i] = a[start][i];
}
v[start] = true;
for(int i =0; i <number -2; i++) {
int current = getSmallIndex();
v[current] = true;
for(int j =0; j < 5; j++) {
if(!v[j]){
if(d[current]+a[current][j] < d[j]) {
d[j] = d[current]+a[current][j];
}
}
}
}
}
int main(void) {
dijkstra(0);
for(int i=0; i<number; i++) {
printf("%d",d[i]);
}
}C언어로 작성한 코드입니다. 이 코드는 선형구조로 간단하게 코드를 작성할 때 사용된다고 합니다. 실제 다익스트라 알고리즘은 힙(우선순위 큐)를 이용합니다. 밑에 코드를 첨부하겠습니다!
#include<iostream>
#include<vector>
#include<queue>
#define INF 1e9
using namespace std;
int main()
{
int V,E;
scanf("%d %d", &V ,&E);
int start;
scanf("%d",&start);
vector<pair<int,int> > arr[V+1];
for(int i=0;i<E;i++){
int from,to,val;
scanf("%d %d %d", &from , &to,&val);
arr[from].push_back({to,val});
}
int dist[V+1];
fill(dist,dist+V+1,INF);
priority_queue<pair<int,int> > qu;
qu.push({0,start});
dist[start]=0;
while(!qu.empty()){
int cost=-qu.top().first;
int here=qu.top().second;
qu.pop();
for(int i=0; i<arr[here].size(); i++){
int next=arr[here][i].first;
int nextcost=arr[here][i].second;
if(dist[next] > dist[here] + nextcost){
dist[next]=dist[here]+nextcost;
qu.push({-dist[next],next});
}
}
}
for(int i=1;i<=V;i++){
printf("%d\n", dist[i]);
}
> 힙을 이용한 코드는 bbo0ong님 블로그 참고했습니다 @.@
