Проблем најширег пута

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

У овом графу, најшири пут од цвора D до цвора Ф је опсега 29, и пролази кроз чворове C, Е, Б и Г

На пример, ако граф представља везе између рутера на Интернету, и тежина гране представља проток конекције између два рутера, проблем најширег пута је проблем налажења пута између два Интернет чвора која имају максимални могући проток. Тежина гране минималне тежине је позната као капацитет протока пута. Поред примене у мрежи рутера, проблем најширег пута је врло важна компонента Шулцове методе (систем за гласање), приликом одлучивања победника избора. Такође проблем се примењује у тзв. дигиталном састављању (процес дигиталне монтаже више слика у једну завршну слику) , у метаболичкој анализи, и у рачунању максималног тока. Могуће је прилагодити алгоритме најкраћег пута како би се израчунао најшири пут, мењајући их тако да користе удаљеност уског грла уместо дужине пута. Добро је знати да, у многим случајевима чак и бржи алгоритми су могући.

Уско повезан проблем са овим проблемом је проблем минимаx пута, који тражи пут тако што минимизује максималну тежину сваке гране. Примењује се тамо где је укључено планирање транспорта. Било који проблем најширег пута може бити промењен у алгоритам проблема минимаx пута, или обрнуто, тако што се преокрене смисао свих поређења тежина која се дешавају у алгоритму, или еквивалентно тако што се свака грана замени својом негацијом.

Неусмерени графови

У неусмереном графу , најшири пут може да се нађе као пут између два чвора у максималном разапињућем стаблу графа, док минимаx пут може да се нађе као пут између два чвора у минималном разапињућем стаблу.

За било који граф, усмерен или неусмерен, постоји јасан алгоритам за тражење најширег пута, чим је позната тежина ивице минималне тежине: једноставно се обришу све мање гране и тражи се било који пут између осталих ивица користећи обилазак стабла у ширину (БФС) или обилазак стабла у дубину (ДФС). На основу овог теста, такође постоји алгоритам линеарног времена за налажење најширег с-т пута у неусмереном графу, који не користи максимално разапињуће стабло. Основна идеја алгоритма је да се алгоритам претраге линеарне временске сложености примени на грани средње тежине, и онда или да се обришу све мање гране или да се све веће гране скупе у зависности од тога да ли пут постоји или не постоји, и да се затим рекурзивно сместе у мањи резултујући граф.

Фернандез, Гарфинкел & Арбиол 1998 користе уско грло најкраћих путева у циљу да саставе композицију фотографија из ваздуха комбиновањем више слика које приказују преклапање области. У подпроблему где се проблем најширег пута примењује, две слике су већ трансформисане у обичан координатни систем; преостали задатак је да се изабере шав, крива која пролази кроз све регије преклапања и дели једну слику од друге. Пиксели на једној страни шава ће бити копирани са једне од слика, а пиксели на другој страни шава ће бити копирани са друге слике; за разлику од осталих метода композиција који секу пикселе са обе слике, овај метод производи важећу фотографску слику сваког дела регије који је усликан. Они мере тежину грана мрежастог графа по нумеричкој процени , колико ће шав кроз ту тачку да буде видљив; избор најкраћег пута као шава, што је боље него конвенционално тражење најкраћег пута, приморава њихов систем да нађе шав кога је тешко разазнати, што је боље него допустити замену веће видљивости једног дела слике за мању видљивост било где на слици.

Ако су тежине свих грана неусмереног графа позитивне, онда минимаx удаљеност између парова тачака (максимална тежина ивица минимаx пута) формира ултраметрички простор (специјална врста метричког простора); обрнуто сваки коначан ултраметрички простор долази од минимаx удаљености. Структура података формирана од минималног разапињућег стабла дозвољава да минимаx удаљеност између било ког пара чворова буде израчуната за константно време у зависности од удаљености, користећи најмањег заједничког претка у Декартовом стаблу (бинарно стабло). Корен Декартовог стабла представља најтежу грану минималног разапињућег стабла, и деца корена су Декартова стабла која су рекурзивно формирана од подстабла минималног разапињућег стабла формираног уклањањем најтежих грана. Листови Декартовог стабла представљају чворове улазног графа, а минимаx растојање између два чвора је једнако тежини чвора који је најмањи заједнички предак Декартовог стабла. Једном кад је минимално разапињуће стабло сортирано, Декартово стабло се може конструисати за линеарно време.

Усмерени графови

У усмереним графовима, решење максималног разапињућег стабла се не може искористити. Уместо тога, постоје неколико познатих алгоритама који се могу искористити; који алгоритам изабрати зависи од тога да ли је почетни или одредишни чвор фиксиран, или да ли путеви више почетних или одредишних чворова морају истовремено да се нађу.

Сви парови

Проблем најширег пута свих парова има примене у Шулцовој методи приликом добијања победника у изборима где гласачи рангирају кандидате према приоритету. Шулцова метода формира комплетан усмерен граф у коме чворови представљају кандидате и свака два чвора су повезана граном. Свака грана је усмерена тако да излази из чвора победника и улази у чвор губитника, при чему свака грана представља сопствено мало такмичење два такмичара који су повезани том граном. Затим, метода рачуна најшири пут између свих парова чворова и победник је кандидат чији чвор има пут до сваког противника који је шири од пута који противници имају до њега. Резултати избора коришћењем ове методе су доследни Кондорсетовој методи (Цондорцет метход) кандидат који је победио сва мала такмичења је аутоматски победио на избору – али генерално допушта да победник буде изабран, чак и у ситуацијама када Кондорсетова метода пропадне. Шулцову методу су користиле различите организације, укључујући и Задужбину Викимедије.

