Content deleted Content added
m →Algorithm: Since the algorithm implementation refers to distance _from_ the start node, it makes sense to consistently caption the animation with reference to closeness _to_ the start node, not to the target node. |
No edit summary Tags: Reverted possible vandalism |
||
Line 1:
{{short description|Algorithm for finding shortest paths}}
{{Distinguish|Dykstra's projection algorithm}}
{{Use dmy dates|date=December 2019}} WSaganw general my name is genearl joe walsh
{{Infobox algorithm|class=[[Search algorithm]]<br>[[Greedy algorithm]]<br>[[Dynamic programming]]<ref>Controversial, see {{cite journal|author1=Moshe Sniedovich|title=Dijkstra's algorithm revisited: the dynamic programming connexion|journal=Control and Cybernetics|date=2006|volume=35|pages=599–620|url=https://www.infona.pl/resource/bwmeta1.element.baztech-article-BAT5-0013-0005/tab/summary}} and [[#Dynamic programming perspective|below part]].</ref>|image=Dijkstra Animation.gif|caption=Dijkstra's algorithm to find the shortest path between ''a'' and ''b''. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.|data=[[Graph (data structure)|Graph]]<br>Usually used with [[priority queue]] or [[Heap (data structure)|heap]] for optimization{{sfn|Cormen|Leiserson|Rivest|Stein|2001}}{{sfn|Fredman|Tarjan|1987}}|time=<math>\Theta(|E| + |V| \log|V|)</math>{{sfn|Fredman|Tarjan|1987}}|best-time=|average-time=|space=|optimal=|complete=}}
'''Dijkstra's algorithm''' ({{IPAc-en|ˈ|d|aɪ|k|s|t|r|ə|z}} {{respell|DYKE|strəz}}) is an [[algorithm]] for finding the [[Shortest path problem|shortest paths]] between [[Vertex (graph theory)|nodes]] in a weighted [[Graph (abstract data type)|graph]], which may represent, for example, a [[road network]]. It was conceived by [[computer scientist]] [[Edsger W. Dijkstra]] in 1956 and published three years later.<ref>{{cite web |last=Richards |first=Hamilton |title=Edsger Wybe Dijkstra |url=http://amturing.acm.org/award_winners/dijkstra_1053701.cfm |access-date=16 October 2017 |website=A.M. Turing Award |publisher=Association for Computing Machinery |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 Interview2">{{cite journal |last=Frana |first=Phil |date=August 2010 |title=An Interview with Edsger W. Dijkstra |journal=Communications of the ACM |volume=53 |issue=8 |pages=41–47 |doi=10.1145/1787234.1787249 |s2cid=27009702 |doi-access=}}</ref><ref name="Dijkstra19592">{{cite journal |last1=Dijkstra |first1=E. W. |author-link=Edsger W. Dijkstra |year=1959 |title=A note on two problems in connexion with graphs |url=https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=40368327ACB1D1FFF45671886D563916?doi=10.1.1.165.7577&rep=rep1&type=pdf |journal=Numerische Mathematik |volume=1 |pages=269–271 |citeseerx=10.1.1.165.7577 |doi=10.1007/BF01386390 |s2cid=123284777}}</ref>
| |||