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

잔글
편집 요약 없음
잔글
{{알고리즘 정보
|분류 = [[검색탐색 알고리즘]]
|그림 = [[파일:Dijkstra Animation.gif|데이크스트라 알고리즘 실행]]
|그림설명 = ''a''와 ''b'' 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다.
|공간복잡도 =
}}
{{그래프 검색탐색 알고리즘}}
[[컴퓨터 과학]]에서, '''데이크스트라 알고리즘(=다익스트라 알고리즘)'''({{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>