мини|Демо за Дајкстрин алгоритам Дајкстрин алгоритам је један од алгоритама за налажење најкраћег пута у графу са ненегативним тежинама ивица. Име је добио по холандском информатичару Едсхеру Дајкстри.
Нека је дат тежински усмерени граф -{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)}-.
Види још Флојд-Воршалов алгоритам А* алгоритам
Литература
Спољашње везе
Анимација рада Дајкстриног алгоритма Имплементација Дајсктриног алгоритма
Категорија:Графовски алгоритми Категорија:Едсгер Дајкстра