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

Од Википедија, слободната енциклопедија
Прејди на: содржини, барај
Алгоритам на Дајкстра
Dijkstra Animation.gif
Класа Пребарувачки алгоритам
Структура на податоци Граф
Најлош случај O(|E| + |V| \log|V|)

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

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

Функцијата на алгоритмот[уреди]

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

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

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

Опис на алгоритмот[уреди]

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

Да претпоставиме дека сакаме да најдиме најкраток пат помеѓу два пресеци во Скопје, и имаме почетна точка и крајна точка т.е дестинацијата до која сакаме да најдиме најкраток пат. Почнуваме од почетната точка, и почетната точка има вредност 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 фамозниот Принцип на оптималноста во контекст со проблемите за најратки патови.

Поврзано[уреди]

Портал „Информатика

Наводи[уреди]

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

Извори[уреди]

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