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

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

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

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

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

Основна операција Дајкстриног алгоритма је ослобађање ивица: уколико постоји ивица из u ка v, тада тренутно најкраћи пут из s у u (d[u]) може добити вредност суме d[v] и тежине ивице (u, v). Дакле, његова дужина ће износити d[u]+w(u, v), уколико је ова вредност мања од d[v]. Процес ослобађања ивица се наставља се док вредност d[v] не одређује најкраћи пут из s у v, за сваки чвор v.

Током извршавања алгоритма издвајају се два скупа чворова S и Q. У скупу S су они чворови за које је позната вредност d[v], а у скупу Q сви остали. На почетку је скуп S празан, а у свакој итерацији један чвор се премешта из Q у S. То је онај чвор који има најмању вредност d[u]. На крају се ослобађају све ивице (u,v) горе описаним поступком.

Псеудокод

У следећем псеудокоду, u := Extract_Min(Q) налази чвор u из скупа Q који има најмању вредност d[u]. Тај чвор се избацује из скупа Q.

 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

Ако нас интересује само најкраћи пут између s и t, претрагу можемо прекинути у реду 9 ако је u = t.

Сада, једноставно можемо одредити најкраћи пут из s до t:

1 S := empty sequence 
2 u := t
3 while defined previous[u]                                        
4       insert u to the beginning of S
5       u := previous[u]

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

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

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

Код једноставне имплементације чворови из скупа Q су садржани у низу, а операција Extract-Min(Q) захтева само линеарну претрагу за све чворове из скупа Q. У том случају, временска сложеност износи O(V²).

Ефикасније је имплементирати Дајсктрин алгоритам користећи бинарни хип. Тада је временска сложеност O(E+V logV).

Види још

Литература

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