프로그래밍/알고리즘

다익스트라 알고리즘

콘파냐 2013. 6. 18. 22:35
반응형

다익스트라의 핵심은 다음글을 보기 바랍니다.


2015/06/02 - [프로그래밍/알고리즘] - 다익스트라 알고리즘(Dijkstra Algorithm)최단경로 알고리즘



아래 글은 제가 오래전 다익스트라를 처음 공부할 때 쓴 글이므로 이해가지 않는 부분도 있고 많이 부족합니다. 코드만 참고하시길 바랍니다.


다익스트라 알고리즘, 이름조차 어렵다.

이 알고리즘을 이해하기위해선 깊이 우선, 너비우선 탐색을 이해해야한다.

2013/06/05 - [프로그래밍/알고리즘] - 탐색-깊이우선탐색, 너비우선탐색

 

2013/06/07 - [프로그래밍/알고리즘] - 위상정렬(topological sort)

 

 

다익스트라 알고리즘은 시작점을 정하고 끝점을 정하면 그 두점사이 최단거리를 구하는 알고리즘이다.

다익스트라 알고리즘의 너비우선탐색의 변형이다. 다른 사이트나 알고리즘 책의 어려운 용어들로 중무장하고, 어려운 설명(결국 똑같은설명들)에 넉다운 되지말길 바란다.그래도 이해안되면 코드만 뚫어지게 쳐다보면서 세번만 똑같이 코드를 써가면서 머리속으로 흐름을 따라가봐라. 그럼 어느정도 이해할것이다. 만약 그래도 이해안된다면 아직은 이 알고리즘을 공부할 시기가 안된 것 뿐이다. 그냥 딴거 하다가 나중에 한번 더보면 이해된다.  그럼 시작해보자.

너비우선탐색에대해 공부를 했을것이다.

너비우선탐색의 방법은 시작되는 정점에서 갈수있는 점들을 파악한다. 그리고 순서대로 큐에 쌓는다. 여기서 너비우선탐색은 큐에 쌓아놓은 순서대로 이같은 작업을 반복한다. 큐에 더쌓을게없고 큐에서 시작정점플래그(head)와 끝점 플래그(tail)가 같아질때까지.

 

다익스트라는 너비우선탐색과 비슷한 듯 보이지만 다른 방식이다. 각 노드까지의 최단거리(토탈가중치)를 저장할 배열을 선언하고 최단거리를 계속 갱신하여 최단거리를 구하는 방식이다.

노드 1을시작해서 너비우선탐색과 같이 탐색하면 2,3,5가 파악된다. 아래 코드를 보면 행렬맵이 너비우선,깊이우선 탐색과는 다르다. 틀리다. 최단거리를 표현하여 저장하였다. 그리고 M의 값은 위 그래프에서 최단거리가 계산되지 않은 곳들은 9999라 저장해놓았다. 이 값은 충분히 큰값으로 대체할 수 있으며 의미는 아직 최단거리를 구하지 않은 곳이라는 의미다. 

예를 들어 노드1->노드7로 가는 가지수는 여러가지가 있기 때문에 아직 최단거리를 알 수 없다는 의미다. 그래서 a[1][7]의 값은 M이 된다. 그리고 value 배열도 모든 값을9999로 저장한다. 거리를 현재 알지못하기때문에 무한대로 둔거라 생각하면된다. 다익스트라 알고리즘은 어짜피 한번은 갱신되게 되어있기 때문에 이렇게 두는 것이다.


노드1부터의 최단거리를 생각해보자.

탐색을 해나가면서 value배열에 최단 거리를 계속해서 갱신하여 저장하는데. 처음에 노드1에서 탐색하는 방법은 2,3,5노드가 있고 가중치는 1,2,7이된다. 여기서 value 배열에 가중치를 저장한다. value[2]=1, value[3]=2, value[57]= 7

그러면 다음 그림을 보자. (아래그림 value[5]가 7, value[7]=9999로 수정합니다.)


