Дијкстрин алгоритам
Из пројекта Википедија
Дијкстрин алгоритам, који је добио име по холандском информатичару Едсџеру Дијкстри, служи за налажење најкраћег пута у усмереном графу са ненегативним вредностима ивица.
На пример, ако чворове представимо као градове, а вредности ивица као растојања између оних градова који су директно повезани, Дијкстрин алгоритам налази најкраћи пут између два града.
Нека је дат граф тежински усмерени граф 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).
