프로그래밍/알고리즘

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

콘파냐 2015. 6. 3. 00:41
반응형

다익스트라 알고리즘에 대한 글을 쓴지 2년이 지났네요. 그동안 이 알고리즘을 사용할 일은 없었습니다. 그리고 최근 제가 쓴 글을 다시 보는 순간 나의 글이 너무 나도 허접해 보였습니다. 공부를 해갈수록 "아는 만큼 보인다" 라는 말이 뼈속 깊이 느껴지네요.

그 당시에 제가 쓴 글은 제 머리 속 생각만 쓰기 급급했습니다. 그래서 비록 아직도 한참 모자라지만, 다익스트라 알고리즘의 핵심을 재해석 해보려 합니다.


다익스타라 알고리즘

이 알고리즘의 핵심은 토탈 가중치에 있습니다.

사실 토탈 가중치는 가중치와 같은 의미로도 쓰이지만, 토탈 가중치는 최초 시작점으로 부터의 가중치라는 뜻입니다.

어떤 사람이 A의 위치에 있고 갈 수 있는 경로가 A->B->C->D 라고 하면

각각의 경로는 가중치가 있습니다. 가중치는 두 노드간 거리를 의미합니다. B->C 의 가중치, B->D까지의 가중치 등등..

이 사람 가고자 하는 경로의 시작점은 A이므로 토탈 가중치는 A부터 어떤 노드까지의 거리를 말합니다.

다익스트라 알고리즘은 이렇게 시작점으로 부터 가중치를 중첩해서 더해갑니다.


탐색의 방법은 너비우선탐색과 같습니다. 너비우선탐색의 경우  루프(for문)에서 반복되는 변수의 영향을 받습니다.

예를들어 for(int i=0;i<n;i++) 라고 하면 0부터 n-1까지 오름차순의 검색이 되고 for(int i=n;i>0;i--)라고 하면 n부터 1까지 내림차순 검색이 됩니다.

이 글을 읽으시는 분들은 이런 탐색은 익숙하실 겁니다.

반면에 다익스트라 알고리즘은 토탈 가중치의 합이 가장 작은 것을 시작점으로 탐색해 나갑니다. 루프의 처음에 가중치가 가장 작은 것을 찾은 후 이 노드까지의 토탈 가중치 + 이 노드로부터 다른노드까지의 가중치를 합해서 현재까지 기록된 토탈 가중치와 비교를 하여 토탈 가중치가 더 작은 경우가 나타나면 토탈 가중치를 갱신합니다. (토탈 가중치의 비교를 위한 배열을 사용합니다.)


위 그림은 노드들간의 가중치를 나타낸 그림입니다.

여기서 한 가지 질문을 해보죠.

만약 누가 1로부터 4까지 거리가 어떻게 되냐고 묻는다면, 어떻게 대답하시겠나요? 우리는 최단거리를 쉽게 파악하고 아마 3이라고 대답하실 겁니다. 하지만 컴퓨터는 사람과 같은 직관을 가지고 있지 않습니다. 1->5->7->4 , 1->3->6->5->7->4 등등의 거리를 직접 가보지 않고서는 4까지의 최단 거리를 알지 못합니다.

그래서 우리는 1부터 4까지의 가중치는 아직 모름(아주 높은 가중치로 설정) 해 놓습니다.(위에서 말한 토탈 가중치를 위한 배열을 아주 높은 값으로 초기화 합니다.) 어짜피 탐색을 하면서 비교되기 때문에 갱신됩니다.



시작점을 1로 하여(토탈 가중치 배열을 0으로 놓는다) 탐색을 시작하면 위와 같이 토탈 가중치가 갱신이 됩니다.

토탈 가중치 배열은 다음과 같이 갱신이 됩니다.

5번노드 토탈 가중치 7로 수정합니다

(0번째 노드는 사용하지 않습니다.)


토탈 가중치를 갱신했으므로 처음으로 돌아가 토탈가중치가 가장 작은 값을 찾습니다. 단 탐색하지 않은 노드여야합니다.

2번 노드가 됩니다.

2번 노드에서 탐색은 다음과 같습니다. 


토탈 가중치는 다음과 같이 갱신됩니다.


5번노드 토탈 가중치 7로 수정합니다

다시 토탈 가중치가 가장 작은 값을 찾습니다. 3번 노드가 되겠네요.




5번노드 토탈 가중치 7로 수정합니다

이번엔 4번 노드가 토탈 가중치의 합이 가장 작군요.



잘 보시면 7까지 토탈 가중치의 합이 한번 갱신 된 적이 있습니다. 1->2->7 의 경로가 그렇습니다. 그리고 위 탐색은 7까지 토탈 가중치의 합이 4가 되므로 다시 갱신을 시킵니다. (4<5 이므로)


5번노드 토탈 가중치 7로 수정합니다

(사실 여기서는 설명하지 않았는데 최단거리 경로를 위해 배열을 더 만들어 토탈 가중치가 갱신될 때 경로를 저장해야 합니다. 다익스트라의 핵심을 설명하기 위해 이 부분은 여기서 설명하지 않겠습니다.)


7번 노드의 토탈 가중치가 가장 작으므로 7번 부터 검색을 하면

5번 노드까지의 토탈 가중치가 7에서 6으로 두번째 갱신이 됩니다.


5번 노드->6


이 경우는 기존 갱신된 값과 비교시 새로 갱신이 안됩니다. 


6번노드와 8번 노드 두개 남았네요.

비교후 6번 부터 탐색이 됩니다.


마지막 8번 노드는 는 탐색할 곳이 없습니다. 바로 루프를 빠져나올 것 입니다.

위에 토탈 가중치 배열을 보시면 1에서 시작하는 모든 최단 거리를 알 수 있습니다.  최단 거리는 토탈 가중치기 때문입니다.

위에 그려진 그림을 보시면 최단 경로를 알 수 있습니다. 

최단 경로를 출력하는 방법은 토탈 가중치가 갱신될때 경로를 저장하는 배열에 경로를 저장하여 출력하는 방법입니다.


2013/06/18 - [프로그래밍/알고리즘] - 다익스트라 알고리즘

경로에 대한 코드는 위에 있는 곳의 코드를 참고하시되 설명 부분은 오래전 내용이라 조잡합니다.

반응형