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

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

Нека је дат тежински усмерени граф 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(V2).

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

Види још

уреди

Литература

уреди

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

уреди