최단경로1 다익스트라(Dijkstra) 알고리즘의 재발견 다익스트라 알고리즘의 pseudo-code와 C 코드는 위키피디아에 잘 나와 있으므로 그곳을 참고한다. 이 글은 어떻게 그 알고리즘을 생각하게 되었을까 를 내 나름대로 생각해 본 후 그에 대하여 쓴 글이다. 요약 다익스트라 최단경로 알고리즘은 다음과 같이 생각해 볼 수 있다. 즉, 경로의 그래프를 실로 되어 있다고 생각하고, 각 지점은 매듭으로 되어 있다고 가정하자. 이와 같은 상황에서 주어진 두 지점을 잇는 최단경로를 찾기 위해서는 그 주어진 두 점을 양 끝으로 잡아 당겼을 때 생기는 직선이 된다. 이것은 자명하다. 다익스트라 알고리즘은, 주어진 경로(그래프)에서 시작점이 주어졌을 때, 각 점으로 가는 최단경로를 구하는 알고리즘이다. 어느 날 나는 그가 어떻게 그 알고리즘을 생각했는지 궁금했다. 그 후.. 2010. 2. 7. 이전 1 다음
