다익스트라 알고리즘의 pseudo-code와 C 코드는 위키피디아에 잘 나와 있으므로 그곳을 참고한다. 이 글은 어떻게 그 알고리즘을 생각하게 되었을까 를 내 나름대로 생각해 본 후 그에 대하여 쓴 글이다.

요약
다익스트라 최단경로 알고리즘은 다음과 같이 생각해 볼 수 있다. 즉, 경로의 그래프를 실로 되어 있다고 생각하고, 각 지점은 매듭으로 되어 있다고 가정하자. 이와 같은 상황에서 주어진 두 지점을 잇는 최단경로를 찾기 위해서는 그 주어진 두 점을 양 끝으로 잡아 당겼을 때 생기는 직선이 된다. 이것은 자명하다[각주:1].

   다익스트라 알고리즘은, 주어진 경로(그래프)에서 시작점이 주어졌을 때, 각 점으로 가는 최단경로를 구하는 알고리즘이다. 어느 날 나는 그가 어떻게 그 알고리즘을 생각했는지 궁금했다. 그 후 한 가지 아이디어를 생각해 낸 후, 알고리즘으로 바꾸자 다익스트라 알고리즘이 되었다.

   아이디어는 매우 단순하다. 우선 출발점과 시작점을 생각한 후, 두 지점을 잇는 최단 경로는 두 점을 양끝으로 잡아 당겼을 때 생기는 직선이라는 것이다.

step1

위와 같은 그래프가 주어져 있고, A와 I 를 잇는 최단 경로를 알고자 한다면, A와 I 를 잡고 양 끝으로 잡아 당기면 되는 것이다.


step2




위와 같은 생각을 정리를 해보자면, 도착점이 어디든 그 점과 시작점을 잡고 양끝으로 잡아 당기면 최단경로가 나오는데, 문제는 어떻게 중간에 있는 노드들을 찾을 것인가 하는 것이다. 결국 시작점과 인접한 노드들부터 그 거리를 계산해야 하는데, 그림으로 나타내면 다음과 같다.

step3

우선 A 의 근접 노드들을 생각해 보자. 아직 이 노드들 중 없애야 할 것을 알 수는 없다. 따라서, 이 인접 노드들의 인접 노드들을 생각해 보자.

step4

위 그림에서 보면 붉고 굵은 선으로 되어 있는 경로에 연결된 D, F, G, H 가 A 에서 거리(여기서 모든 edge는 거리가 1로 가정)가 2인 노드들이다. 이 노드들 중에 특히 G를 생각해 보자. 왜냐 하면 A에서 G 로 가는, 길이가 2인 경로가 여러 개이기 때문이다.

step5

이 경우, A에서 G로 가는 경로만 따로 떼어서 생각을 해보면,

step6


최단 경로는 결국 A와 G를 양끝으로 잡아 당긴 경로이다.

step7

이 경로를 다시 원래의 그래프로 가져가면,

step8

이렇게 된다. 이것은, 즉, A에서 G로 가는 3개의 경로

A -> B -> G
A -> E -> G
A -> B -> E -> G

중 A -> E -> G 를 선택해야 함을 의미한다. 지금까지의 생각을 곧바로 재귀시켜버리면 다익스트라 알고리즘이 나온다. 즉, 트리로 바꾸어서 똑같은 논리를 따라 갈 수 있다. 이제, 본격적으로 문제를 풀어 보자.

우선 각 edge 가 다른 길이를 갖는 그래프를 하나 만들자.

step9


A 에서 출발할 것이므로, A 를 root note 로 두고 한 단계 덧붙이자.

step10

역시 이 단계에선 버릴 노드를 알 단서가 없다. 한 단계 더 덧붙이자.

step11

이 단계에선 여러 노드가 겹치는 것을 볼 수 있다. E 를 생각해 보자. 결국 이것은 A 에서 E 로 가는 여러 경로가 존재함을 의미한다. 이 여러 경로 중 어느 것을 선택할 것인가는 자명하다.

