|
|
|
}}
{{그래프 탐색 알고리즘}}
[[컴퓨터 과학]]에서, '''데이크스트라 알고리즘'''조민서({{llang|en|Dijkstra algorithm}}) 또는 '''다익스트라 알고리즘'''은 도로 교통망 같은 곳에서 나타날 수 있는 [[그래프 (자료 구조)|그래프]]에서 꼭짓점 간의 [[최단 경로 문제|최단 경로]]를 찾는 [[알고리즘]]이다. 이 알고리즘은 [[컴퓨터 과학자]] [[에츠허르 데이크스트라]]가 1956년에 고안했으며 삼 년 뒤에 발표했다.<ref>{{웹 인용|url=http://amturing.acm.org/award_winners/dijkstra_1053701.cfm |title=Edsger Wybe Dijkstra |last=Richards |first=Hamilton |website=A.M. Turing Award |publisher=Association for Computing Machinery |access-date=October 16, 2017 |quote=At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities?}}</ref><ref name="Dijkstra Interview">{{저널 인용|first=Phil |last=Frana |title=An Interview with Edsger W. Dijkstra|journal=Communications of the ACM|date=August 2010|volume=53|issue=8|pages=41–47 |doi=10.1145/1787234.1787249}}</ref><ref name="Dijkstra1959">{{저널 인용| authorlink = 에츠허르 데이크스트라 | first1 = E. W. | last1 = Dijkstra | url= http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf | title = A note on two problems in connexion with graphs | journal = Numerische Mathematik | volume = 1 | year = 1959 | pages = 269–271 | ref = harv | doi = 10.1007/BF01386390}}</ref>
이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만,{{r|Dijkstra1959}} 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 [[최단 경로 트리]]를 만드는 것이다.
|
