Преглед на кодот на Дајкстрин алгоритам

{{Infobox algorithm
|class=[[пребарувачки алгоритам]]
|image=[[Image:Dijkstra_Animation.gif]]
|caption = 
|data=[[граф]]
|time= <math>O(|E| + |V| \log|V|)</math>
|best-time=
|average-time=
|space=
|optimal=
|complete=
}}
'''Дајкстрин алгоритам''' — вид [[пребарувачки алгоритам]] во [[граф]] што може да реши еден проблем во вид на најкраток пат во даден граф со ненегативни вредности (тежини) на гранките на еден граф (растојанието од една до друга точка претставува гранка), така што алгоритмот продуцира дрво со најкраток пат. Осмислен е од холанѓанскиот компјутерски научник [[Едгсер Дајкстра]] во 1956 година и објавен во 1959 г.

За дадена точка во графот, алгоритмот ќе ги најде сите најкратки патишта од дадената точка до сите други точки на графот. Алгоритмот можи да се подеси да бара само најкраток пат од една до друга точка така што кога ќе го најде бараното одредиште тој да застани да работи и на излез да ја прикажи бараната вредност. Алгоритмот на Дајкстра може да биде искористен за да најди најкраток пат од еден град до сите други градови во светот.

== Функцијата на алгоритмот ==
[[Image:Dijkstras progress animation.gif|thumb|Илустрација на Дајкстриниот алгоритам како изгледа пребарување на најкраток пат од почетна точка до крајна точка.]]

На почеток треба да одбериме точка од каде што ќе почниме да пребаруваме. Нека растојанието до точка Y биди растојание од почетната точка до Y. Дајкстриниот алгоритам ќе означи некој почетни вредности на растојанијата и ќе проба да ги подобри нивни.

# Додели на секоја точка одредено растојание со пробна вредност: почетната точка треба да има вредност 0 додека на другите точки(точките има бесконечна вредност не ребрата) ќе му дадеш бесконечно голема вредност.
# На почекот сите точки се непосетени,тргнуваш од одберена точка.Создаваш еден сет од непосетени точки,каде што ги содржи сите точки освен почетната т.е точката што ја одберивме.
# Почнуваш од почетната точка и ги пресметуваш растојанијата од точката до нејзините соседни точки.Почнуваме од почеток, почетната точка има вредност (0),така што ако пристапиме од почетната точка(А) до некоја точка (B), ја земаме вредноста на точката А=0 и ако пристапиме до некоја точка со вредност B=∞, вредноста на точката А ја собираме со вредноста на растојанието од А до B така што ако растојанието е 6 и имаме (0+6)=6 и на точката B и ја задаваме вредноста минимално (A+растојанието од А до B,вредноста на точката ). .
# Кога завршивме со разгледување низ растојанијата до соседните точки ја означуваме точката до која што имаме пристапено како посетена, ја бришиме од сетот за непосетени точки.Посетената точка нема никогаш да биде проверена уште еднаш, и растојанието снимено сега е финално и минимално.
# Ако дестинационата точка е означена како посетена или ако најмалата тежина од точките е во непосетениот сет, тогаш застани. Алгоритмо заврши.
# Сетираја непосетената точка обележана со најмало растојание како следна почетна точка и вратисе на третиот чекор.

== Опис на алгоритмот ==
'''Забелешка''': За полесно разбирање на алгоритмот, ова дискусија користи термини како '''пресек''','''пат''' и '''мапа''' – инаку, овие термини се точки, гранки, кои образуваат еден вид на '''граф'''.
 
Да претпоставиме дека сакаме да најдеме најкраток пат помеѓу два пресеци во Скопје, и имаме почетна точка и крајна точка т.е одредиштето до која сакаме да најдеме најкраток пат. Почнуваме од почетната точка, и почетната точка има вредност 0 додека другите точки има бесконечно голема вредност. Ова не значи дека ќе имаме бесконечен голем пат до местото кај што сакаме да втасаме, туку означува дека точката не е посетена. Потоа од пресекот ги посетуваме сите соседни пресеци, и нив му ја задаваме вредноста која што сме ја поминале. Пример: Ако железничката во Скопје до Центар има 5000 метри, тогаш пресекот Центар ќе има вредност 5000. 
Од пресекот во кој се наоѓаме во моментот, го надоградуваме растојанието од едниот пресек до другиот пресек којшто се директно поврзани. 
Продолжиго овај процес со надоградување на соседните пресеци со најкратките растојанија, и продолжи до најблиските непосетени пресеци сè додека нема повеќе соседни темиња за посетување, и го означуваме пресекот во кој се наоѓаме како посетен. Во моментот кога го означи пресекот како посетен, ти го имаш одредено најкраткиот пат до точката. 
Како забелешка фактот е дека овај алгоритам не прави никаков обид за директно истражување како некој би очекувал. Туку, работи така што го бара растојанието до следниот пресек, не до бараниот пресек.

