Јенов алогритам

Јенов алгоритам рачуна К-најкраћих путања без циклова у графу са једним извором и не-негативним ценама грана.^[1] Алгоритам је објављен 1971. од стране Ђин Ј. Јена и користи било који алгоритам за тражење најкраћег пута у графу да пронађе најбољу путању, а затим наставља да пронађе К-1 одступања од најбоље путање.^[2]

Алгоритам

Терминологија и ознаке

Ознака	Опис
$N$	Величина графа, тј. број чворова у графу.
$(i)$	$i$ -ти чвор графа, где $i$ узима вредности од $1$ до $N$ . Ово значи да је чвор $(1)$ извор, а чвор $(N)$ понор графа.
$d_{i j}$	Цена гране између $(i)$ и $(j)$ , под претпоставком да $(i) \neq (j)$ и $d_{i j} \geq 0$ .
$A^{k}$	$k$ -та најкраћа путања од $(1)$ до $(N)$ , где $k$ иде од $1$ до $K$ . Тада је $A^{k} = (1) - (2^{k}) - (3^{k}) - \dots - ({Q^{k}}_{k}) - (N)$ , а $(2^{k})$ је други чвор $k$ -те најкраће путање, $(3^{k})$ је трећи чвор $k$ -те најкраће путање, итд.
${A^{k}}_{i}$	Одступајућа путања од $A^{k - 1}$ код чвора $(i)$ , где $i$ иде од $1$ до $Q_{k}$ . Максимална вредност $i$ је $Q_{k}$ , који је чвор одмах испред понора у $k$ најкраћој путањи. Ово значи да одступајућа путања не може да одступа од $k - 1$ најкраће путање у понору. Путање $A^{k}$ и $A^{k - 1}$ прате исти пут до $i$ -тог чвора, где је $(i)^{k} - (i + 1)^{k}$ грана не припада ни једној путањи у $A^{j}$ , и $j$ узима вредности од $1$ до $k - 1$ .
${R^{k}}_{i}$	Коренска путања од ${A^{k}}_{i}$ која прати $A^{k - 1}$ све до $i$ -тог чвора од $A^{k - 1}$ .
${S^{k}}_{i}$	Споредна путања од ${A^{k}}_{i}$ која почиње у $i$ -том чвору и завршава се у понору.

Опис

Алгоритам се може поделити на два дела, одређивање прве к-најкраће путање, $A^{1}$ , а затим, одређивање свих осталих к-најкраћих путања. Да бисмо одредили $A^{1}$ , најкраћу путању од извора до понора, можемо искористити било који ефикасни алгоритам за тражење најкраћег пута у графу.

Да бисмо пронашли $A^{k}$ , где $k$ узима вредности од $2$ до $K$ , алгоритам претпоставља да су све путање од $A^{1}$ до $A^{k - 1}$ претходно пронађене. $k$ -то понављање може бити подељено на два поступка, проналажење свих одступања ${A^{k}}_{i}$ и одабир најкраћег који ће постати $A^{k}$ . Обратите пажњу да у овом понављању $i$ узима вредности од $1$ до ${Q^{k}}_{k}$ .

Први поступак се може додатно поделити на три операције: проналажење ${R^{k}}_{i}$ , проналажење ${S^{k}}_{i}$ , а затим додавање ${A^{k}}_{i}$ у спремиште $B$ . Коренска путања, ${R^{k}}_{i}$ , се одабира тражењем потпутање у $A^{k - 1}$ која прати првих $i$ чворова од $A^{j}$ , где $j$ узима вредности од $1$ до $k - 1$ . Онда, ако је путања пронађена, цена гране $d_{i (i + 1)}$ од $A^{j}$ се поставља на бесконачно. Следеће, споредна путања, ${S^{k}}_{i}$ , се проналази тако што се рачуна најкраћа путања од споредног чвора $i$ до понора. Одстрањивање претходно кориштених грана од $(i)$ до $(i + 1)$ осигурава нам да је споредна путања различита. ${A^{k}}_{i} = {R^{k}}_{i} + {S^{k}}_{i}$ , збир коренске путање и споредне путање, се додаје у $B$ . Следеће, гране које су уклоњене, тј. чија цена је била постављен на бесконачно, се враћају у првобитно стање.