step12

A에서 E 로 오는 경로가 가장 짧은 것만 남겨 두고 나머지는 버린다. 이 단계가 바로 위에서 그래프를 실로 된 것으로 생각했을 때 시작 노드와 끝 노드를 양끝으로 잡아 당기는 상황을 표현한 것이다.

step13

이런 식으로 나머지 겹치는 노드들에 대해서도 같은 절차를 적용하면 결과적으로 다음과 같이 된다.

step14

이젠 더이상 버릴 노드가 없다. 이 상태에서 남아 있는 노드들을 가지고 한 단계 또 늘려 보자.

step15

역시 같은 논리로, 새로 추가된 노드들에 대하여, 그 노드로 가는 중복경로 중 가장 짧은 것만 남기고 나머지는 지운다. 그러면 다음과 같이 된다.

step16

이제 더이상 추가할 노드가 없다. 그러므로 끝.


그냥 단순히 그래프에서 양 끝으로 잡아 당기는 것은 약간 혼동될 수 있는데, 트리로 바꾼 것은 쉽게 이해할 수 있는 형태이다. 트리로 표현한 절차를 알고리즘으로 옮기면 정확히 다익스트라 알고리즘이 된다.




  1. 두 점을 잇는 최단경로는 직선이다, 이것은 수학에서의 공리이다 [본문으로]

'컴퓨터 > 수학이랑' 카테고리의 다른 글

일반화된 상관계수  (0) 2010.03.23
constraint adaptive differential evolution  (2) 2010.02.16
다익스트라(Dijkstra) 알고리즘의 재발견  (22) 2010.02.07
Savitzky-Golay smoothing  (4) 2010.01.16
monotone cubic Hermite interpolation  (15) 2010.01.12
cubic spline interpolation  (18) 2010.01.11
Posted by adnoctum

