Дајкстрин алгоритам
From Wikipedia, the free encyclopedia
Remove ads
Дајкстрин алгоритам је један од алгоритама за налажење најкраћег пута у графу са ненегативним тежинама ивица. Име је добио по холандском информатичару Едсхеру Дајкстри.

Нека је дат тежински усмерени граф и почетни чвор из . Ако скуп свих чворова графа обележимо са , скуп ивица са , тада је свака ивица из , представљена паром чворова које она повезује из . Такође, нека свака ивица добије одређену вредност (тежину) . Тежина сваке ивице се може представити као растојање између два чвора које она повезује. Дужина пута између два чвора је сума тежина ивица на том путу. За дати пар чворова и из , Дајкстрин алгоритам налази вредност најкраћег пута. Честа је његова употреба за налажење најкраћег пута од чвора до свих осталих из скупа .
Remove ads
Опис алгоритма
Дајкстрин алгоритам је похлепни алгоритам који се заснива на памћењу вредности тренутног најкраћег пута од за сваки чвор . За почетни чвор та вредност најпре износи 0, тј. , а за остале чворове се узима вредност бесконачно. При престанку рада алгоритма, добија вредност најкраћег пута из у , или вредност бесконачно, уколико такав пут не постоји.

Основна операција Дајкстриног алгоритма је ослобађање ивица: уколико постоји ивица из ка , тада тренутно најкраћи пут из у може добити вредност суме и тежине ивице . Дакле, његова дужина ће износити , уколико је ова вредност мања од . Процес ослобађања ивица се наставља се док вредност не одређује најкраћи пут из у , за сваки чвор .
Током извршавања алгоритма издвајају се два скупа чворова и . У скупу су они чворови за које је позната вредност , а у скупу сви остали. На почетку је скуп празан, а у свакој итерацији један чвор се премешта из у . То је онај чвор који има најмању вредност . На крају се ослобађају све ивице горе описаним поступком.
Remove ads
Псеудокод
У следећем псеудокоду, налази чвор из скупа који има најмању вредност . Тај чвор се избацује из скупа .
1 function Dijkstra(G, w, s) 2 for each vertex v in V[G] // Иницијализација 3 d[v] := infinity 4 previous[v] := undefined 5 d[s] := 0 6 S := empty set 7 Q := V[G] 8 while Q is not an empty set // Дајкстрин алгоритам 9 u := Extract_Min(Q) 10 S := S union {u} 11 for each edge (u,v) outgoing from u 12 if d[u] + w(u,v) < d[v] // Ослобађање ивице (u,v) 13 d[v] := d[u] + w(u,v) 14 Q := Q union {v} 15 previous[v] := u
Ако нас интересује само најкраћи пут између и , претрагу можемо прекинути у реду 9 ако је .
Сада, једноставно можемо одредити најкраћи пут из до :
1 S := empty sequence 2 u := t 3 while defined previous[u] 4 insert u to the beginning of S 5 u := previous[u]
У скупу је садржана листа чворова који се налазе на најкраћем путу из у . Уколико тај пут не постоји, скуп је празан.
Remove ads
Временска сложеност
Временска сложеност Дајкстриног алгоритма над графом са ивицама и чворовима се може изразити у зависности од и .
Код једноставне имплементације чворови из скупа су садржани у низу, а операција захтева само линеарну претрагу за све чворове из скупа . У том случају, временска сложеност износи .
Ефикасније је имплементирати Дајсктрин алгоритам користећи бинарни хип. Тада је временска сложеност .
Види још
Литература
- Dijkstra, E. W. (1959). „A note on two problems in connexion with graphs」 (PDF). Numerische Mathematik. 1: 269—271. doi:10.1007/BF01386390. Архивирано из оригинала (PDF) 23. 01. 2020. г. Приступљено 25. 09. 2013.
- 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 978-0-262-03293-3.
- 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. Архивирано из оригинала 11. 10. 2012. г. Приступљено 25. 09. 2013.
- 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.
- Donald_Knuth, D.E. (1977). „A Generalization of Dijkstra's Algorithm」. Information Processing Letters. 6 (1): 1—5.
Remove ads
Спољашње везе
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads