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

프로그래밍/알고리즘

다익스트라 알고리즘(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까지의 가중치는 아직 모름(아주 높은 가중치로 설정) 해 놓습니다.(위에서 말한 토탈 가중치를 위한 배열을 아주 높은 값으로 초기화 합니다.) 어짜피 탐색을 하면서 비교되기 때문에 갱신됩니다.