디익스트라 알고리즘(Dijkstra algorithm)

위키피디아에 있는 코드1이 왠지 어려워서 나름대로 주석을 좀 추가하고 정리를 해봤는데, 그래도 어렵다. 그림을 그려서 설명하면 그나마 좀 괜찮은데 글로만 설명하려니 역시 쉽지 않은듯.

알고리즘 설명

시작노드를 설정 후 모든 노드에 대해(메인 루프) 아래 2가지 루프를 적용한다.

  • 서브 루프1: 현재 노드에서 도달 가능한 모든 노드 중 최소거리인 노드를 찾은 후 현재노드값을 해당 위치로 변경
  • 서브 루프2: 변경된 현재 노드까지 오는 최단거리를 알고있으므로, 이 값을 기준으로 다른 모든 노드들에 도달하는 거리를 한번씩의 덧셈으로 업데이트 한다. (현재노드까지 최단거리값 + 현재노드에서 다음노드 거리 = 출발노드에서 다음 노드까지의 최단거리)


  1. http://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98