Jenov alogritam

Jenov algoritam računa K-najkraćih putanja bez ciklova u grafu sa jednim izvorom i ne-negativnim cenama grana.^[1] Algoritam je objavljen 1971. od strane Đin J. Jena i koristi bilo koji algoritam za traženje najkraćeg puta u grafu da pronađe najbolju putanju, a zatim nastavlja da pronađe K-1 odstupanja od najbolje putanje.^[2]

Algoritam

Terminologija i oznake

Oznaka	Opis
$N$	Veličina grafa, tj. broj čvorova u grafu.
$(i)$	$i$ -ti čvor grafa, gde $i$ uzima vrednosti od $1$ do $N$ . Ovo znači da je čvor $(1)$ izvor, a čvor $(N)$ ponor grafa.
$d_{ij}$	Cena grane između $(i)$ i $(j)$ , pod pretpostavkom da $(i)\neq (j)$ i $d_{ij}\geq 0$ .
$A^{k}$	$k$ -ta najkraća putanja od $(1)$ do $(N)$ , gde $k$ ide od $1$ do $K$ . Tada je $A^{k}=(1)-(2^{k})-(3^{k})-\cdots -({Q^{k}}_{k})-(N)$ , a $(2^{k})$ je drugi čvor $k$ -te najkraće putanje, $(3^{k})$ je treći čvor $k$ -te najkraće putanje, itd.
${A^{k}}_{i}$	Odstupajuća putanja od $A^{k-1}$ kod čvora $(i)$ , gde $i$ ide od $1$ do $Q_{k}$ . Maksimalna vrednost $i$ je $Q_{k}$ , koji je čvor odmah ispred ponora u $k$ najkraćoj putanji. Ovo znači da odstupajuća putanja ne može da odstupa od $k-1$ najkraće putanje u ponoru. Putanje $A^{k}$ i $A^{k-1}$ prate isti put do $i$ -tog čvora, gde je $(i)^{k}-(i+1)^{k}$ grana ne pripada ni jednoj putanji u $A^{j}$ , i $j$ uzima vrednosti od $1$ do $k-1$ .
${R^{k}}_{i}$	Korenska putanja od ${A^{k}}_{i}$ koja prati $A^{k-1}$ sve do $i$ -tog čvora od $A^{k-1}$ .
${S^{k}}_{i}$	Sporedna putanja od ${A^{k}}_{i}$ koja počinje u $i$ -tom čvoru i završava se u ponoru.

Opis

Algoritam se može podeliti na dva dela, određivanje prve k-najkraće putanje, $A^{1}$ , a zatim, određivanje svih ostalih k-najkraćih putanja. Da bismo odredili $A^{1}$ , najkraću putanju od izvora do ponora, možemo iskoristiti bilo koji efikasni algoritam za traženje najkraćeg puta u grafu.

Da bismo pronašli $A^{k}$ , gde $k$ uzima vrednosti od $2$ do $K$ , algoritam pretpostavlja da su sve putanje od $A^{1}$ do $A^{k-1}$ prethodno pronađene. $k$ -to ponavljanje može biti podeljeno na dva postupka, pronalaženje svih odstupanja ${A^{k}}_{i}$ i odabir najkraćeg koji će postati $A^{k}$ . Obratite pažnju da u ovom ponavljanju $i$ uzima vrednosti od $1$ do ${Q^{k}}_{k}$ .

Prvi postupak se može dodatno podeliti na tri operacije: pronalaženje ${R^{k}}_{i}$ , pronalaženje ${S^{k}}_{i}$ , a zatim dodavanje ${A^{k}}_{i}$ u spremište $B$ . Korenska putanja, ${R^{k}}_{i}$ , se odabira traženjem potputanje u $A^{k-1}$ koja prati prvih $i$ čvorova od $A^{j}$ , gde $j$ uzima vrednosti od $1$ do $k-1$ . Onda, ako je putanja pronađena, cena grane $d_{i(i+1)}$ od $A^{j}$ se postavlja na beskonačno. Sledeće, sporedna putanja, ${S^{k}}_{i}$ , se pronalazi tako što se računa najkraća putanja od sporednog čvora $i$ do ponora. Odstranjivanje prethodno korištenih grana od $(i)$ do $(i+1)$ osigurava nam da je sporedna putanja različita. ${A^{k}}_{i}={R^{k}}_{i}+{S^{k}}_{i}$ , zbir korenske putanje i sporedne putanje, se dodaje u $B$ . Sledeće, grane koje su uklonjene, tj. čija cena je bila postavljen na beskonačno, se vraćaju u prvobitno stanje.

Drugi postupak određuje odgovarajuću putanju za $A^{k}$ , tako što pronalazi putanju u spremištu $B$ sa najmanjom cenom. Ova putanja se uklanja iz $B$ i ubacuje u $A$ i algoritam nastavlja sa sledećim korakom. Ako je broj putanji u $B$ jednak ili veći od broja k-najkraćih putanja koje još treba pronaći, onda se tražene putanje iz $B$ dodaju u $A$ i algoritam se završava.

Pseudokod

Algoritam pretpostavlja da se koristi Dijkstra algoritam za traženje najkraćih putanja između dva čvora, ali se može iskoristiti i neki drugi algoritam.

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;

Primer

Jenov algoritam, K=3, C do H

Ovaj primer koristi Jenov algoritam da izračuna 3 najkraće putanje od $(C)$ to $(H)$ . Dijkstrin algoritam je iskoršćen da se izračuna najbolja putanja od $(C)$ to $(H)$ , koja je $(C)-(E)-(F)-(H)$ sa cenom od 5. Ova putanja je dodata u $A$ i postaje prva k-ta najkraća putanja, $A^{1}$ .

