2019년 11월 25일 (월) 23:55 판 편집 Mc progw12 (토론 \| 기여) 335 편집 편집 요약 없음 태그: m 모바일 웹 ← 이전 편집		2019년 12월 9일 (월) 11:58 판 편집 편집 취소 TedBot (토론 \| 기여) 봇, 업로더 2,721,547 편집 잔글 봇: 인용 틀 구식 변수 정리 다음 편집 →
22번째 줄: == 역사 == {{인용문5\|[[로테르담]]에서 [[흐로닝언]]까지, 일반적으로 한 도시에서 다른 도시로 가는 가장 짧은 길은 무엇일까요? 이것은 제가 이십 분 동안 생각해낸 [[최단 경로 문제\|최단 거리를 찾는 알고리즘]]입니다. 어느 날 아침에 저는 제 약혼녀와 [[암스테르담]]에서 쇼핑을 하고 있었고, 지쳤었기 때문에 카페 테라스에 앉아서 커피를 마시면서 그 문제에 대해서 생각하다가 최단 거리를 찾는 알고리즘을 고안했습니다. 제가 말했듯이, 이것은 이십 분 짜리 발명품입니다. 사실, 이 알고리즘은 삼 년 뒤인 [[1959년\|59년]]에 발표했습니다. 그 간행물을 여전히 읽을 수 있습니다. 사실은 꽤 괜찮습니다. 이것이 괜찮은 이유 중 하나는 제가 이 알고리즘을 고안할 때 연필과 종이 없이 고안했다는 것입니다. 제가 나중에 알게 된 바로는 연필과 종이 없이 고안하는 것의 좋은 점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문이라고 합니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다.<!--What is the shortest way to travel from [[Rotterdam]] to [[Groningen]], in general: from given city to given city. [[Shortest path problem\|It is the algorithm for the shortest path]], which I designed in about twenty minutes. One morning I was shopping in [[Amsterdam]] with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.-->\|에츠허르 데이크스트라, Philip L과의 인터뷰에서. Frana, Communications of the ACM, 2001<ref name="Dijkstra Interview"/>}} 데이크스트라는 1956년에 네덜란드 국립 수학 정보과학 연구소에서 새로운 컴퓨터 ARMAC의 수용력을 입증하는 프로그래머로 일할 때 최단 경로 문제에 대해서 생각했다.<ref>{{웹 인용\|title=ARMAC\|url=http://www-set.win.tue.nl/UnsungHeroes/machines/armac.html\|website=Unsung Heroes in Dutch Computing History\|date=2007\|archiveurl=https://web.archive.org/web/20131113021126/http://www-set.win.tue.nl/UnsungHeroes/machines/armac.html\|archivedate=13 November 2013\|~~deadurl~~url-status=~~yes~~dead\|df=dmy-all}}</ref> 이제 해야 할 일은 컴퓨터를 다루지 않는 사람들도 이해할 수 있도록 문제와 (컴퓨터가 만들어낸)해법을 둘 다 선택하는 것이었다. 그는 최단 거리 알고리즘을 고안하고, 이후 ARMAC에서 약간 단순화된 네덜란드 도시 64개(도시의 숫자를 표시하기 위해서 6 비트만 필요하도록 64를 선정했다)의 교통 지도에 대해서 수행했다.<ref name="Dijkstra Interview"/> 일 년 뒤, 데이크스트라는 기관의 다음 컴퓨터를 작업하던 하드웨어 엔지니어들의 문제를 직면했다: 기계의 후면 패널에 있는 핀을 연결 할 때 필요한 전선의 개수를 최소화 하는 것이다. 그 해법으로, [[프림 알고리즘\|프림 최소 신장 트리 알고리즘]]으로 알려진 알고리즘을 재발견 했다(이전에는 [[Vojtěch Jarník\|Jarník]]에 의해 알려져 있었고, 또한 프림에 의해 재발견 되었었다).<ref name="EWD841a">{{인용\| last1 = Dijkstra \| first1 =Edsger W. \| title = Reflections on "A note on two problems in connexion with graphs \| url = https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD841a.PDF}}</ref><ref>{{인용\|first=Robert Endre\|last=Tarjan\|authorlink=로버트 타잔\|title=Data Structures and Network Algorithms\|series=CBMS_NSF Regional Conference Series in Applied Mathematics\|volume=44\|year=1983\|publisher=Society for Industrial and Applied Mathematics\|page=75\|quote=The third classical minimum spanning tree algorithm was discovered by Jarník and rediscovered by Prim and Dikstra; it is commonly known as Prim's algorithm.}}</ref> 데이크스트라는 이 알고리즘을 프림이 발표한 지 2년 뒤이고 Jarník이 발표한 지 29년 뒤인 1959년에 발표했다.<ref>{{저널 인용\|last1=Prim\|first1=R.C.\|title=Shortest connection networks and some generalizations\|journal=Bell System Technical Journal\|date=1957\|volume=36\|pages=1389–1401\|doi=10.1002/j.1538-7305.1957.tb01515.x\|url=http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf\|archiveurl=https://web.archive.org/web/20170718230207/http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf\|archivedate=2017-07-18\|~~deadurl~~url-status=예dead\|df=dmy-all\|확인날짜=2018-06-21}}</ref><ref>V. Jarník: ''O jistém problému minimálním'' [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (in Czech)</ref> == 알고리즘 == 263번째 줄: * {{저널 인용\|first1=Rajeev\|last1=Raman\|title=Recent results on the single-source shortest paths problem\|journal=SIGACT News\|volume=28\|issue=2\|pages=81–87\|year=1997\|ref=harv\|doi=10.1145/261342.261352}} * {{저널 인용\|first1=Mikkel\|last1=Thorup\|title=On RAM priority Queues\|journal=SIAM Journal on Computing\|volume=30\|issue=1\|pages=86–109\|year=2000\|doi=10.1137/S0097539795288246\|ref=harv}} * {{저널 인용\|first1=Mikkel\|last1=Thorup\|title=Undirected single-source shortest paths with positive integer weights in linear time\|journal=journal of the ACM\|volume=46\|issue=3\|pages=362–394\|year=1999\|doi=10.1145/316542.316548\|ref=harv\|url=http://www.diku.dk/users/mthorup/PAPERS/sssp.ps.gz\|확인날짜=2017년 11월 1일\|보존url=https://web.archive.org/web/20170921234030/http://www.diku.dk/users/mthorup/PAPERS/sssp.ps.gz\|보존날짜=2017년 9월 21일\|~~깨진링크~~url-status=예dead}} == 외부 링크 ==

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