== Псевдокод ==
{{превод|англиски}}
Во следниот код <code>u := точка in ''Q'' со најмало растојание растојание[]</code>, пребарува во сето од точки <code><var>u</var></code>  <code><var>Q</var></code> што има најмала <code>растојание[<var>u</var>]</code> вредност. Таа точка е отстранета од сетот <code><var>Q</var></code> и вратена на излез  <code>dist_between(<var>u</var>, <var>v</var>)</code>  така што го пресметува растојанието помеѓу точката <code><var>u</var></code> и <code><var>v</var></code>. Променливата <code><var>alt</var></code> на линија 20 & 22 е должината од почетната точка до некоја соседна точка <code><var>v</var></code> ако оди низ точката  <code><var>u</var></code>. Ако патот пресметан е покракот од вредноста која ја има точката <code><var>v</var></code>, патот којшто го има точката се заменува со по оптималниот пат<code><var>alt</var></code>. Претходната низа има покажувач до следната точка за да се земи најкраткиот пат.

  1  '''функција''' Дајкстра(''Граф'', ''почетна точка''):
  2      '''За секоја''' точка ''v'' во ''графот'':                                ''// Иницализација на сите точки''
  3          растојание[''v''] := бесконечно голема вредност ;                                  ''//Непозната вредност на сите точки до 
  4                                                                                ''//точката v'' 
  5          претходно[''v''] := недефинирано ;                             ''// Претходната точка во оптималниот пат
  6                                                                 ''// од почетната точка ''
  7      
  8      растојание[''почетна точка''] := 0 ;                                        ''// Растојанието од почетната точка до почетната''
  9      ''Q'' := сет од сите точки во''Графот'' ;                       ''// Сите точки во графот се ''
 10                                                                 ''// неоптимизирано - со тоа што се во Q''
 11      '''Додека''' ''Q'' '''не е ''' празен извршувај:                                      ''// Главниот циклус''
 12          ''u'' := точка во ''Q'' со најмало растојание во растојание[] ;    ''// Почетната точка во првиот случај''
 13          избршија  ''u'' од ''Q'' ;
 14          '''Ако''' растојание[''u''] = бесконечност:
 15              '''врати на почеток на циклус''' ;                                            ''//  не може да се пристати ''
 16                                                                 ''// до точките од почетната точка ''
 17          
 18          '''За  секој''' сосед ''v'' од''u'':                              ''// каде в не е отстранет 
 19                                                                                 оо сетот Q.
 20              ''alt'' := растојание[''u''] + растојание_помеѓу(''u'', ''v'') ; ''// На промелнивата алт се задава вредност од ''
 21              '''Ако''' ''alt'' < растојание[''v'']: 
                   ''//изминатото растојание и се проверува дали е помало од растојанието до точката што се пристапува ''         
 22                  растојание[''v''] := ''alt'' ;
 23                  претходна[''v''] := ''u'' ;
 24                  намалувачки-kлуч ''v'' во ''Q'';                           ''// И се прередува v во сетот Q ''
 25      '''врати''' растојание;

Ако сме заинтересирани само за растојание помеѓу две точки <code><var>почетна точка</var></code> и <code><var>крајна точка</var></code>, можиме да заврши во линија 13 ако <code><var>u=</var>крајна точка</var></code>.
Сега можиме да го прочитаме најкраткиот пат од <code><var>почетна точка</var></code> до <code><var>крајна точка</var></code> со итерација:

 1  ''S'' := empty sequence
 2  ''U''крајна точка''
 3  '''Додека''' претходна[''u''] е дефинирана:
 4      внеси ''u'' во почеток од сетот''S''
 5      ''u'' := претходно[''u'']
 6  '''заврши со циклусот''' ;