Čvor $(C)$ od $A^{1}$ postaje sporedni čvor sa korenskom putanjom sačinjenom od samog sebe, ${R^{2}}_{1}=(C)$ . Grana $(C)-(E)$ se uklanja, jer se poklapa sa korenskom putanjom i putanjom u $A$ . Dijkstra se koristi da se izračuna sporedna putanja ${S^{2}}_{1}$ koje je $(C)-(D)-(F)-(H)$ , sa cenom 8. ${A^{2}}_{1}={R^{2}}_{1}+{S^{2}}_{1}=(C)-(D)-(F)-(H)$ se dodaju u $B$ kao potencijalna k-najkraća putanja.

Čvor $(E)$ iz $A^{1}$ postaje sporedni čvor sa ${R^{2}}_{2}=(C)-(E)$ . Grana $(E)-(F)$ se uklanja jer se poklapa sa korenskom putanjom i putanjom u $A$ . Dijkstra se koristi za izračunavanje sporedne putanje ${S^{2}}_{2}$ , koja je $(E)-(G)-(H)$ , sa cenom 7. ${A^{2}}_{2}={R^{2}}_{2}+{S^{2}}_{2}=(C)-(E)-(G)-(H)$ se dodaje u $B$ kao potencijalna k-najkraća putanja.

Čvor $(F)$ iz $A^{1}$ postaje sporedni čvor sa ${R^{2}}_{3}=(C)-(E)-(F)$ . Grana $(F)-(H)$ se uklanja jer se poklapa sa korenskom putanjom i putanjom u $A$ . Dijkstra se koristi za izračunavanje sporedne putanje ${S^{2}}_{3}$ , koja je $(F)-(G)-(H)$ , sa cenom 8. ${A^{2}}_{3}={R^{2}}_{3}+{S^{2}}_{3}=(C)-(E)-(F)-(G)-(H)$ se dodaje u $B$ kao potencijalna k-najkraća putanja.

Od tri putanje u $B$ , ${A^{2}}_{2}$ je odabrana da postane $A^{2}$ , jer ima najmanju cenu od 7. Ovaj proces se nastavlja do 3. k-te najkraće putanje. Međutim, u trećem ponavljanju, neke sporedne putanje ne postoje, a putanja koja je odabrana da postane $A^{3}$ je $(C)-(E)-(F)-(G)-(H)$ .

Osobine

Prostorna složenost

Da bi se čuvale grane grafa, lista najkraćih putanja $A$ i lista potencijalnih najkraćih putanja $B$ , potrebno je $N^{2}+KN$ memorije.^[2] U najgorem slučaju, svaki čvor je povezan sa svim ostalim i tada nam treba $N^{2}$ memorije. Samo $KN$ memorije je potrebno za liste $A$ i $B$ , jer se čuva najviše $K$ putanja, maksimalne dužine $N$ .^[2]

Vremenska složenost

Vremenska složenost zavisi od algoritma za traženje najkraćeg puta koji se koristi u izračunavanju sporednih putanja, pa se pretpostavlja da se koristi Dijkstra algoritam. Dijkstra ima vremensku složenost najgoreg slučaja $O(N^{2})$ , ali ako se koristi Fibonačijev hip ono postaje $O(M+N\log N)$ ,^[3] gde je $M$ broj grana u grafu. Pošto Jenov algoritam ima $K$ poziva Dijkstrinog algoritma u računanju sporednih putanja, vremenska složenost postaje $O(KN(M+N\log N))$ .^[4]

Unapređenja

Jenov algoritam može biti unapređen korišćenjem hipa za čuvanje potencijalnih k-najkraćih putanja u listi $B$ . Korišćenjem hipa umesto liste će se poboljšati brzina, ali ne i složenost.^[5] Jedan od načina za blago smanjenje složenosti je da se preskoče čvorovi koji nemaju sporedne putanje. Ovaj slučaj nastaje kada su sve sporedne putanje iz nekog sporednog čvora iskorišćene u prethodnom $A^{k}$ . Takođe, ako $B$ ima $K-k$ putanja minimalne dužine, u vezi sa putanjama u $A$ , onda ih možemo ubaciti u $A$ , jer više nijedna putanja neće biti kraća.

Lolerovo unapređenje

Judžin Loler je predložio modifikaciju Jenovog algoritma u kome se duplikati putanja ne izračunavaju, za razliku od originalne ideje, gde se oni izračunavaju, ali se potom odbacuju kada se ustanovi da su duplikati.^[6] Ovi duplikati nastaju kada se računaju sporedne putanje za čvorove iz korena od $A^{k}$ . Na primer $A^{k}$ odstupa od $A^{k-1}$ u nekom čvoru $(i)$ . Svaka sporedna putanja ${S^{k}}_{j}$ gde je $j=0,\ldots ,i$ , koje se izračuna će biti duplikat, jer su već izračunate u $k-1$ ponavljanju. Zbog toga, potrebno je izračunati samo sporedne putanje za čvorove koji su deo sporedne putanje od $A^{k-1}$ , tj. samo ${S^{k}}_{h}$ gde $h$ uzima vrednosti od $(i+1)^{k-1}$ do $(Q_{k})^{k-1}$ . Da bi se ovo uradilo za $A^{k}$ , potrebno je negde zabeležiti gde se $A^{k-1}$ odvojilo od $A^{k-2}$ .

Reference

^ 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.
^ ^a ^b ^v 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.

Literatura

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.

Spoljašnje veze

Pajton implementacija otvorenog koda na GitHub strani
C++ implementacija otvorenog koda na Google Code strani

[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] v 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]