Да би се израчунала најшира ширина пута за све парове чворова у збијеном усмереном графу, као граф који се јавља у примени у гласању, асимптотски најбржи могући приступ има временску сложеност О(н^(3+ω)/2) где је ω експонент за брзо множење матрица. Користећи најбоље познате алгоритме за множење матрица, временска сложеност постаје О(н^2.688). Насупрот томе, имплементација Шулцове методе користи измењену верзију једноставнијег Флојд-Варшаловог алгоритма, и има временску сложеност О(н³). За графове који су проређени, било би ефикасније да се више пута примени алгоритам најширег пута са појединачним извором.

Један извор

Ако су гране сортиране на основу својих тежина, онда измењена верзија Дијкстриног алгоритма може да рачуна уска грла између одређеног почетног и сваког другог чвора у графу, за линеарно време. Кључна идеја иза убрзане конвенционалне верзије Дијкстриног алгоритма је да секвенца растојања до сваког чвора, са циљем да се чворови узимају у обзир овим алгоритмом, је монотона подсеквенца свих сортираних тежинских грана; стога ред са приоритетом Дијкстриног алгоритма може бити замењен низом бројева од 1 до м (број грана у графу), где члан низа и садржи чворове чије растојање је тежина гране на позицији и у сортираном редоследу. Ова метода дозвољава да се проблем најширег пута реши брзо колико и сортирање; на пример, ако је тежина гране представљена као цео број, онда би се време које је потребно за сортирање листе од м целих бројева могло применити на овај проблем.

Један извор и једно одредиште

Берман & Хандлер 1987 предлажу да би сервис возила и возила хитне помоћи требало да користе минимаx путеве када се враћају у своју базу након позива сервиса. У овој примени , време повратка није толико важно, за разлику од времена реаговања на могући позив сервиса док је возило сервиса у повратку. Користећи минимаx путању, где је тежина гране максимално време путовања од једне тачке гране до најудаљенијег могућег позива сервиса, може се испланирати рута која минимизује максимално могуће време чекања од тренутка када сервис прими позив до тренутка када возило сервиса дође на позвано место. Уллах, Лее & Хассоун 2009 користе максималне путање како би направили доминантну ланчану реакцију у метаболичким мрежама; у њиховом моделу, тежина гране је слободна енергија метаболичке реакције која је представљена граном.

Још једна примена најширих путања се јавља у Форд-Фулкерсоновом алгоритму за проблем максималног протока. Више пута повећавајући проток дуж максималног капацитета пута у мрежи протока доводи до мале границе, О(м лог У), бројева повећања који су потребни да би се нашао максимални проток; овде, гране капацитета су подразумевано цели бројеви, који су у већини случајева У. Ипак, ова анализа није поздана за налажење пута који има максимални капацитет; било који пут чији капацитет има константан фактор максимума је довољан. Комбинујући ову приближну идеју са методом повећања најкраћег пута Едмондс-Карповог алгоритма, доводи до алгоритма максималног протока који је сложености О(мн лог У).

Могуће је врло ефикасно наћи путање максималног капацитета и минимаx путање са појединачним извором и појединачним одредиштем чак и у моделима рачунања код којих не смемо да вршимо било какву математичку операцију, можемо само да упоређујемо гране улазног графа. Алгоритам садржи сет од С грана за које се зна да представљају уско грло оптималног пута; иницијално, С је само сет свих м грана графа. У свакој итерацији алгоритма, С се дели на одређене подсетове С₁, С₂, ... које су приближно истих величина; број подсетова у овој подели није случајан, изабран је тако да се све раздвојене тачке између подсетова могу наћи понављањем средњег-тражења за време О(м). Алгоритам затим поново поставља тежину свакој грани графа у зависности од индекса подсета којој грана припада, и затим се на тако измењеном графу примени измењени Дијкстрин алгоритам; и у зависности од резултата рачунања, алгоритам може за линеарно време да одреди који од подсета садржи грану која има тежину уског грла. Након тога се С замени подсетом С_и, за који се претходно установило да садржи грану уског грла, и почиње следећу итерацију са сада новим сетом С. Број подсетова на којих се С може поделити се експоненцијално повећава сваким кораком, па је број итерација пропорционалан логаритамској функцији, О(лог*н), док је временска сложеност овог алгоритма О(млог*н).

Еуклидов сет тачака

Варијанта проблема минимаx путање се такође узела у обзир за сет тачака у Еуклидовој геометрији. За разлику од неусмерених графова, овај проблем може да се реши врло ефикасно тако што се нађе Еуклидово минимално разапињајуће стабло. Ипак, постаје компликованије када је пут такав да не минимизује само кратка растојања него, међу путањама које имају иста кратка растојања, минимизује или приближно минимизује укупну дужину пута. Приближно решење се може добити коришћењем тзв. геометријских извијача.