Други поступак одређује одговарајућу путању за $A^{k}$ , тако што проналази путању у спремишту $B$ са најмањом ценом. Ова путања се уклања из $B$ и убацује у $A$ и алгоритам наставља са следећим кораком. Ако је број путањи у $B$ једнак или већи од броја к-најкраћих путања које још треба пронаћи, онда се тражене путање из $B$ додају у $A$ и алгоритам се завршава.

Псеудокод

Алгоритам претпоставља да се користи Дијкстра алгоритам за тражење најкраћих путања између два чвора, али се може искористити и неки други алгоритам.

function YenKSP(Graph, source, sink, K):
   // Одређивање најкраће путање од извора до понора
   A[0] = Dijkstra(Graph, source, sink);
   // Иницијализујемо хип у коме чувамо потенцијалну к-ту најкраћу путању
   B = [];
   
   for k from 1 to K:
       // Споредни чвор је из опсега од првог од претпоследњег у најкраћој путањи
       for i from 0 to size(A[k − 1]) − 1:
           
           // Споредни чвор се узима преходне к-најкраће путање, k − 1.
           spurNode = A[k-1].node(i);
           // Низ чворова од извора до споредног чвора претходне к-најкраће путање
           rootPath = A[k-1].nodes(0, i);
           
           for each path p in A:
               if rootPath == p.nodes(0, i):
                   // Уклонити везе које су део претходне најкраће путање које деле исту коренску путању
                   remove p.edge(i, i + 1) from Graph;
           
           // Израчунати споредну путању од споредног чвора до понора
           spurPath = Dijkstra(Graph, spurNode, sink);
           
           // Цела путања настаје спајање коренске путање и споредне путање
           totalPath = rootPath + spurPath;
           // Додати потензијалну к-најкраћу путању на хип
           B.append(totalPath);
           
           // Вратити гране које су уклоњене из графа
           restore edges to Graph;
       
       // Сортирати потенцијалне к-најкраће путање по цени.
       B.sort();
       // Путања најмање цене постаје к-та најкраћа путања
       A[k] = B[0];
   
   return A;

Пример

Овај пример користи Јенов алгоритам да израчуна 3 најкраће путање од $(C)$ to $(H)$ . Дијкстрин алгоритам је искоршћен да се израчуна најбоља путања од $(C)$ to $(H)$ , која је $(C) - (E) - (F) - (H)$ са ценом од 5. Ова путања је додата у $A$ и постаје прва к-та најкраћа путања, $A^{1}$ .

Чвор $(C)$ од $A^{1}$ постаје споредни чвор са коренском путањом сачињеном од самог себе, ${R^{2}}_{1} = (C)$ . Грана $(C) - (E)$ се уклања, јер се поклапа са коренском путањом и путањом у $A$ . Дијкстра се користи да се израчуна споредна путања ${S^{2}}_{1}$ које је $(C) - (D) - (F) - (H)$ , са ценом 8. ${A^{2}}_{1} = {R^{2}}_{1} + {S^{2}}_{1} = (C) - (D) - (F) - (H)$ се додају у $B$ као потенцијална к-најкраћа путања.

Чвор $(E)$ из $A^{1}$ постаје споредни чвор са ${R^{2}}_{2} = (C) - (E)$ . Грана $(E) - (F)$ се уклања јер се поклапа са коренском путањом и путањом у $A$ . Дијкстра се користи за израчунавање споредне путање ${S^{2}}_{2}$ , која је $(E) - (G) - (H)$ , са ценом 7. ${A^{2}}_{2} = {R^{2}}_{2} + {S^{2}}_{2} = (C) - (E) - (G) - (H)$ се додаје у $B$ као потенцијална к-најкраћа путања.

Чвор $(F)$ из $A^{1}$ постаје споредни чвор са ${R^{2}}_{3} = (C) - (E) - (F)$ . Грана $(F) - (H)$ се уклања јер се поклапа са коренском путањом и путањом у $A$ . Дијкстра се користи за израчунавање споредне путање ${S^{2}}_{3}$ , која је $(F) - (G) - (H)$ , са ценом 8. ${A^{2}}_{3} = {R^{2}}_{3} + {S^{2}}_{3} = (C) - (E) - (F) - (G) - (H)$ се додаје у $B$ као потенцијална к-најкраћа путања.