댓글을 달아 주세요

  1. Favicon of http://smallhuman.egloos.com 긁적 2010.05.28 22:57  댓글주소  수정/삭제  댓글쓰기

    다익스트라를 'C로 쓴 자료구조론'보고 공부했는데, 이게 훨씬 쉽네요 _-_....
    재미있는 포스트 감사합니다.

  2. Favicon of http://blog.naver.com/gustns2010 로지 2011.02.19 10:21  댓글주소  수정/삭제  댓글쓰기

    와, 정말 재밌게 설명하셨네요. Dijkstra 알고리즘을 트리로 해석해서 본건 이번이 처음 인 것 같습니다. 재밌는 해석 감사드립니다.

  3. 돌멩이 2011.06.11 20:31  댓글주소  수정/삭제  댓글쓰기

    정말 쉽게 설명해놨네용 감사합니다~

  4. Favicon of http://wonderfuldream.tistory.com johnny 2011.07.29 21:36  댓글주소  수정/삭제  댓글쓰기

    정말 잘 설명해주셨네요. 잘 보고 갑니다!

  5. 은빛 2011.08.20 01:20  댓글주소  수정/삭제  댓글쓰기

    아주 이해가 척척 가네요~ 감사합니다~~

  6. 영차 2011.09.15 23:29  댓글주소  수정/삭제  댓글쓰기

    전세계에서 가장 쉬운 설명입니다. ㄳ

  7. 2011.10.29 14:19  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

    • Favicon of https://adnoctum.tistory.com adnoctum 2011.10.29 18:14 신고  댓글주소  수정/삭제

      공모전은 자신의 생각을 표현하는 자리 아닌가요? 만약 위의 생각을 그대로 '다시' 표현하는 것이라면 저는 별로 의미없다고 생각하며, 따라서, 위 그림을 이용하는 것은 좋지 않은 접근이라 생각합니다.

      만약 님이 위 생각을 확장/수정/보완/개선해서 발표할 것이라면 위 그림 및 내용을 사용하는 것이 상관은 없습니다. 이런 경우 원래의 생각(idea)이 자신이 아니라면 출처를 밝히는 것은 보통 가장 기본적인 태도로 간주하기 때문에 이 부분은 정확히 밝혀주는 것이 좋을 것입니다. 만약 그렇게 할 것이라면 출처를 '인터넷 검색'이라고만 해도 저는 상관이 없습니다.

      요약하면, 위 생각을 그대로 이용할 것이라면 위의 내용 및 그림을 그대로 공모전에 사용하는 것을 저는 반대합니다. 반대로, 위 생각을 발전시킨다면 출처를 이 곳이라 명시하지 않아도 내용 및 그림의 사용에 적극 찬성합니다. 만약 후자라면 말씀하세요, 원본 visio 파일을 드리겠습니다.

  8. 컴공학도 2011.12.04 23:50  댓글주소  수정/삭제  댓글쓰기

    주옥같은 설명이었습니다!

  9. 지나가다 2012.04.12 23:43  댓글주소  수정/삭제  댓글쓰기

    설명 최고에요 짱

  10. 나그네 2012.06.29 16:44  댓글주소  수정/삭제  댓글쓰기

    감사합니다^^ 제가 본 설명 중 최고네요

  11. Favicon of http://cafe.naver.com/gld3d 바른생활 2012.07.24 08:38  댓글주소  수정/삭제  댓글쓰기

    아~ 이런 글을 아름답다고 해야 하나요? *-*... 저희 카페(3Dprogramming)에도 글 앞부분 쪼금 보여주고 이리 올 수 있도록 링크 좀 걸어두었습니다. 감사합니다.~

  12. CodeNo8892 2012.11.30 20:13  댓글주소  수정/삭제  댓글쓰기

    굿

  13. 공부하다 2013.12.03 09:48  댓글주소  수정/삭제  댓글쓰기

    대단하십니다.

    감동입니다. ^^

  14. 해피 2014.05.01 16:09  댓글주소  수정/삭제  댓글쓰기

    감사합니다 ㅎㅎ 트리문양으로 금방해결이되네요!

  15. 이삭 2014.10.20 20:53  댓글주소  수정/삭제  댓글쓰기

    다익스트라 계속 이해가 안가서 이뭉사 저문서 많이 찾아봤는데.. 이 글은 단번에 이해 가능했습니다. 전달의 창의성이 대단합니다~ 좋은글 감사합니다.

  16. ee23 2014.11.26 13:42  댓글주소  수정/삭제  댓글쓰기

    안녕하세요 최근에 알고리즘 관련해서 자주 찾게 되네요

    혹시 본문에 설명하실 때 그린 그림은 무슨 툴 사용하셨는지 알수 있나요 (파워포인트나 비지오 같기도 하고)

  17. Favicon of https://sayheart.tistory.com sayheart 2015.05.07 02:19 신고  댓글주소  수정/삭제  댓글쓰기

    이 글을 보고. 제가 다시 정리해봤습니다.
    제 생각이 맞는지는 모르지만. 한번 봐주시겠습니까?
    아직 저도 대충 만든거라. 확인이 필요합니다. ㅇ_ㅇ;;

    작성한 내용의 주소
    https://t1.daumcdn.net/cfile/blog/256AFB36554A4C8113

  18. Favicon of https://sayheart.tistory.com sayheart 2015.05.07 23:44 신고  댓글주소  수정/삭제  댓글쓰기

    답변 감사드립니다. ㅇ_ㅇ;;
    좀 더 쉬운 방법을 고민해봤는데. 잘 알려졌으면 좋겠습니다.

  19. 도은쓰 2016.06.19 10:03  댓글주소  수정/삭제  댓글쓰기

    와 !!!! 진짜 감사합니다!!! 진짜 쩐다!!! 낼시험인데 굿굿 정말 감사해요 ㅜㅜㅜㅜㅜ