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

Дајкстрин алгоритам
Класа	пребарувачки алгоритам
Структура на податоци	граф
Најлош случај

Дајкстрин алгоритам — вид пребарувачки алгоритам во граф што може да реши еден проблем во вид на најкраток пат во даден граф со ненегативни вредности (тежини) на гранките на еден граф (растојанието од една до друга точка претставува гранка), така што алгоритмот продуцира дрво со најкраток пат. Осмислен е од холанѓанскиот компјутерски научник Едгсер Дајкстра во 1956 година и објавен во 1959 г.

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

Функцијата на алгоритмот

Илустрација на Дајкстриниот алгоритам како изгледа пребарување на најкраток пат од почетна точка до крајна точка.

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

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

Опис на алгоритмот

Забелешка: За полесно разбирање на алгоритмот, ова дискусија користи термини како пресек,пат и мапа – инаку, овие термини се точки, гранки, кои образуваат еден вид на граф.

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

Псевдокод

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

 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      врати растојание;

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

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

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

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

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

Горната границата на времето на извршување на алгоритмот со гранки $E$ и точки $V$ можеме да ја прикажиме како функција од $|E|$ и $|V|$ со користење на Голема-O ознака.

За секоја имплементација од сетот на точки $Q$ времето на извршување е $O(|E|\cdot dk_{Q}+|V|\cdot em_{Q})$ , каде $dk_{Q}$ и $em_{Q}$ се времињата потребни да се намали клучот и да се извршат минимум операции во сетот $Q$ , соодвнетно.

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

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

Забелешка дека во Директен ацикличен граф, можно е да се најде најкраток пат од почетна точка до крајна точка во линеарно време, со обработка на точките во тополошки ред, и пресметување на најкраткиот пат за секоја точка да има најмала должина добиена од некој од следните гранки.^[1]

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

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

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

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

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

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

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

Од гледна точка на динамичко програмирање, Дајкстриниот алгоритам е успешна шема што решава равенка на динамичкото програмирање за најраток пат со таканаречен Метод на достигнување .^[2]^[3]^[4]

Всушност, Дајкстриниот алгоритам ја објаснува логиката зад алгоритмот,^[5] namely

Проблем 2. Најдете го најкраткиот пат помеѓу две точки $P$ и $Q$ .
Ние го користиме фактот дека, ако $R$ е точка од минимален пат од $P$ до $Q$ , така што најрактиот пат од $P$ до $R$ .

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

Поврзано

Наводи

↑ http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html
↑ Sniedovich, M. (2006). „Dijkstra's algorithm revisited: the dynamic programming connexion“ (PDF). Journal of Control and Cybernetics. 35 (3): 599–620. Online version of the paper with interactive computational modules.
↑ Denardo, E.V. (2003). Dynamic Programming: Models and Applications. Mineola, NY: Dover Publications. ISBN 978-0-486-42810-9.
↑ Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles. Francis & Taylor. ISBN 978-0-8247-4099-3.
↑ Dijkstra 1959, стр. 270

Извори

Dijkstra, E. W. (1959). „A note on two problems in connexion with graphs“ (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „Section 24.3: Dijkstra's algorithm“. Introduction to Algorithms (Second. изд.). MIT Press and McGraw-Hill. стр. 595–601. ISBN 0-262-03293-7.
Fredman, Michael Lawrence; Tarjan, Robert E. (1984). „Fibonacci heaps and their uses in improved network optimization algorithms“. 25th Annual Symposium on Foundations of Computer Science. IEEE: 338–346. doi:10.1109/SFCS.1984.715934. Архивирано од изворникот на 2012-10-11. Посетено на 2012-08-29.
Fredman, Michael Lawrence; Tarjan, Robert E. (1987). „Fibonacci heaps and their uses in improved network optimization algorithms“. Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874.
Zhan, F. Benjamin; Noon, Charles E. (1998). „Shortest Path Algorithms: An Evaluation Using Real Road Networks“. Transportation Science. 32 (1): 65–73. doi:10.1287/trsc.32.1.65.
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.

Надворешни врски

Oral history interview with Edsger W. Dijkstra, Charles Babbage Institute University of Minnesota, Minneapolis.
Dijkstra's Algorithm in C#
Fast Priority Queue Implementation of Dijkstra's Algorithm in C#
Applet by Carla Laffra of Pace University
Animation of Dijkstra's algorithm
Visualization of Dijkstra's Algorithm
Shortest Path Problem: Dijkstra's Algorithm Архивирано на 27 септември 2007 г.
Dijkstra's Algorithm Applet
точкаSource Java Graph package with implementation of Dijkstra's Algorithm
Haskell implementation of Dijkstra's Algorithm on Bonsai code
Java Implementation of Dijkstra's Algorithm Архивирано на 31 јануари 2012 г. on AlgoWiki
QuickGraph, Graph Data Structures and Algorithms for .NET Архивирано на 21 јануари 2018 г.
Implementation in Boost C++ library
Implementation in T-SQL
A Java library for path finding with Dijkstra's Algorithm and example applet Архивирано на 7 март 2015 г.
A MATLAB program for Dijkstra's algorithm Архивирано на 18 декември 2012 г.
A basic C++ implementation of Dijkstra's algorithm

[1] ttp://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html

[sniedovich_06-2] Sniedovich, M. (2006). „Dijkstra's algorithm revisited: the dynamic programming connexion“ (PDF). Journal of Control and Cybernetics. 35 (3): 599–620. Online version of the paper with interactive computational modules.

[denardo_03-3] Denardo, E.V. (2003). Dynamic Programming: Models and Applications. Mineola, NY: Dover Publications. ISBN 978-0-486-42810-9.

[sniedovich_10-4] Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles. Francis & Taylor. ISBN 978-0-8247-4099-3.

[5] Dijkstra 1959, стр. 270

[1]

[2]

[3]

[4]

[5]