Од три путање у $B$ , ${A^{2}}_{2}$ је одабрана да постане $A^{2}$ , јер има најмању цену од 7. Овај процес се наставља до 3. к-те најкраће путање. Међутим, у трећем понављању, неке споредне путање не постоје, а путања која је одабрана да постане $A^{3}$ је $(C) - (E) - (F) - (G) - (H)$ .

Особине

Просторна сложеност

Да би се чувале гране графа, листа најкраћих путања $A$ и листа потенцијалних најкраћих путања $B$ , потребно је $N^{2} + K N$ меморије.^[2] У најгорем случају, сваки чвор је повезан са свим осталим и тада нам треба $N^{2}$ меморије. Само $K N$ меморије је потребно за листе $A$ и $B$ , јер се чува највише $K$ путања, максималне дужине $N$ .^[2]

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

Временска сложеност зависи од алгоритма за тражење најкраћег пута који се користи у израчунавању споредних путања, па се претпоставља да се користи Дијкстра алгоритам. Дијкстра има временску сложеност најгорег случаја $O (N^{2})$ , али ако се користи Фибоначијев хип оно постаје $O (M + N \log N)$ ,^[3] где је $M$ број грана у графу. Пошто Јенов алгоритам има $K$ позива Дијкстриног алгоритма у рачунању споредних путања, временска сложеност постаје $O (K N (M + N \log N))$ .Шаблон:Sfn

Унапређења

Јенов алгоритам може бити унапређен коришћењем хипа за чување потенцијалних к-најкраћих путања у листи $B$ . Коришћењем хипа уместо листе ће се побољшати брзина, али не и сложеност.^[4] Један од начина за благо смањење сложености је да се прескоче чворови који немају споредне путање. Овај случај настаје када су све споредне путање из неког споредног чвора искоришћене у претходном $A^{k}$ . Такође, ако $B$ има $K - k$ путања минималне дужине, у вези са путањама у $A$ , онда их можемо убацити у $A$ , јер више ниједна путања неће бити краћа.

Лолерово унапређење

Јуџин Лолер је предложио модификацију Јеновог алгоритма у коме се дупликати путања не израчунавају, за разлику од оригиналне идеје, где се они израчунавају, али се потом одбацују када се установи да су дупликати.^[5] Ови дупликати настају када се рачунају споредне путање за чворове из корена од $A^{k}$ . На пример $A^{k}$ одступа од $A^{k - 1}$ у неком чвору $(i)$ . Свака споредна путања ${S^{k}}_{j}$ где је $j = 0, \dots, i$ , које се израчуна ће бити дупликат, јер су већ израчунате у $k - 1$ понављању. Због тога, потребно је израчунати само споредне путање за чворове који су део споредне путање од $A^{k - 1}$ , тј. само ${S^{k}}_{h}$ где $h$ узима вредности од $(i + 1)^{k - 1}$ до $(Q_{k})^{k - 1}$ . Да би се ово урадило за $A^{k}$ , потребно је негде забележити где се $A^{k - 1}$ одвојило од $A^{k - 2}$ .

Референце

Шаблон:Reflist

Литература

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

Пајтон имплементација отвореног кода на GitHub страни
C++ имплементација отвореног кода на Google Code страни

Шаблон:Нормативна контрола

[yenksp-1] Шаблон:Cite journal

[yenksp2-2] 2,0 ^2,1 ^2,2 Шаблон:Cite journal

[dijkstra-3] Шаблон:Cite journal

[4] Шаблон:Cite book

[5] Шаблон:Cite journal

[1]

[2]

[3]

[4]

[5]

Јенов алогритам

Садржај

Алгоритам

Терминологија и ознаке

Опис

Псеудокод

Пример

Особине

Просторна сложеност

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

Унапређења

Лолерово унапређење

Референце

Литература

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

Мени за навигацију

Јенов алогритам

Алгоритам

Терминологија и ознаке

Опис

Псеудокод

Пример

Особине

Просторна сложеност

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

Унапређења

Лолерово унапређење

Референце

Литература

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

Мени за навигацију

Претрага