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

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

Алгоритам

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

Ознака	Опис
$N$	Величина графа, тј. број чворова у графу.
$(i)$	$i$ -ти чвор графа, где $i$ узима вредности од $1$ до $N$ . Ово значи да је чвор $(1)$ извор, а чвор $(N)$ понор графа.
$d_{ij}$	Цена гране између $(i)$ и $(j)$ , под претпоставком да $(i)\neq (j)$ и $d_{ij}\geq 0$ .
$A^{k}$	$k$ -та најкраћа путања од $(1)$ до $(N)$ , где $k$ иде од $1$ до $K$ . Тада је $A^{k}=(1)-(2^{k})-(3^{k})-\cdots -({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 до H

Овај пример користи Јенов алгоритам да израчуна 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}+KN$ меморије.^[2] У најгорем случају, сваки чвор је повезан са свим осталим и тада нам треба $N^{2}$ меморије. Само $KN$ меморије је потребно за листе $A$ и $B$ , јер се чува највише $K$ путања, максималне дужине $N$ .^[2]

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

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

Унапређења

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

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

Јуџин Лолер је предложио модификацију Јеновог алгоритма у коме се дупликати путања не израчунавају, за разлику од оригиналне идеје, где се они израчунавају, али се потом одбацују када се установи да су дупликати.^[6] Ови дупликати настају када се рачунају споредне путање за чворове из корена од $A^{k}$ . На пример $A^{k}$ одступа од $A^{k-1}$ у неком чвору $(i)$ . Свака споредна путања ${S^{k}}_{j}$ где је $j=0,\ldots ,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}$ .

Референце

^ Yen, Jin Y. (1970). „An algorithm for finding shortest routes from all source nodes to a given destination in general networks”. Quarterly of Applied Mathematics. 27: 526—530. MR 0102435.
^ ^а ^б ^в Yen, Jin Y. (1971). „Finding the k Shortest Loopless Paths in a Network”. Management Science. 17 (11): 712—716.
^ Fredman, Michael Lawrence; Tarjan, Robert E. (1984). „Fibonacci heaps and their uses in improved network optimization algorithms”. 25th Annual Symposium on Foundations of Computer Science. IEEE: 338—346. doi:10.1109/SFCS.1984.715934.
^ Bouillet 2007.
^ Brander, Andrew William; Sinclair, Mark C. A comparative study of k-shortest path algorithms. Department of Electronic Systems Engineering, University of Essex, 1995.
^ Lawler, EL (1972). „A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem.”. Management Science, Theory Series. 18: 401—405.

Литература

Bouillet, Eric (2007). Path routing in mesh optical networks. Chichester, England: John Wiley & Sons. ISBN 9780470032985.
Brander, Andrew William; Sinclair, Mark C. A comparative study of k-shortest path algorithms. Department of Electronic Systems Engineering, University of Essex, 1995.

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

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

[yenksp-1] Yen, Jin Y. (1970). „An algorithm for finding shortest routes from all source nodes to a given destination in general networks”. Quarterly of Applied Mathematics. 27: 526—530. MR 0102435.

[yenksp2-2] а ^б ^в Yen, Jin Y. (1971). „Finding the k Shortest Loopless Paths in a Network”. Management Science. 17 (11): 712—716.

[dijkstra-3] Fredman, Michael Lawrence; Tarjan, Robert E. (1984). „Fibonacci heaps and their uses in improved network optimization algorithms”. 25th Annual Symposium on Foundations of Computer Science. IEEE: 338—346. doi:10.1109/SFCS.1984.715934.

[FOOTNOTEBouillet2007-4] Bouillet 2007.

[5] Brander, Andrew William; Sinclair, Mark C. A comparative study of k-shortest path algorithms. Department of Electronic Systems Engineering, University of Essex, 1995.

[6] Lawler, EL (1972). „A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem.”. Management Science, Theory Series. 18: 401—405.

[1]

[2]

[3]

[4]

[5]

[6]