Back

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




                                     

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

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

                                     

1.1. Алгоритам Опис

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

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

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

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

                                     

1.2. Алгоритам Псеудокод

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

function YenKSP: // Одређивање најкраће путање од извора до понора A; return A;
                                     

1.3. Алгоритам Пример

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

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

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

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

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



                                     

2.1. Особине Просторна сложеност

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

                                     

2.2. Особине Временска сложеност

Временска сложеност зависи од алгоритма за тражење најкраћег пута који се користи у израчунавању споредних путања, па се претпоставља да се користи Дијкстра алгоритам. Дијкстра има временску сложеност најгорег случаја O N 2 {\displaystyle ON^{2}}, али ако се користи Фибоначијев хип оно постаје O M + N log ⁡ N {\displaystyle OM+N\log N}, где је M {\displaystyle M} број грана у графу. Пошто Јенов алгоритам има K {\displaystyle K} позива Дијкстриног алгоритма у рачунању споредних путања, временска сложеност постаје O K N M + N log ⁡ N) {\displaystyle OKNM+N\log N)}.

                                     

3. Унапређења

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

                                     

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

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