위의 이미지는 위키피디아 Dijkstra Algorithm에 대한 내용에서 가져왔음을 밝힙니다.
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

다익스트라 알고리즘(Dijkstra's algorithm)은 그래프에서 최단거리를 구해, 그래프를 트리의 구조로 변경시키는데 목적이 있습니다. 여기서 경로의 길이를 감안한다는 것과 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다는 점이 있습니다.

위의 이미지는 다익스트라 알고리즘을 굉장히 잘 설명하고 있습니다. 초기에는 노드 a에서 연결될 수 있는 모든 노드들에 대한 값을 무한대로 설정을 합니다. 여기서 거리를 감안하여, 하나씩 최단거리를 모두 알아가는 과정을 거칩니다. 가능한 모든 경우의 수를 시도한 노드는 out 상태가 됩니다.

위의 그래프에서 다익스트라 알고리즘을 수행하였을 때, 최종 결과는 어떻게 나올까요?



최단거리를 구한다는 것은 가장 빠른 시간을 통한 접근이라는 말이 됩니다. 이는 네트워크 쪽에서 라우팅 프로토콜을 배울 때 사용되기도 하니 잘 알아두시면 편리할 것 같습니다.
저작자 표시 비영리 변경 금지
신고
by 가우초 2012.01.03 20:42
| 1 |