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

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

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

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

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

Дајкстрин алгоритам је похлепни алгоритам који се заснива на памћењу вредности тренутног најкраћег пута од за сваки чвор . За почетни чвор та вредност најпре износи 0, тј. , а за остале чворове се узима вредност бесконачно. При престанку рада алгоритма, добија вредност најкраћег пута из у , или вредност бесконачно, уколико такав пут не постоји.

Дајкстрин алгоритам заснован на еуклидској удаљености.

Основна операција Дајкстриног алгоритма је ослобађање ивица: уколико постоји ивица из ка , тада тренутно најкраћи пут из у може добити вредност суме и тежине ивице . Дакле, његова дужина ће износити , уколико је ова вредност мања од . Процес ослобађања ивица се наставља се док вредност не одређује најкраћи пут из у , за сваки чвор .

Током извршавања алгоритма издвајају се два скупа чворова и . У скупу су они чворови за које је позната вредност , а у скупу сви остали. На почетку је скуп празан, а у свакој итерацији један чвор се премешта из у . То је онај чвор који има најмању вредност . На крају се ослобађају све ивице горе описаним поступком.

Псеудокод

У следећем псеудокоду, налази чвор из скупа који има најмању вредност . Тај чвор се избацује из скупа .

 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]

У скупу је садржана листа чворова који се налазе на најкраћем путу из у . Уколико тај пут не постоји, скуп је празан.

Временска сложеност

Временска сложеност Дајкстриног алгоритма над графом са ивицама и чворовима се може изразити у зависности од и .

Код једноставне имплементације чворови из скупа су садржани у низу, а операција захтева само линеарну претрагу за све чворове из скупа . У том случају, временска сложеност износи .

Ефикасније је имплементирати Дајсктрин алгоритам користећи бинарни хип. Тада је временска сложеност .

Види још

• Флојд-Воршалов алгоритам
• А* алгоритам

Литература

• 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.

Спољашње везе

• Анимација рада Дајкстриног алгоритма
• Имплементација Дајсктриног алгоритма