Сега секвенцата <code><var>S</var></code> е листа од точки со најкратки патеки од code><var>почетна точка</var></code> до <code><var>крајна точка</var></code>, или е празна зошто таква патека не постои.

По генерален проблем е да се најда сите најкратки патишта помеѓу <code><var>почетна точка</var></code>,  и <code><var>крајна точка</var></code>,  (може да има повеќе такви со исти вредности). Тогаш наместо да ставиме една точка во низата <code>previous[]</code> ќе ставиме низа од точки за да ги дознаеме патеките. На пример, ако точката <code><var>r</var></code> и <<code><var>почетната  точка</var></code>,  се поврзуваат во <code><var>крајна точка</var></code> и двете од нив имаат различни најкратки патишта до <code><var>крајна точка</var></code>(зошто тежините на гранките се исти), тогаш ќе ги додадеме двете точки, <code><var>r</var></code> и <code><var>почетна точка</var></code>,  на <code><var>претходна[крајна точка]</var></code>, Кога алгоритмот ќе заврши, <code>претходна[]</code> податочната структура всушност опишува график што претставува подграф на главниот график со неколку гранки отфрлени. Клучот на алгоритмот е ако почниме од некоја точка до друга точка, сите точки до каде што има пристапено алгоритмот имаат најкратки патеки, и сите должини од оригиналниот граф ќе бидат претставени на нов граф. Тогаш за всушност да го најдеме најкраткиот пат помеѓу две точки ќе искористиме пребарување во длабочина.

== Време на извршување ==

