"데이크스트라 알고리즘"의 두 판 사이의 차이

편집 요약 없음
(1 개의 출처 구조, 0 개의 링크를 깨진 것으로 표시) #IABot (v2.0)
태그: m 모바일 웹
그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다.<ref name="mehlhorn">{{서적 인용|last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn|first2=Peter |last2=Sanders|author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |publisher=Springer |year=2008 |chapter=Chapter 10. Shortest Paths |chapterurl=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ShortestPaths.pdf |isbn=978-3-540-77977-3 |doi=10.1007/978-3-540-77978-0}}</ref>{{rp|196–206}} 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 [[그래프]]에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 [[라우팅 프로토콜]]에서 널리 이용되며, 특히 [[IS-IS]] (Intermediate System to Intermediate System)와 [[OSPF]](Open Shortest Path First)에서 주로 사용된다. 또한 데이크스트라 알고리즘은 [[존슨 알고리즘]] 같은 알고리즘의 [[서브루틴]]으로 채택되었다.
 
데이크스트라의 원래 알고리즘은 [[우선순위 큐|최소 우선 큐]]를 사용하지 않았기 때문에 [[시간 복잡도]]가 <math>O(|V|^2)</math> (<math>|V|</math>는 꼭짓점의 개수이다)이다. 이 알고리즘의 개념은 {{괄호 없는 하버드 인용|Leyzorek|Gray|Johnson|Ladew|1957}}에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 [[피보나치 힙]]으로 수행되며 시간복잡도는 {{괄호 없는 하버드 인용|Fredman|Tarjan|1984}} 때문에 <math>O(|E|+|V|\log|V|)</math> (<math>|E|</math>는 변의 개수이다)이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 [[유향 그래프]]에서의 단일 소스 [[최단 경로 문제|최단 경로 알고리즘]] 중 [[점근 계산 복잡도|점근적]]으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우(제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우)에는 다른 {{slink||세분화된 변형}}으로 개선할 수 있다.
 
어떤 분야, 특히 [[인공 지능]] 분야에서, 데이크스트라 알고리즘이나 그 변형은 '''균일 비용 탐색'''으로 알려져 있으며 [[최상 우선 탐색]]의 일반적인 아이디어의 예시로 공식화 되어있다.<ref name="felner">{{콘퍼런스 인용|first=Ariel |last=Felner |title=Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm |conference=Proc. 4th Int'l Symp. on Combinatorial Search |year=2011 |url=http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357}}</ref>

편집

308