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

다익스트라(Dijkstra)란?

다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘 입니다. 즉 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려준다. -> ex) 인공위성

다만 음의 간선을 포함할 수 없으며, 현실에도 음의 간선은 존재하지 않기에 현실에서 사용하기 적합한 알고리즘 입니다.

 

예제1)

"1부터 다른 노드로 가는 최단 경로를 구해보자"

1. 1의 연결 노드는 2, 3, 4이며 각각 3, 6, 7로 산정할 수 있다.

0

3

6

7

위 그래프는 1, 2, 3, 4 다른 노드로 가는 비용을 정리한 것 

 

2. 그럼 비용이 가장 저렴한 2번 노드로 가서 산정을 해본다. 이때 무한은 접근 할수가 없는 노드이다.

3

0

1

무한

이렇게 되면 3번 노드는 3 + 1로 이전에 있었던 6비용보다 4라는 비용으로 접근 할 수 있게 된다.

다시말해 다익스트라 알고리즘은 "현재까지 알고 있던 경로를 계속 갱신" 해서 최단 경로를 구하는 것이 다익스트라 알고리즘이라고 할 수 있다.

 

구체적인 작동과정

1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 설정
3. 방문하지 않은 노드중에서 가장 비용이 낮은 노드를 방문
4. 해당 노드를 거쳐서 가서 특정 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 과정에서 3, 4번을 반복작업. 

 

예제2)

이러한 그래프는 컴퓨터의 2차원 배열로 처리되기에 바로 아래와 같이 각 노드마다 비용을 그래프로 산정해줍니다.

컬럼이 뜯하는 것은 왼쪽에서 차례대로 1, 2, 3, 4, 5, 6 노드의 비용을 산정.

로우는 기준 노드를 구분하기 위함입니다. (비용 == 0 ? 기준노드 : 노드)

0	2	5	1	MAX	MAX
2	0	3	2	MAX	MAX
5	3	0	3	1	5
1	2	3	0	1	MAX
MAX	MAX	5	1	0	2
MAX	MAX	5	MAX	2	0

그러면 순서대로 진행해보겠다.

 

"빨간 글자 = 순회한 노드."

"검은 글자 = 비용 갱신"

 

1. 1번 노드

가장 낮은 비용인 4번 노드로 이동

0

2

5

1

MAX

MAX

 

2. 4번 노드

가장 낮은 비용인 4번 노드로 이동 이때 3번 노드를 (1 + 3)으로 4로 단축, 5번 노드 조회 가능 그리고 가장 적은 노드인 2번 노드로 이동

0

2

4

1

2

MAX

 

3. 2번 노드

2노드를 거치더라도 갱신되는 것이 없음 그래서 배열은 유지하며 가장 비용이 적은 5노드로 이동합니다.

0

2

4

1

2

MAX

 

4. 5번 노드

이때 5를 거쳐서 3노드를 순회하는 것이 (1 + 1 + 1)3으로 단축, 6번 노드 조회 가능. 이때 가장 비용이 적은 3번 노드로 이동.

0

2

3

1

2

4

 

5. 3번 노드

비용 갱신이 일어나지 않는다. 

0

2

3

1

2

4

 

5. 6번 노드

비용 갱신이 일어나지 않는다.

0

2

3

1

2

4

 

즉 최종결과는 이렇게 된다. 

 

그럼 이것을 알고리즘으로 구현해보자.

구현에 앞서 위에서 말한 작동과정에 대해서 이해하고 빗대어서 생각하면 훨신 쉽게 이해할 수 있었다.

 

#include <iostream>
using namespace std;

int num = 6;
int MAX = 100000000;

int a[6][6] = {
  {0, 2, 5, 1, MAX, MAX},
  {2, 0, 3, 2, MAX, MAX},
  {5, 3, 0, 3, 1, 5},
  {1, 2, 3, 0, 1, MAX},
  {MAX, MAX, 1, 1, 0, 2},
  {MAX, MAX, 5, MAX, 2, 0},
};

bool v[6]; //방문한 노드 체크
int line[6]; //비용

int getSallIndex() {
  int min = MAX;
  int index = 0;
  for(int i = 0; i < num; i++) {
    if(line[i] < min && !v[i]) { //방문하지 않은 노드의 낮은 비용체크
      min = line[i];
      index = i;
    }
  }
  return index;
}

void dijkstra(int start) {
  //비용확인
  for(int i = 0; i < num; i++) {
    line[i] = a[start][i];
  }
  //1. 첫 노드 방문 체크
  v[start] = true;

  //num - 2를 하는 이유: 첫번째와 마지막 노드를 제외를 생각해서 시간 단축
  for(int i = 0; i < num - 2; i++) { 
    int current = getSallIndex(); // 가장 비용이 저렴한 노드 추출
    v[current] = true; //노드 방문 체크
    for(int j = 0; j < 6; j++) {
      if(!v[j]) { //방문이 안된 노드 체크
        //t. a[current][j] = 선택한 노드에서 산정된 방문할 수 있는 노드의 비용
        //선택한 노드의 비용과 t의 합을 산정해 기존의 비용과 비교
        if(line[current] + a[current][j] < line[j]) {
          //비교후 낮은 비용의 값을 선정
          line[j] = line[current] + a[current][j];
        }
      }
    }
  }
}

int main() {
  dijkstra(0);
  for(int i = 0; i < num; i++) {
    cout << line[i];
  }
}

이렇게 해서 

0 2 3 1 2 4로 비용갱신이 되어 최단경로를 찾은 것을 확인할 수 있다.

 

 

 

출처: https://www.youtube.com/watch?v=611B-9zk2o4