노드1부터 시작해서 노드 2,3,7까지의 거리가 9999와 비교해서 작기 때문에 노드 2,3,7에 해당하는 value요소가 갱신되었다. 그리고 루프의 처음으로 돌아와서 다시 value배열의 요소들을 서로 비교해서 제일 작은 값이 다음 탐색기준점이다. 그래서 다음 탐색 기준점은 노드 2가된다. 탐색기준점이 정해졌으면 f배열의 해당번째요소에 1을 넣어서 기록한다. 그래야 다음 시작번지를 정하는 점검에서 제외되기 때문이다. 노드1의 경우는 설명을 생략했지만, 제일 처음의 경우도 마찬가지였다. 어짜피 노드1이 시작이고 0으로 초기화 한 상태기 때문에 노드1이 점검의 최소값이 되었고 f[1]=0으로 초기화 되었다. 이렇게 다익스트라의 다음 탐색기준점은 토탈 가중치가 제일 작은 값부터 시작이다. value배열은 노드1로부터의 토탈 가중치(거리)를 갱신한다는 것을 다시 상기해보자. 그리고 이런 방법을 나름대로 정리하여 그림을 보고 순서를 나열하는 연습을 해야할 것이다.



토탈 가중치를 갱신하는 방법은 

현재탐색기준노드까지 기록된 가중치 + 현재탐색기준노드에서 j노드까지 가중치 < 노드1부터 노드j까지 기록된 가중치 

일때 갱신을 하면된다. 기록된 가중치라함은 value 배열에 기록되 값을 말한다. 이 값은 최종적으로 시작점노드1로부터 최단거리를 나타내게된다.


다익스트라 알고리즘의핵심은 너비우선탐색은 아니지만, 너비우선탐색과 동일한 순서로 탐색해나간다. 너비우선탐색의 경우 행렬맵에서 중간에 노드가 있는 경우에는 값이 0이 되므로 조건에서 거짓이 된다. 하지만 다익스트라 알고리즘은 행렬맵에서 자신으로 가는 경우만 제외하면 모두 값이 존재하기 때문에 모든 경우수를 검사한다. 어짜피 모든 경우수를 파악하더라도 값이 M인 경우는 경로가 최소값이 될 수 없으므로 조건에서 거짓이 되기 때문이다.


기억해야할 것은 다익스트라는 너비우선탐색과 달리 가중치의 최소값을 지닌 노드가 시작점으로 정해지는 방식이다.연결된 방법이 아닌 연결될 노드끼리의 가중치에 따라서 검색 순서가 바뀌게된다. 


 

 

 

9999는 값은 무한대를 의미한다  아직파악이 안된 곳은 충분히 큰값 9999로 초기화 되어있다. 실제 거리가아닌 가상의 거리라생각하면편하다. 어떤 다른 방법이 존재하고 그 거리가 9999라고 생각하고 이제부터 최단거리를 갱신해나간다는 뜻으로 생각하자.

이는 인간의 직관과 다르게 컴퓨터로 일을 시키기위해선 모든 노드를 매번 반복적으로 비교해야하기때문이다. 반면 사람이 하는 일이라면 시작정점과 직접 연결된 부분과 파악된 점들(시작정점이었던 곳도 포함 <가중치가 갱신될 수도 있기때문에>)만 확인하고 넘어갈것이다. 컴퓨터에게 이 일을 시킬려면 어떻게 할 수가없다. 반복적이고 일관된 루프를 만들기위해선 이런 식으로 한 것이다.

 

여기서 index[]가 등장한다.

이것은 경로저장을 위한 것이다. 노드x에 해당하는 index[x]값은 최단거리에서 이전노드를 저장한다. 이를 이용해서 최단거리의 이동경로를 조사할 수 있다. 이또한 최단경로가 갱신될때 같이갱신되게 되어있다.

 

다익스트라 알고리즘은 하나씩 때어놓고 파악하기는 어렵지않다.

하지만 전체를 보기위해선 구조에대한 확실한 이해가 있어야한다.

제일 왼편값은 토탈 가중치합

알고리즘을 알기위해서는 우선 자료구조공부가 우선 되어야 한다고 생각한다. 물론 알고리즘을 먼저공부할 수도 있지만, 어짜피 자료구조들이 쓰이기 때문에 익숙해지면, 신경써야할 부분이 덜어진다고 할까

반응형