다익스트라 알고리즘은 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 사용한다. 주로 네트워크 경로 설계에 많이 적용된다.
- (ex) OSPF(Open Shortest Path First)라는 IP 망에서의 라우팅 프로토콜.
간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 너비우선탐색(BFS)을 기본으로 한다. 이때 가중치는 음수값을 갖지 않는다.
다익스트라 알고리즘은 각각의 정점에 대해서 정점 s에서 정점 v까지의 최단 거리를 d[v]에 저장하면서 탐색한다. 알고리즘 시작 시에 d[s] = 0이고, s가 아닌 다른 모든 정점에 대해서는 d[v] = ∞ 로 놓아 다른 정점에 대해서는 아직 최단 경로를 모른다는 것을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
다익스트라 알고리즘은 다음과 같다. G[A][B]는 A와 B 사이의 거리라고 하자.
- 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF(자료형의 최대값)를 채워 넣는다.
- 현재 노드 A에 출발 노드를 저장한다.
- A로부터 갈 수 있는 임의의 노드 B에 대해,
d[A]+G[A][B]와 d[B]의 값을 비교한다. - 만약
d[A]+G[A][B]가 더 짧다면, d[B]의 값을 이 값으로 갱신시킨다. (edge relaxtion) - 모든 이웃 노드 B에 대해 이 작업을 수행한다.
- A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
- "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
- 모든 노드를 순회해 거리가 제일 짧은 노드를 찾아야한다. 이때 우선순위큐를 활용하면 이 비용을 줄일 수 있다.
- 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.
도착 노드에 저장된 값이 A로부터의 최단거리이다. 만약 도착노드의 값이 INF라면, 중간에 경로가 끊긴 것을 의미한다.
기존의 d(z)가 75였는데 탐색 과정에서 d(u)+e = 60으로 길이가 더 짧을 때, 노드와 엣지의 정보를 업데이트 해주는 것을 말한다.
#include <stdio.h>
#include <limits.h> //INT_MAX
#define V 9
typedef enum { false, true } bool;
// 최단 거리를 찾는 함수
int min_distance(int dist[], bool visited[])
{
// 자료형의 최대값으로 min값 설정
int min = INT_MAX, min_index=0;
for (int v = 0; v < V; v++){
//visited[v]가 false이면서 dist[v]가 최소값보다 적은 경우
if (visited[v] == false && dist[v] <= min){
min = dist[v];
min_index = v;
}
}
return min_index;
}
void print_path(int parent[], int j){
if (parent[j] == - 1)
return;
print_path(parent, parent[j]);
printf("%d ", j);
}
// dist 배열을 출력해주는 함수
void print_distance(int dist[], int n, int parent[])
{
int src =0;
printf("Vertex\t시작 정점으로부터 거리\t경로\n");
for (int i = 0; i < V; i++){
printf("\n%d -> %d \t\t %d\t\t%d ",
src, i, dist[i], src);
print_path(parent, i);
}
}
// 다익스트라 함수
void dijkstra(int graph[V][V], int src)
{
// dist배열은 최단거리를 저장하는 배열이다. 즉, 결과값
// src에서 정점 i까지 가는 거리
int dist[V];
bool visited[V]; //방문했는지 기록하는 배열
int parent[V]; // 부모 노드를 기억할 배열
// dist배열은 자료형의 최대값, visited배열은 false 로 초기화
parent[0] = -1;
for (int i = 0; i < V; i++){
dist[i] = INT_MAX;
visited[i] = false;
}
// 시작점(src)에서 자기자신의 거리는 0이다.
dist[src] = 0;
// 모든 정점에서 최단거리 찾기
for (int count = 0; count < V-1; count++){
int u = min_distance(dist, visited); // 최소거리의 정점을 저장한다. u는 count가 0일때 src와 같다.
visited[u] = true; //방문했음을 표시한다.
// 값을 update해준다.
for (int v = 0; v < V; v++){
// visited이 false이면서, u->v로의 엣지가 있고
// 엣지를 더한 값이 현재 distance보다 작은 경우
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v]){
parent[v] = u;
dist[v] = dist[u] + graph[u][v];
}
}
}
// 시작점으로 부터 각 정점의 최단거리 출력
print_distance(dist, V,parent);
}
int main()
{
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{5, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{0, 12, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}최소힙(minheap)은 우선순위큐로 아직 포함되지 않은 정점으로 부터 최소 거리 정점을 가져온다.
- 크기 V(그래프 정점 수)의 최소 힙을 생성 ( 정점 번호, 정점의 거리 값 포함 )
- src를 시작 루트로 하여 최소힙을 초기화한다. (src->src의 거리는 0, 나머지는 INF)
- 최소힙이 빌때까지 반복해서 수행한다.
- 최소 거리값 정점을 추출(u)한다.
- 추출된 정점(u)의 모든 인접한 정점(v)에 대해서 v가 최소힙에 있는지 확인한다. 최소 힙에 있고, 거리값이 u+v의 가중치보다 작다면 distance를 업데이트한다.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct node{
int dest; //목적노드
int weight; //가중치
struct node * next;
} Node;
typedef struct list{
Node * head;
}List;
typedef struct graph{
int V;
List * array;
}Graph;
Node * new_node(int dest, int weight){
Node * new = (Node*)malloc(sizeof(Node));
new->dest=dest;
new->weight=weight;
new->next=NULL;
return new;
}
Graph * create_graph(int V){
Graph * g = (Graph*)malloc(sizeof(Graph));
g->V = V;
g->array = (List*)malloc(V*sizeof(List));
for(int i=0;i<V;i++){
g->array[i].head=NULL;
}
return g;
}
void add_edge(Graph *g,int src, int dest, int weight){
Node * new = new_node(dest, weight);
new->next=g->array[src].head;
g->array[src].head=new;
new=new_node(src, weight);
new->next = g->array[dest].head;
g->array[dest].head = new;
}
typedef struct hnode{
int v;
int dis;
}HNode;
typedef struct heap{
int size;
int capacity;
int *pos; //decrease key()에 필요하다.
HNode **array;
}Heap;
HNode * new_hnode(int v, int dis){
HNode * new = (HNode*)malloc(sizeof(HNode));
new->v=v;
new->dis=dis;
return new;
}
Heap * create_heap(int capacity){
Heap * heap = (Heap*)malloc(sizeof(Heap));
heap->pos=(int*)malloc(capacity*sizeof(int));
heap->size=0;
heap->capacity=capacity;
heap->array=(HNode**)malloc(capacity*sizeof(HNode*));
return heap;
}
void swap_node(HNode ** a, HNode **b){
HNode * tmp =*a;
*a=*b;
*b=tmp;
}
void heapify(Heap* heap,int i){
int min,left,right;
min=i;
left = i*2+1;
right = i*2+2;
if(left < heap->size && (heap->array[left]->dis < heap->array[min]->dis))min=left;
if(right<heap->size && heap->array[right]->dis<heap->array[min]->dis)min=right;
if(min!=i){
HNode * smallest = heap->array[min];
HNode * inode = heap->array[i];
heap->pos[smallest->v]=i;
heap->pos[inode->v]=min;
swap_node(&heap->array[min], &heap->array[i]);
heapify(heap,min);
}
}
int is_empty(Heap * h){
return h->size==0;
}
HNode * delete(Heap * h){
if(is_empty(h))return NULL;
HNode * root = h->array[0];
HNode * last = h->array[h->size - 1];
h->array[0]=last;
h->pos[root->v]=h->size-1;
h->pos[last->v]=0;
--h->size;
heapify(h, 0);
return root;
}
void decrease_key(Heap * h, int v, int dis){
// heap array의 정점 v에 대한 index
int i = h->pos[v];
h->array[i]->dis = dis; //distance update
while(i && ( h->array[i]->dis < h->array[(i-1)/2]->dis)){
h->pos[h->array[i]->v] = (i-1)/2;
h->pos[h->array[(i-1)/2]->v] = i;
swap_node(&h->array[i], &h->array[(i-1)/2]);
i=(i-1)/2;
}
}
int is_min(Heap * h, int v){
if(h->pos[v] < h->size) return 1;
else return 0;
}
void print_array(int dis[],int n){
printf("정점\t\t시작노드로부터거리\n");
for(int i=0;i<n;i++)
printf("%d\t\t\t%d\n",i,dis[i]);
}
void dijkstra(Graph * g,int src){
int V= g->V;
int dis[V];
Heap * heap = create_heap(V);
for(int i=0;i<V;i++){
dis[i]=INT_MAX;
heap->array[i]=new_hnode(i, dis[i]);
heap->pos[i]=i;
}
// 출발점의 거리를 0으로 만듦
heap->array[src]=new_hnode(src, dis[src]);
heap->pos[src]=src;
dis[src]=0;
decrease_key(heap,src,dis[src]);
heap->size=V;
while(!is_empty(heap)){
HNode * min = delete(heap);
int u = min->v;
Node * trav = g->array[u].head;
while(trav!=NULL){
int v = trav->dest;
if(is_min(heap, v)&&dis[u]!=INT_MAX && trav->weight+dis[u]<dis[v]){
dis[v] = dis[u] + trav->weight;
decrease_key(heap,v,dis[v]);
}
trav=trav->next;
}
}
print_array(dis, V);
}
int main(){
int V = 9;
Graph * graph = create_graph(V);
add_edge(graph, 0, 1, 4);
add_edge(graph, 0, 7, 8);
add_edge(graph, 1, 2, 8);
add_edge(graph, 1, 7, 11);
add_edge(graph, 2, 3, 7);
add_edge(graph, 2, 8, 2);
add_edge(graph, 2, 5, 4);
add_edge(graph, 3, 4, 9);
add_edge(graph, 3, 5, 14);
add_edge(graph, 4, 5, 10);
add_edge(graph, 5, 6, 2);
add_edge(graph, 6, 7, 1);
add_edge(graph, 6, 8, 6);
add_edge(graph, 7, 8, 7);
dijkstra(graph, 0);
return 0;
}
- 가중치가 음수인 경우 처리할 수 없다.
- 출발점으로부터 거리가 가까우면서 동시에 도착점의 방향과 무관한 점들의 최단 경로를 먼저 찾는 헛수고를 하는 경우가 있다. 출발점이 a이고 도착점이 d일 때, 다익스트라 알고리즘은 도착점과 무관한 방향에 있는 점 e, f, g, h, i 모두의 최단 경로를 찾은 후에서야 도착점 d를 향해 최단 경로 찾기를 수행한다.