다익스트라(Dijkstra) 알고리즘

다익스트라의 최단경로 알고리즘(Dijkstra Shortest Path Algorithm)

  다익스트라의 최단경로 알고리즘은 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로

  동작원리가 프림 알고리즘(Prim Algorithm)과 흡사하다.

  다익스트라의 최단경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.

  현실에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실에 적합한 알고리즘이다.

 

과정

  그래프의 시작점을 선택하여 트리 T에 포함시킨다.

  T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선중에서 이동거리가 가장 작은 간선을 찾는다.

  해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다.

  모든 노드가 포함될때까지 반복한다.

  이와 같은 그래프가 있고 1에서 시작한다고 하면

  자기자신은 0, 인접노드는 해당 간선값, 인접하지 않은 노드는 무한이다.

  그럼 자기자신을 제외한 노드중에서 가장 거리가 짧은 노드를 먼저 방문하기 때문에 4를 방문하게 된다.

  4에서는 인접노드로 3과 5가 있다.

  3의 경우는 1에서 4를 거쳐 3으로 이동하면 1 + 3의 비용이 소모된다.

  원래의 비용인 5보다 더 작기 때문에 3의 거리비용을 4로 변경해준다.

  5는 무한이었으니 4를 거쳐 이동하는 비용인 2로 변경해준다.

  그럼 이제 2와 5가 같은 최소값을 갖고 있는데 둘중 어디를 먼저가도 상관없다.

  5를 먼저 갔다고 했을 때 5에서는 3과 6이 인접노드이다.

  3의 경우는 원래 거리비용이 4였지만 1->4->5 를 통해 이동하면 3의 비용만이 소모되므로

  3으로 변경해준다.

  6은 무한이었기 때문에 5까지의 거리비용인 2에 6으로 이동하는 거리비용인 2를 더해 4의 거리비용으로

  변경해준다.

  그럼 이제 방문하지 않은 노드중 최소비용을 갖고 있는 2로 이동한다.

  2에서는 인접노드가 4밖에 존재하지 않는다.

  현재 2의 거리비용은 2이고 4로 이동하는 거리비용은 2이므로 총 4를 갖게 되는데 현재 4는 1의 거리비용을

  갖고 있기 때문에 변경하지 않고 그대로 둔다.

  남은 노드인 3, 6중에 3의 거리비용이 더 작으므로 3으로 이동한다.

  3에서는 2와 6이 인접해있고 2로 이동하는 비용을 더하면 6, 6으로 이동하는것은 8의 비용이 소모되는데

  기존 2와 6이 갖고 있는 거리비용이 더 작기 때문에 변경하지 않고 6으로 이동한다.

  그럼 마지막으로 6으로 이동하게 되고 0, 2, 3, 1, 2, 4가 각 노드의 최소 거리비용이 된다.

 

  다익스트라 알고리즘은 각 간선에 대한 정보를 우선순위큐에 담아 처리하는 방식으로 구현할 수 있으며

  O(ElogV)의 시간 복잡도를 갖는다.

 

예제코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define NODE_MAX 20001
#define EDGE_MAX 600001 //양방향 간선이므로 300,000개

typedef struct{ //각 간선의 정보
  int cost;
  int node;
} Edge;

void swap(Edge* a, Edge* b){ //두개의 간선에 대한 정보를 교체
  Edge temp;
  temp.cost = a->cost;
  temp.node = a->node;
  a->cost = b->cost;
  a->node = b->node;
  b->cost = temp.cost;
  b->node = temp.node;
}

typedef struct{
  Edge* heap[EDGE_MAX];
  int count;
} priorityQueue;

void enQueue(priorityQueue* pq, Edge* edge){
  if(pq->count >= EDGE_MAX) return;
  pq->heap[pq->count] = edge;
  int now = pq->count;
  int parent = (pq->count - 1) / 2;
  
  //새 원소를 삽입한 이후에 상향식으로 힙을 구성
  while(now > 0 && pq->heap[now]->cost < pq->heap[parent]->cost){
    swap(pq->heap[now], pq->heap[parent]);
    now = parent;
    parent = (parent - 1) / 2;
  }
  pq->count++;
}

Edge* deQueue(priorityQueue* pq){
  if(pq->count <= 0) return NULL;
  Edge* res = pq->heap[0];
  pq->count--;
  pq->heap[0] = pq->heap[pq->count];
  int now = 0, leftChild = 1, rightChild = 2;
  int target = now;
  
  //새원소를 추출한 이후에 하향식으로 힙을 구성
  while(leftChild < pq->count){
    if(pq->heap[target]->cost > pq->heap[leftChild]->cost) target = leftChild;
    if(pq->heap[target]->cost > pq->heap[rightChild]->cost && rightChild < pq->count) target = rightChild;
    if(target == now) break; //더이상 내려가지 않아도 될 때 종료
    else{
      swap(pq->heap[now], pq->heap[target]);
      now = target;
      leftChild = now * 2 + 1;
      rightChild = now * 2 + 2;
    }
  }
  return res;
}

