다익스트라 알고리즘 이란?

1. 다익스트라 알고리즘 이란?

그래프에서 어떤 한 지점(시작점)에서 다른 모든 지점까지의 최단 거리(가장 짧은 거리)를 구하는 알고리즘입니다. 다익스트라 네덜란드의 컴퓨터 공학자가 만든 알고리즘 입니다.

2. 다익스트라 알고리즘 이용

가능한 적은 비용으로 가장 빠르게 해답에 도달 하는 경로를 찾아내는 대부분의 문제에 응용됩니다.

특히 네비게이션, 운송비 계산 등에 사용됩니다.

 

3. 다익스트라 알고리즘 순서

(1) 시작점은 0, 나머지 노드는 거리 무한대로 설정합니다.

[1] → 0      ← 시작점
[2] → ∞
[3] → ∞
[4] → ∞

 

(2) 갈수 있는 곳에 거리를 입력 합니다.

[1] → 0
[2] → 4  (1 → 2)
[3] → 4  (1 → 3)
[4] → ∞

 

(3) 갈 수 있는 마을 하나를 정하고 (2부터), 그 마을이 연결된 길이를 더해 봅니다.

[1] → 0
[2] → 2
[3] → 5  / 3+5 (2->3)
[4] → 10 (2 -> 4)

 

(4) 이때 3번을 보면, 1->3 은 5의 시간이 걸리고, 1->2->3 를 한다면, 3+5 의 시간이 걸립니다. 그러면 당연히 숫자가 적은 쪽이 유리 하기 때문에 8로 업데이트 하지 않고 5 그대로 3번 노드에 적으면 됩니다.

[1] → 0
[2] → 2
[3] → 5  
[4] → 10 (2 -> 4)

 

(5) 반대로 새로운 길을 찾았을때 그 값이 기존 값보다 작다면, 그 길을 선택하는게 유리하기에 그길로 값을 바꾸면 됩니다.

 

(6) 이, 규칙을 반복하여 모든 노드를 한바퀴 돌았다면 알고리즘은 끝이납니다. 모든 노드를 돌았다는 것을 체크하기 위해서 bool 형을 사용해 주시면 됩니다.

 

(7) 마지막으로  완성된 객체에는 출발지로 부터 각 노드까지의 최소 길이가 저장 되어 있게 됩니다. 

[1] → 0
[2] → 2 
[3] → 5  
[4] → 8 

이렇게 결과가 나왔다면 4번 노드까지의 최소 거리는 8이 됩니다.