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

Алгоритам

уреди

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

уреди
Ознака Опис
  Величина графа, тј. број чворова у графу.
   -ти чвор графа, где   узима вредности од   до  . Ово значи да је чвор   извор, а чвор   понор графа.
  Цена гране између   и  , под претпоставком да   и  .
   -та најкраћа путања од   до  , где   иде од   до  . Тада је  , а   је други чвор  -те најкраће путање,   је трећи чвор  -те најкраће путање, итд.
  Одступајућа путања од   код чвора  , где   иде од   до  . Максимална вредност   је  , који је чвор одмах испред понора у   најкраћој путањи. Ово значи да одступајућа путања не може да одступа од   најкраће путање у понору. Путање   и   прате исти пут до  -тог чвора, где је   грана не припада ни једној путањи у  , и   узима вредности од   до  .
  Коренска путања од   која прати   све до  -тог чвора од  .
  Споредна путања од   која почиње у  -том чвору и завршава се у понору.

Опис

уреди

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

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

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

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

Псеудокод

уреди

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

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 најкраће путање од   to  . Дијкстрин алгоритам је искоршћен да се израчуна најбоља путања од   to  , која је   са ценом од 5. Ова путања је додата у   и постаје прва к-та најкраћа путања,  .

Чвор   од   постаје споредни чвор са коренском путањом сачињеном од самог себе,  . Грана   се уклања, јер се поклапа са коренском путањом и путањом у  . Дијкстра се користи да се израчуна споредна путања   које је  , са ценом 8.   се додају у   као потенцијална к-најкраћа путања.

Чвор   из   постаје споредни чвор са  . Грана   се уклања јер се поклапа са коренском путањом и путањом у  . Дијкстра се користи за израчунавање споредне путање  , која је  , са ценом 7.   се додаје у   као потенцијална к-најкраћа путања.

Чвор   из   постаје споредни чвор са  . Грана   се уклања јер се поклапа са коренском путањом и путањом у  . Дијкстра се користи за израчунавање споредне путање  , која је  , са ценом 8.   се додаје у   као потенцијална к-најкраћа путања.

Од три путање у  ,   је одабрана да постане  , јер има најмању цену од 7. Овај процес се наставља до 3. к-те најкраће путање. Међутим, у трећем понављању, неке споредне путање не постоје, а путања која је одабрана да постане   је  .

Особине

уреди

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

уреди

Да би се чувале гране графа, листа најкраћих путања   и листа потенцијалних најкраћих путања  , потребно је   меморије.[2] У најгорем случају, сваки чвор је повезан са свим осталим и тада нам треба   меморије. Само   меморије је потребно за листе   и  , јер се чува највише   путања, максималне дужине  .[2]

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

уреди

Временска сложеност зависи од алгоритма за тражење најкраћег пута који се користи у израчунавању споредних путања, па се претпоставља да се користи Дијкстра алгоритам. Дијкстра има временску сложеност најгорег случаја  , али ако се користи Фибоначијев хип оно постаје  ,[3] где је   број грана у графу. Пошто Јенов алгоритам има   позива Дијкстриног алгоритма у рачунању споредних путања, временска сложеност постаје  .[4]

Унапређења

уреди

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

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

уреди

Јуџин Лолер је предложио модификацију Јеновог алгоритма у коме се дупликати путања не израчунавају, за разлику од оригиналне идеје, где се они израчунавају, али се потом одбацују када се установи да су дупликати.[6] Ови дупликати настају када се рачунају споредне путање за чворове из корена од  . На пример   одступа од   у неком чвору  . Свака споредна путања   где је  , које се израчуна ће бити дупликат, јер су већ израчунате у   понављању. Због тога, потребно је израчунати само споредне путање за чворове који су део споредне путање од  , тј. само   где   узима вредности од   до  . Да би се ово урадило за  , потребно је негде забележити где се   одвојило од  .

Референце

уреди
  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. 
  2. ^ а б в Yen, Jin Y. (1971). „Finding the k Shortest Loopless Paths in a Network”. Management Science. 17 (11): 712—716. 
  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. 
  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. 

Литература

уреди
  • 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. 

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

уреди