typedef struct Node{
  Edge* data;
  struct Node* next;
} Node;

Node** adj;
int ans[NODE_MAX]; //특정노드까지의 최단거리값

void addNode(Node** target, int index, Edge* edge){
  if(target[index] == NULL){
    target[index] = (Node*)malloc(sizeof(Node));
    target[index]->data = edge;
    target[index]->next = NULL;
  }
  else {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = edge;
    node->next = target[index];
    target[index] = node;
  }
}

int main(void){
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  adj = (Node**)malloc(sizeof(Node*) * (n + 1)); //노드의 개수만큼 연결리스트 생성
  
  for(int i = 1; i <= n; i++){ //연결리스트 초기화
    adj[i] = NULL;
    ans[i] = INT_MAX; //모든 노드로 갈수있는 비용은 전부 무한이라고 초기화
  }
  priorityQueue* pq;
  pq = (priorityQueue*)malloc(sizeof(priorityQueue));
  pq->count = 0;
  
  for(int i = 0; i < m; i++){ //방향그래프 형식
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c); //a에서 b까지 가는 거리가 C이다
    Edge* edge = (Edge*)mallco(sizeof(Edge));
    edge->node = b;
    edge->cost = c;
    addNode(adj, a, edge); //연결리스트에 추가해서 a번째 인덱스에 원소 b를 추가하는 형태
  }
  //간선에 대한 정보들이 우선순위 큐에 들어간것
  
  
  //다익스트라 알고리즘 시작
  ans[k] = 0; //출발하고자하는 노드의 비용 설정 시작노드는 비용이 0
  Edge* start = (Edge*)malloc(sizeof(Edge));
  start->cost = 0; start->node = k; enQueue(pq, start);//출발노드에 대한 간선정보를 큐에 넣는다
  while(1){ //모든 간선에 대한 정보를 큐에 담았다가 꺼내면서 처리
    Edge* now = deQueue(pq); //큐에 담겨있는 원소 추출
    if(now == NULL) break;
    int curNode = now->node;
    int curCost = now->cost;
    if(ans[curNode] < curCost) continue;
    //최단경로이기 때문에 현재 보고있는 비용이 테이블에 담은 비용보다 크다면 무시하고 넘어간다
    
    Node* cur = adj[curNode]; //그렇지 않다면 새롭게 특정한 노드가 추가되었다는 것이므로
    while(cur != NULL){ //그 노드에 연결되어있는 모든 노드를 확인한다
      Edge* temp = cur->data;
      temp->cost += curCost; //확인했을 때 해당노드로 건너가는 비용을 cost에 담는다
      
      if(temp->cost < ans[temp->node]){
        //현재 테이블에 담겨있던 해당 노드에 대한 최단거리 비용이
        //현재 보고있는 비용보다 크다면 더 작은값으로 갱신
        ans[temp->node] = temp->cost;
        enQueue(pq, temp);
        //테이블 갱신
        //이후에 다시 해당 간선을 우선순위 큐에 담아서 다시한번
        //간선데이터를 확인하도록 한다.
      }
      cur = cur->next;
    }
    //내부 while End
    //모든 간선을 확인해서 더 적은비용으로 갱신하겠다는 것.
    //이것이 다익스트라 알고리즘의 핵심이다.
  }
  
  for(int i = 1; i <= n; i++){
    if(ans[i] == INT_MAX) printf("INF\n");
    //무한이라는 값을 갖고 있으면 해당 노드로는 도착할 수 없기 때문에 INF출력
    else printf("%d\n", ans[i]);
  }
  system("pause");
}

  3 3 1

  1 2 10

  1 3 30

  2 3 5

  이렇게 입력하면

  0

  10

  15

  이렇게 출력된다.

  입력된 값을 보면

  노드수  간선수  출발노드

  1에서 2까지 비용 10

  1에서 3까지 비용 30

  2에서 3까지 비용 5

  이렇게 입력된것이고

  그럼 1의 비용은 시작점이니까   0

  2는 10의 비용을 갖고 있으니    10

  3은 1에서 3으로 가는 비용(30)과

  1에서 2를 거쳐 가는 비용(15)

  두가지가 있으니 더 작은값인    15

  이렇게 처리된다.

 

 

레퍼런스

● 패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직

● m.blog.naver.com/ndb796/221234424646