Горната границата на времето на извршување на алгоритмот со гранки <math>E</math> и точки <math>V</math> можеме да ја прикажиме како функција од <math>|E|</math> и <math>|V|</math> со користење на [[Голема О ознака#Graph theory|Голема-O ознака]].

За секоја имплементација од сетот на точки <math>Q</math> времето на извршување е <math>O(|E| \cdot dk_Q + |V| \cdot em_Q)</math>, каде <math>dk_Q</math> и <math>em_Q</math> се времињата потребни да се намали клучот и да се извршат минимум операции во сетот <math>Q</math>, соодвнетно.

Нај елементарна имплементација на Дајкстриниот алгоритам е сетот на точки <math>Q</math> да се смести во поврзана листа или низа, и да екстрактираш од <math>Q</math> и само што  пребаруваме линеарно во сетот <math>Q</math>. Во овај случај, времето потребно да се изврши е <math>O(|E| + |V|^2) = O(|V|^2)</math>.

За [[ретки графови]], тоа се, графови со помалку од <math>O(|V|^2)</math> гранки, Дајкстриниот алгоритам може да биде полесно применет со  [[соседни листи]] и користење на [[бинарен хип]], [[парен хип]], or [[фибоначиев хип]] и еден [[приоритетен ред]] да се имплементира минималното екстрактирање. Со бинарен хип, на алгоритмот му е потребно <math>\Theta((|E| + |V|) \log |V|)</math> време (што е доминирано со<math>\Theta( | E | log | V | )</math>, ако претпоставиме дека графот е поврзан). За да избегниме  O(|V|) треба да видиме во клучот што се намалува на бинарниот хип, и многу важно е да се воспостави суплементарно мапирање на индексите од точките во индексирањето на бинарниот хип (за да можи да биди во тек со промените на приоритетниот ред <math>Q</math>), со што времето на извршување ќе биде  <math>O(log|V|)</math>. [[Фибоначиевиот хип]] го подобро времето на извршување за <math>O(|E| + |V| \log|V|)</math>.

Забелешка дека во  [[Директен ацикличен граф]], можно е да се најде најкраток пат од почетна точка до крајна точка во линеарно време, со обработка на точките во тополошки ред, и пресметување на најкраткиот пат за секоја точка да има најмала должина добиена од некој од следните гранки.<ref>http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html</ref>

== Поврзани проблеми и алгоритми ==

Функционалноста на Дајкстриниот алгоритам може да биде изменет со различни техники. На пример, некогаш потребни се решенија помалку математички оптимални. За да добијаме помалку оптимални решенија, првин треба да го пресметаме оптималното решение. Така што кога ќе го имаме оптималното решенија ќе избршиме една гранка од графот, и оптималното решенија за новиот граф ќе биде пресметано. Секоја откината гранка е прикриена на страна и нови најкратки патеки се пресметуваат. Вторите решенија се издвоени и рангирани после првото оптимално решение.

Принципот на работа на Дајкстриниот алгоритам се користи во [[link-state routing protocol]]s, [[OSPF]] и [[IS-IS]].

Не како Дајкстриниот алгоритам, [[Алгоритмот на Беллман-Форд]] можи да биде искористен во граф со негативни тежини, сè додека графот нема [[негативни кругови]] дофатни од избраната точка''s''. (Присуството на такви графови означува дека нема најкраток пат, затоа што најкратка тежина се стреми кон минус бесконечност.)

[[A-стар алгоритмот|A* алгоритам]] е генерализација од Дајкстриниот алгоритам така што графот што мора да биде истражен го издвојува во подграф. Овај пристап може да се гледа како [[линеарно програмирање]]: има природна линеарна програма за пресметување на најкратки патеки , и решенијата на [[двојната линеарна програма]] се издволјиви ако и само ако формираат [[евристичка согласнот]]. Ова двојно издвојување / евристичка согласност дефинираат ненегативни намалени "трошоци" и A* суштински работи со намалени "трошоци".

Процесот што го користи Дајкстриниот алгоритам има сличен алчен метод како [[алгоритмот на Прим]]. Примовиот алгоритам бара [[најкратко разгрането дрво]] што ги спојува сите точки во графот; додека Дајкстра бара најкратко растојание помеѓу две точки. Примовиот алгоритам не ја оценува вкупната тежина на графот туку само поединечниот пат.

== Од гледна точка на динамичко програмирање ==

Од гледна точка на [[динамичко програмирање]], Дајкстриниот алгоритам е успешна шема што решава равенка на динамичкото програмирање за најраток пат со таканаречен  '''Метод на достигнување''' .<ref name=sniedovich_06>{{Наведено списание | last = Sniedovich | first = M. | title = Dijkstra’s algorithm revisited: the dynamic programming connexion | journal = Journal of Control and Cybernetics | volume = 35 | issue = 3 | pages = 599–620 | year = 2006 | url = http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf | format = [[PDF]]}} [http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html Online version of the paper with interactive computational modules.]</ref><ref name=denardo_03>{{Наведена книга | last = Denardo | first = E.V. | title = Dynamic Programming: Models and Applications | publisher = [[Dover Publications]] | location = Mineola, NY | year = 2003 | isbn = 978-0-486-42810-9}}</ref><ref name=sniedovich_10>{{Наведена книга | last = Sniedovich | first = M. | title = Dynamic Programming: Foundations and Principles | publisher = [[Francis & Taylor]] | year = 2010 | isbn = 978-0-8247-4099-3  }}</ref>

Всушност, Дајкстриниот алгоритам ја објаснува логиката зад алгоритмот,<ref>{{harvnb|Dijkstra|1959|p=270}}</ref> namely
{{quote|
'''Проблем 2.''' Најдете го најкраткиот пат помеѓу две точки <math>P</math> и <math>Q</math>.

Ние го користиме фактот дека, ако <math>R</math> е точка од минимален пат од <math>P</math> до <math>Q</math>, така што најрактиот пат од <math>P</math> до <math>R</math>.
}}

е парафразирање од [[Richard Bellman|Bellman's]] фамозниот [[Принцип на оптималноста]] во контекст со проблемите за најратки патишта.

== Поврзано ==
{{портал|Информатика}}
* [[Евклидов најкраток пат]]
* [[Проблем на најдолг пат]]

== Наводи ==
{{наводи}}

== Извори ==
* {{Наведено списание | authorlink = Edsger W. Dijkstra | 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  | doi = 10.1007/BF01386390}}
* {{Наведена книга | author1-link = Thomas H. Cormen | first1 = Thomas H. | last1 = Cormen | author2-link = Charles E. Leiserson | first2 = Charles E. | last2 = Leiserson | author3-link = Ronald L. Rivest | first3 = Ronald L. | last3 = Rivest | author4-link = Clifford Stein | first4 = Clifford | last4 = Stein | title = [[Introduction to Algorithms]] | edition = Second | publisher = MIT Press and [[McGraw-Hill]] | year = 2001 | isbn = 0-262-03293-7 | chapter = Section 24.3: Dijkstra's algorithm | pages = 595–601}}
* {{Наведено списание|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=25th Annual Symposium on Foundations of Computer Science|year=1984|publisher=[[IEEE]]|pages=338&ndash;346|url=http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715934|doi=10.1109/SFCS.1984.715934|access-date=2012-08-29|archive-date=2012-10-11|archive-url=https://web.archive.org/web/20121011090757/http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715934|url-status=dead}}
* {{Наведено списание|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=Journal of the Association for Computing Machinery|volume=34|year=1987|pages=596&ndash;615|url=http://portal.acm.org/citation.cfm?id=28874|doi=10.1145/28869.28874|issue=3}}
* {{Наведено списание | first1 = F. Benjamin | last1 = Zhan | first2 = Charles E. | last2 = Noon  | year = 1998 | title = Shortest Path Algorithms: An Evaluation Using Real Road Networks | journal = [[Transportation Science]] | volume = 32 | issue = 1 | pages = 65–73 | doi = 10.1287/trsc.32.1.65}}
* {{Наведена книга|first1=M.|last1=Leyzorek|first2=R. S.|last2=Gray|first3=A. A.|last3=Johnson|first4=W. C.|last4=Ladew|first5=S. R.|last5=Meaker, Jr.|first6=R. M.|last6=Petry|first7=R. N.|last7=Seitz|title=Investigation of Model Techniques &mdash; First Annual Report &mdash; 6 June 1956 &mdash; 1 July 1957 &mdash; A Study of Model Techniques for Communication Systems|publisher=Case Institute of Technology|location=Cleveland, Ohio|year=1957}}

== Надворешни врски ==
{{рв|Dijkstra's algorithm}}
* [http://purl.umn.edu/107247 Oral history interview with Edsger W. Dijkstra],  [[Charles Babbage Institute]] University of Minnesota, Minneapolis.
* [http://www.codeproject.com/KB/recipes/ShortestPathCalculation.aspx Dijkstra's Algorithm in C#]
* [http://www.codeproject.com/KB/recipes/FastHeapDijkstra.aspx   Fast Priority Queue Implementation of Dijkstra's Algorithm in C#]
* [http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html Applet by Carla Laffra of Pace University]
* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html Animation of Dijkstra's algorithm]
* [http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm Visualization of Dijkstra's Algorithm]
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml Shortest Path Problem: Dijkstra's Algorithm] {{Семарх|url=https://web.archive.org/web/20070927234553/http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml |date=2007-09-27 }}
* [http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm Dijkstra's Algorithm Applet]
* [http://code.google.com/p/annas/почетна точкаSource Java Graph package with implementation of Dijkstra's Algorithm]
* [http://bonsaicode.wordpress.com/2011/01/04/programming-praxis-dijkstra’s-algorithm/ Haskell implementation of Dijkstra's Algorithm] on Bonsai code
* [http://algowiki.net/wiki/index.php?title=Dijkstra's_algorithm Java Implementation of Dijkstra's Algorithm] {{Семарх|url=https://web.archive.org/web/20120131232348/http://algowiki.net/wiki/index.php?title=Dijkstra%27s_algorithm |date=2012-01-31 }} on AlgoWiki
* [http://quickgraph.codeplex.com/ QuickGraph, Graph Data Structures and Algorithms for .NET] {{Семарх|url=https://web.archive.org/web/20180121140629/http://quickgraph.codeplex.com/ |date=2018-01-21 }}
* [http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/dijkstra_shortest_paths.html Implementation in Boost C++ library]
* [http://hansolav.net/sql/graphs.html Implementation in T-SQL]
* [http://www.stackframe.com/software/PathFinder A Java library for path finding with Dijkstra's Algorithm and example applet] {{Семарх|url=https://web.archive.org/web/20150307205448/http://www.stackframe.com/software/PathFinder |date=2015-03-07 }}
* [http://www.mathworks.com/matlabcentral/fileexchange/20025-advanced-dijkstras-minimum-path-algorithm A MATLAB program for Dijkstra's algorithm] {{Семарх|url=https://web.archive.org/web/20121218050306/http://www.mathworks.com/matlabcentral/fileexchange/20025-advanced-dijkstras-minimum-path-algorithm |date=2012-12-18 }}
* [http://www.technical-recipes.com/2011/implementing-dijkstra%E2%80%99s-algorithm/ A basic C++ implementation of Dijkstra's algorithm]

[[Категорија:Алгоритми]]
[[Категорија:Комбинаторика]]
[[Категорија:Холандски пронајдоци]]