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

From Wikipedia, the free encyclopedia

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

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

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

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

Remove ads

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

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

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

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

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

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

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

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

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

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

Види још

Литература

Remove ads

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

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads