반응형


다익스트라(dijkstra)란?


그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용할 수 있다.

그래프 공부 시, 아주 중요한 알고리즘이며, 

이 알고리즘 및 벨만포드 알고리즘 (The Bellman_Ford Algorithm) 그리고 

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) 이 3가지 알고리즘을 통해 최단 경로를 구할 수 있다.


이러한 세가지 알고리즘은 각각 정점과 간선의 개수가 어떻게 구성되냐에 따라 시간 복잡도의 차이가 있기에,


각 상황에 맞는 알고리즘을 이용하면 된다.


우선 이번 게시물에서는 다익스트라에 대해 알아 보도록 한다.



우선 다익스트라 알고리즘에 대한 전제 조건은 다음과 같다.


1. 시작 노드 - 시작 노드까지 거리는 0이다.

2. 다른 노드를 통해서 이 노드를 방문할 때는, 모든 간선의 가중치가 양이므로 중복 방문을 하면 무조건 거리가 더 길어진다.

(즉 0에서 1로 가는 길이가 2인데 0에서 1로 1에서 0으로 가면 4가 되니 이러한 방식은 거리가 더 길어지게만 한다.)



다음은 다익스트라 알고리즘의 시간 복잡도 분석이다.







다익스트라는 그림을 통해 확인해 보는것이 글보다 더 쉽다.





위의 사진 처럼 그래프가 형성되어 있다고 가정하자.


그래프는 0번 노드부터 4번 노드까지 총 5개의 노드가 있고,


간선은 총 10개로 구성되어 있는 무방향 그래프이다.


그리고 현재 0번 노드에서 n번 노드로 갈때의 최단 거리는 아직 아무것도 모르니 


최단 거리를 확인하는 배열에서 모두 무한대로 설정해둔다.


0번 노드에서 2번 노드로 갈때의 최단 거리에 대해 구해보자.




0번에서 0번 노드로 가는 최단 거리는 0이므로 배열 0에서 0으로 가는 최단 거리는 0으로 설정해준다.


배열 및 그래프에서 파란색은 시작 노드로부터 그 점을 최종적으로 방문 했다는 의미이다. (visit node)


즉, 파란색이 되면, 다음번 부터는 파란색으로 확인한 곳은 가지 않아도 된다는 의미이다.



두번째로 이제 0에서 갈 수 있는 모든 노드에 대해 생각해보자




0번 노드에서 1번 노드로 갈때의 현재 최단 거리는 3이다. 


따라서 배열 0에서 1로 가는 최단 거리는 현재 3으로 지정해둔다.


배열 및 그래프에서 빨간색은 간선을 통해 노드를 방문하고 있는 상황을 의미한다.




결과적으로 다음과 같이 설정이 되었다.






이렇게 3이 끝나고 2번 노드에 대해서도 현재 최단 거리를 찾아주고 설정해준다.


이렇게 0번 노드에 대해 계속 찾아낸다면 다음과 같은 그림이 연속할 것이다.






현재 노드 0번부터 시작해서 갈 수 있는 모든 노드를 방문하였을 때 최단거리는 배열 값과 같다.


0 -> 0 :: 0 ( 자기 자신 )

0 -> 1 :: 3

0 -> 2 :: 6

0 -> 3 :: 9

0 -> 4 :: 7



이제 0번 노드는 확인이 끝이났으니 그다음 0번 노드에서 가장 최단거리인 1번 노드에 대해 확인해 보도록한다.


즉, 1번 노드를 확인하고있다는 의미는, 0번에서 n번을 갈때 최단거리를 구하는 것이라는 것을 명심하고 있어야 한다.




이 과정을 보기 전, 위의 그림과 비교 해보자.


0번에서 2번 노드로 가는 최단 거리가 원래는 6이었는데 현재 5로 바뀌었다.


바로 위의 빨간 글씨가 이 말을 하고싶었는 내용이다.


즉, 계속해서 갱신하고 있음을 알고 있어야한다.



0->1->3의 값도 바뀌고 있다.


원래는 0->3으로 가는 최단 거리는 8이었는데 0->1->3을 통해 가는것이 더 빠르므로 현재 7로 갱신되었다.



0->1->4는 0->4보다 더 값이 커지므로, 따로 갱신을 하지 않아준다.



이번엔 0 -> 2 -> n번노드로 방문하는 것을 확인해보자.


경우의 수는 0 -> 2 -> 3, 0 -> 2 -> 4가 있는데


0 -> 2 -> 3은 11이고, 0 -> 1 -> 3이 7이므로 따로 갱신을 하지 않는다.


0 -> 2 -> 4는 11이고, 0 -> 4가 7이기에 따로 갱신을 해주지 않는다.


최단 거리일때만 계속해서 갱신해준다는 것을 잊으면 안된다.


또한 방문하고 있는 노드마다 배열이 파란색으로 변하고 있다는 점 또한 잊으면 안된다.(방문을 기록하는 색)



3번 노드또한 1가지 경우가 있다.


0 -> 3 -> 4 :: 10

0 -> 4 :: 7 이기에 따로 갱신을 하지 않는다.



따라서 모든 계산이 끝이나고,



실제 다익스트라 알고리즘이 추적한 경로는 다음과 같다.


최종적으로 알 수 있는 결과는 다음과 같다.


0 -> 0 최단거리 :: 0

0 -> 1 최단거리 :: 3

0 -> 2 최단거리 :: 5

0 -> 3 최단거리 :: 7

0 -> 4 최단거리 :: 7


이렇게 구하는 알고리즘을 다익스트라(dijkstra) 알고리즘이라고 한다.


소스 코드는 다음 게시물에 올릴 예정이다.






반응형