Јенов алгоритам рачуна К-најкраћих путања без циклова у графу са једним извором и не-негативним ценама грана. Алгоритам је објављен 1971. од стране Ђин Ј. Јена и користи било који алгоритам за тражење најкраћег пута у графу да пронађе најбољу путању, а затим наставља да пронађе К-1 одступања од најбоље путање.
Алгоритам Терминологија и ознаке Ознака Опис Величина графа, тј. број чворова у графу. -ти чвор графа, где узима вредности од до . Ово значи да је чвор извор, а чвор понор графа. Цена гране између и , под претпоставком да и . -та најкраћа путања од до , где иде од до . Тада је , а је други чвор -те најкраће путање, је трећи чвор -те најкраће путање, итд. Одступајућа путања од код чвора , где иде од до . Максимална вредност је , који је чвор одмах испред понора у најкраћој путањи. Ово значи да одступајућа путања не може да одступа од најкраће путање у понору. Путање и прате исти пут до -тог чвора, где је грана не припада ни једној путањи у , и узима вредности од до . Коренска путања од која прати све до -тог чвора од . Споредна путања од која почиње у -том чвору и завршава се у понору.
Опис Алгоритам се може поделити на два дела, одређивање прве к-најкраће путање, , а затим, одређивање свих осталих к-најкраћих путања. Да бисмо одредили , најкраћу путању од извора до понора, можемо искористити било који ефикасни алгоритам за тражење најкраћег пута у графу.
Да бисмо пронашли , где узима вредности од до , алгоритам претпоставља да су све путање од до претходно пронађене. -то понављање може бити подељено на два поступка, проналажење свих одступања и одабир најкраћег који ће постати . Обратите пажњу да у овом понављању узима вредности од до .
Први поступак се може додатно поделити на три операције: проналажење , проналажење , а затим додавање у спремиште . Коренска путања, , се одабира тражењем потпутање у која прати првих чворова од , где узима вредности од до . Онда, ако је путања пронађена, цена гране од се поставља на бесконачно. Следеће, споредна путања, , се проналази тако што се рачуна најкраћа путања од споредног чвора до понора. Одстрањивање претходно кориштених грана од до осигурава нам да је споредна путања различита. , збир коренске путање и споредне путање, се додаје у . Следеће, гране које су уклоњене, тј. чија цена је била постављен на бесконачно, се враћају у првобитно стање.
Други поступак одређује одговарајућу путању за , тако што проналази путању у спремишту са најмањом ценом. Ова путања се уклања из и убацује у и алгоритам наставља са следећим кораком. Ако је број путањи у једнак или већи од броја к-најкраћих путања које још треба пронаћи, онда се тражене путање из додају у и алгоритам се завршава.
Псеудокод Алгоритам претпоставља да се користи Дијкстра алгоритам за тражење најкраћих путања између два чвора, али се може искористити и неки други алгоритам.
function YenKSP(Graph, source, sink, K): // Одређивање најкраће путање од извора до понора A = 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;
return A;
Пример центар|Јенов алгоритам, К=3, C до H Овај пример користи Јенов алгоритам да израчуна 3 најкраће путање од to . Дијкстрин алгоритам је искоршћен да се израчуна најбоља путања од to , која је са ценом од 5. Ова путања је додата у и постаје прва к-та најкраћа путања, .
Чвор од постаје споредни чвор са коренском путањом сачињеном од самог себе, . Грана се уклања, јер се поклапа са коренском путањом и путањом у . Дијкстра се користи да се израчуна споредна путања које је , са ценом 8. се додају у као потенцијална к-најкраћа путања.
Чвор из постаје споредни чвор са . Грана се уклања јер се поклапа са коренском путањом и путањом у . Дијкстра се користи за израчунавање споредне путање , која је , са ценом 7. се додаје у као потенцијална к-најкраћа путања.
Чвор из постаје споредни чвор са . Грана се уклања јер се поклапа са коренском путањом и путањом у . Дијкстра се користи за израчунавање споредне путање , која је , са ценом 8. се додаје у као потенцијална к-најкраћа путања.
Од три путање у , је одабрана да постане , јер има најмању цену од 7. Овај процес се наставља до 3. к-те најкраће путање. Међутим, у трећем понављању, неке споредне путање не постоје, а путања која је одабрана да постане је .
Особине Просторна сложеност Да би се чувале гране графа, листа најкраћих путања и листа потенцијалних најкраћих путања , потребно је меморије. У најгорем случају, сваки чвор је повезан са свим осталим и тада нам треба меморије. Само меморије је потребно за листе и , јер се чува највише путања, максималне дужине .
Временска сложеност Временска сложеност зависи од алгоритма за тражење најкраћег пута који се користи у израчунавању споредних путања, па се претпоставља да се користи Дијкстра алгоритам. Дијкстра има временску сложеност најгорег случаја , али ако се користи Фибоначијев хип оно постаје , где је број грана у графу. Пошто Јенов алгоритам има позива Дијкстриног алгоритма у рачунању споредних путања, временска сложеност постаје .
Унапређења Јенов алгоритам може бити унапређен коришћењем хипа за чување потенцијалних к-најкраћих путања у листи . Коришћењем хипа уместо листе ће се побољшати брзина, али не и сложеност. Један од начина за благо смањење сложености је да се прескоче чворови који немају споредне путање. Овај случај настаје када су све споредне путање из неког споредног чвора искоришћене у претходном . Такође, ако има путања минималне дужине, у вези са путањама у , онда их можемо убацити у , јер више ниједна путања неће бити краћа.
Лолерово унапређење Јуџин Лолер је предложио модификацију Јеновог алгоритма у коме се дупликати путања не израчунавају, за разлику од оригиналне идеје, где се они израчунавају, али се потом одбацују када се установи да су дупликати. Ови дупликати настају када се рачунају споредне путање за чворове из корена од . На пример одступа од у неком чвору . Свака споредна путања где је , које се израчуна ће бити дупликат, јер су већ израчунате у понављању. Због тога, потребно је израчунати само споредне путање за чворове који су део споредне путање од , тј. само где узима вредности од до . Да би се ово урадило за , потребно је негде забележити где се одвојило од .
Референце
Литература
Спољашње везе Пајтон имплементација отвореног кода на GitHub страни C++ имплементација отвореног кода на Google Code страни
Категорија:Графовски алгоритми