Перегляд вихідного коду сторінки Алгоритм Флойда — Воршелла

{{Infobox Algorithm
|class=[[Задача про найкоротший шлях]] (для зважених графів)
|image=
|caption =
|data=Граф
|time=<math>O(|V|^3)</math>
|best-time=<math>\Omega (|V|^3)</math>
|space=<math>\Theta(|V|^2)</math>
}}
{{Алгоритми пошуку графами}}

В [[Інформатика|інформатиці]] '''алгоритм Флойда&nbsp;— Воршелла''' служить для розв'язання [[Задача про найкоротший шлях|задачі про найкоротший шлях]] в [[Орієнтований граф|орієнтованому]] [[зважений граф|зваженому графі]] з додатними або від'ємними вагами ребер (але без негативних циклів).<ref>{{CLRS|chapter=25.2 Алгоритм Флойда — Воршала}}</ref><ref>{{cite book | author=Kenneth H. Rosen | title=Discrete Mathematics and Its Applications, 5th Edition | publisher = Addison Wesley | year=2003 | isbn=0-07-119881-4 }}</ref>

При звичайній реалізації алгоритм повертає довжини (сумарні ваги) найкоротших шляхів між усіма парами вершин. Модифікація алгоритму може також повертати інформацію про самі шляхи. Різні версії алгоритму також використовують для знаходження [[Транзитивне замикання|транзитивного замикання]] у [[Бінарне відношення|відношенні]] <math>R</math>, або для знаходження [[Задача про найширший шлях|найширшого шляху]] між усіма парами вершин у зваженому графі (наприклад, при використанні [[Метод Шульце|методу Шульце]]).

== Історія і назва ==
Алгоритм було опубліковано в звичній сьогодні формі [[Роберт Флойд|Робертом Флойдом]] 1962 року.<ref>{{cite journal | first = Robert W. | last = Floyd | authorlink = Robert W. Floyd | title = Algorithm 97: Shortest Path | journal = [[Communications of the ACM]] | volume = 5 | issue = 6 | page = 345 | date=  June 1962 | doi = 10.1145/367766.368168 }}</ref> Проте це практично той самий алгоритм, що був опублікований {{нп|Бернард Рой|Бернардом Роєм||Bernard Roy}} 1959 року<ref>{{cite journal | first = Bernard | last = Roy |authorlink=Bernard Roy| title = Transitivité et connexité. | journal = [[C. R. Acad. Sci. Paris]] | volume = 249 | pages = 216–218 | year=  1959 }}
</ref> і [[Стівен Воршелл|Стівеном Воршеллом]] 1962 року<ref>{{cite journal | first = Stephen | last = Warshall | title = A theorem on Boolean matrices | journal = [[Journal of the ACM]] | volume = 9 | issue = 1 | pages = 11–12 | date=  January 1962 | doi = 10.1145/321105.321107 }}</ref> для знаходження [[Транзитивне замикання|транзитивного замикання]] в графі,<ref>{{mathworld|id=Floyd-WarshallAlgorithm | title = Floyd-Warshall Algorithm}}</ref> і є досить тісно пов'язаним з {{нп|Алгоритм Кліні|алгоритмом Кліні||Kleene's algorithm}} (опублікованим 1956 року) для перетворення [[Детермінований скінченний автомат|детермінованих скінченних автоматів]] у [[Регулярний вираз|регулярні вирази]].<ref>{{cite book | authorlink = Stephen Cole Kleene | first = S. C. | last = Kleene | chapter = Representation of events in nerve nets and finite automata | title = Automata Studies | editor = [[Claude Elwood Shannon|C. E. Shannon]] and [[Джон Маккарті|J. McCarthy]] | pages = 3–42 | publisher = Princeton University Press | year=  1956 }}</ref> Сучасне формулювання алгоритму як трьох вкладених циклів було вперше подано Пітером Інгерманом 1962 року.<ref>{{cite journal | first = Peter Z. | last = Ingerman | title = Algorithm 141: Path Matrix | journal = [[Communications of the ACM]] | volume = 5 | number = 11 | page = 556 | date = November 1962 | doi = 10.1145/368996.369016 }}</ref>

Алгоритм Флойда&nbsp;— Воршелла також відомий як '''Алгоритм Флойда''', '''Алгоритм Роя&nbsp;— Воршелла''', '''Алгоритм Роя&nbsp;— Флойда''', або '''Алгоритм WFI'''.

== Алгоритм ==
{{Вичитати|дата=липень 2021}}
Алгоритм Воршелла порівнює всі можливі [[Шлях (теорія графів)|шляхи]] в [[граф]]і між кожною парою [[Вершина (теорія графів)|вершин]]. Він виконується за <math>\Theta(|V|^3)</math> порівнянь. Це доволі швидко, враховуючи, що в графі може бути до <math>\Omega (|V|^2)</math> ребер, і кожну комбінацію буде перевірено. Він виконує це шляхом поступового поліпшення оцінки найкоротшого шляху між двома вершинами, поки оцінка не стає оптимальною.

Нехай є граф <math>G</math> з вершинами ''<math>V</math>'', пронумерованими від <math>1</math> до&nbsp;<math>N</math>. Крім того, нехай є функція <math display="inline">\mathrm{shortestPath}(i, j, k)</math>, яка повертає найкоротший шлях від&nbsp;<math>i</math> до&nbsp;<math>j</math>, використовуючи вершини з множини <math>\{1,2,\ldots,k\}</math> як проміжні у шляху. Маючи таку функцію, нам потрібно знайти найкоротший шлях від кожного&nbsp;<math>i</math> до кожного&nbsp;<math>j</math>, використовуючи лише вершини з множини <math>\{1,2,\ldots,k+1\}</math>.

Для кожної з цих пар вершин, найкоротшим шляхом може бути або

: 1) шлях, у якому є тільки вершини з множини <math>\{1,2,\ldots,k\}</math>,

або

: 2) шлях, який крізь вершини з множини <math>\{1,2,\ldots,k\}</math> проходить спочатку від <math>i</math> до <math>k+1</math>, а потім від <math>k+1</math> до ''<math>j</math>''.

Найкоротший шлях від <math>i</math> до <math>j</math>, у якому є тільки вершини від <math>1</math> до <math>k</math>, визначається функцією <math display="inline">\mathrm{shortestPath}(i, j, k)</math>. Якщо є коротший шлях від ''<math>i</math>'' крізь ''<math>k+1</math>'' до ''<math>j</math>'', то довжина цього шляху буде сумою (конкатенацією) найкоротшого шляху від ''<math>i</math>'' до ''<math>k+1</math>'' (крізь вершини з <math>\{1,2,\ldots,k\}</math>) та найкоротшого шляху від ''<math>k+1</math>'' до ''<math>j</math>'' (також крізь вершини з <math>\{1,2,\ldots,k\}</math>).

Якщо позначити вагу ребра від <math>i</math> до <math>j</math> через <math>w(i, j)</math>, можна визначити <math display="inline">\mathrm{shortestPath}(i, j, k+1)</math> наступною [[Рекурентне співвідношення|рекурентною формулою]]:

База:
: <math>\textrm{shortestPath}(i, j, 0) = w(i, j)</math>,
рекурентна частина:
: <math>\textrm{shortestPath}(i,j,k+1) = \min(\textrm{shortestPath}(i,j,k),\,\textrm{shortestPath}(i,k+1,k) + \textrm{shortestPath}(k+1,j,k))</math>

Ця формула є основною частиною алгоритму Флойда&nbsp;— Воршелла. Алгоритм спочатку обчислює <math display="inline">\mathrm{shortestPath}(i, j, k)</math> для всіх пар <math>(i,j)</math> при <math>k=1</math>, потім при <math>k=2</math>, і&nbsp;т.&nbsp;д. Цей процес продовжується до виконання умови ''<math>k=N</math>'' (включно), в результаті чого буде знайдено всі найкоротші шляхи для пар <math>(i,j)</math> крізь будь-які проміжні вершини. [[Псевдокод]] для цієї версії алгоритму:

 1 '''let''' dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 2 '''for each''' vertex ''v''
 3    dist[''v''][''v''] &larr; 0
 4 '''for each''' edge (''u'', ''v'')
 5    dist[''u''][''v''] &larr; w(''u'', ''v'')  ''// the weight of the edge (''u'','' v'')''
 6 '''for''' ''k'' '''from''' 1 '''to''' |V|
 7    '''for''' ''i'' '''from''' 1 '''to''' |V|
 8       '''for''' ''j'' '''from''' 1 '''to''' |V|
 9          '''if''' dist[''i''][''j''] > dist[''i''][''k''] + dist[''k''][''j''] 
 10             dist[''i''][''j''] &larr; dist[''i''][''k''] + dist[''k''][''j'']
 11         '''end if'''

== Приклад ==
Наведений вище алгоритм виконується на графі, розташованому ліворуч на малюнку нижче:

[[Файл:Floyd-Warshall example.svg|600px]]

Перед першою ітерацією циклу, тобто при <math>k=0</math>, усі відомі шляхи відповідають одиничним ребрам у графі. Після кроку <math>k=1</math> алгоритм знаходить шляхи, які проходять через вершину <math>1</math>. Зокрема, шлях <math>2 \rightarrow 1 \rightarrow 3</math> замінить шлях <math>2 \rightarrow 3</math>, що проходить через меншу кількість ребер, але є довшим (у сенсі ваги). Після <math>k=2</math> знайдено шляхи, що проходять через вершини <math>\{1,2\}</math>. Червоні та блакитні обведення показують, як шлях <math>4 \rightarrow 2 \rightarrow 1 \rightarrow 3</math> складається зі шляхів <math>4 \rightarrow 2</math> та <math>2 \rightarrow 1 \rightarrow 3</math>, визначених на попередніх ітераціях. Шлях <math>4 \rightarrow 2 \rightarrow 3</math> не розглядається, тому що найкоротшим шляхом від <math>2</math> до <math>3</math> на даному етапі є <math>2 \rightarrow 1 \rightarrow 3</math>. Після <math>k=3</math> знайдено шляхи, що проходять через <math>\{1,2,3\}</math>. Нарешті, після <math>k=4</math>, знайдено всі найкоротші шляхи.

== При негативних циклах ==
Негативний цикл&nbsp;— це цикл, в якому сума всіх ребер є меншою за нуль. Між будь-якою парою вершин <math>(i,j)</math>, що входять до негативного циклу, не існує найкоротшого шляху, оскільки довжина шляху між ними може бути наскільки завгодно малою (від'ємною). Для отримання осмисленого результату, алгоритм Флойда&nbsp;— Воршелла передбачає відсутність у графі негативних циклів. Тим не менш, якщо негативні цикли існують, алгоритм Флойда&nbsp;— Воршелла можна використати, щоб виявити їх. Інтуїтивно можна навести наступні міркування:

* Алгоритм Флойда&nbsp;— Воршелла багаторазово змінює довжини шляху між усіма парами вершин <math>(i,j)</math>, включаючи ті, де <math>i=j</math>;
* Початкова довжина шляху <math>(i,i)</math> рівна 0;
* Шлях <math>i \rightarrow j \rightarrow \ldots \rightarrow i</math> може покращити початкову довжину, якщо він має довжину меншу за нуль, тобто позначає негативний цикл;
* Таким чином, після виконання алгоритму, найкоротший шлях <math>(i,i)</math> буде від'ємним, якщо існує негативний цикл&nbsp;— шлях від'ємної довжини від <math>i</math> назад до <math>i</math>.

Отже, для виявлення негативних циклів з використанням алгоритму Флойда&nbsp;— Воршелла можна перевірити діагональ матриці шляхів. Присутність від'ємного числа означатиме, що графік містить щонайменше один негативний цикл.<ref>{{cite web | author = Dorit Hochbaum | url = http://www.ieor.berkeley.edu/~hochbaum/files/ieor266-2014.pdf | title = Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths | work = Lecture Notes for IEOR 266: Graph Algorithms and Network Flows | date = 2014 | format = [[PDF]] | publisher = Department of Industrial Engineering and Operations Research, [[University of California, Berkeley]] | accessdate = 2 червня 2015 | archive-date = 20 жовтня 2016 | archive-url = https://web.archive.org/web/20161020144626/http://www.ieor.berkeley.edu/~hochbaum/files/ieor266-2014.pdf }}</ref> Під час виконання алгоритму присутність негативного циклу може викликати появу чисел, які на порядки перевищують модуль найменшої від'ємної ваги ребра. Щоб уникнути проблем [[Арифметичне переповнення|переповнення]] або [[зникнення порядку]], потрібно перевіряти діагональ матриці шляхів у внутрішньому циклі алгоритму.<ref>{{cite journal
 |title        = The Floyd–Warshall algorithm on graphs with negative cycles
 |author       = Stefan Hougardy
 |journal      = Information Processing Letters
 |url          = http://www.sciencedirect.com/science/article/pii/S002001901000027X
 |volume       = 110
 |number       = 8-9
 |date         = April 2010
 |pages        = 279–281
 |doi          = 10.1016/j.ipl.2010.02.001
 |accessdate   = 2 червня 2015
 |archive-date = 24 вересня 2015
 |archive-url  = https://web.archive.org/web/20150924153424/http://www.sciencedirect.com/science/article/pii/S002001901000027X
}}</ref> Очевидно, що в неорієнтованому графі негативне ребро створює негативний цикл за участі прилеглих до ребра вершин. Якщо розглядати граф з попереднього прикладу як неорієнтований, то послідовність ребер <math>4 \rightarrow 2 \rightarrow 4</math> утворюють цикл довжини <math>-2</math>.

== Знаходження шляху ==
Алгоритм Флойда&nbsp;— Воршелла зазвичай знаходить тільки довжини шляхів між усіма парами вершин. За допомогою простих змін можна створити функцію для відновлення фактичного шляху між будь-якими двома кінцевими точками вершин. У наївному підході можна зберігати шлях від кожної вершини до кожної вершини, але це не обов'язково, і насправді дуже витратно щодо пам'яті. Натомість, {{нп|дерево найкоротших шляхів||en|Shortest-path tree}} може бути обчисленим для кожної вершини за час <math>\Theta(|E|)</math>, використовуючи <math>\Theta(|V|)</math> пам'яті для збереження кожного дерева, що дозволить ефективно відтворити шлях між будь-якими двома з'єднаними вершинами.

 '''let''' dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 '''let''' next be a |V| × |V| array of vertex indices initialized to '''null'''
 
 '''procedure''' FloydWarshallWithPathReconstruction()
    '''for each''' edge (u, v)
       dist[u][v] &larr; w(u, v)  ''// the weight of the edge (u,v)
       next[u][v] &larr; v
    '''for''' k '''from''' 1 '''to''' |V| ''// standard Floyd-Warshall implementation
       '''for''' i '''from''' 1 '''to''' |V|
          '''for''' j '''from''' 1 '''to''' |V|
             '''if''' dist[i][k] + dist[k][j] < dist[i][j] '''then'''
                dist[i][j] &larr; dist[i][k] + dist[k][j]
                next[i][j] &larr; next[i][k]
 
 '''procedure''' Path(u, v)
    '''if''' next[u][v] = null '''then'''
        '''return''' []
    path ← [u]
    '''while u ≠ v'''
        u &larr; next[u][v]
        path.append(u)
    '''return''' path

== Аналіз ==
Нехай <math>n</math> дорівнює кількості вершин <math>|V|</math>. Щоб знайти усі <math>n^2</math> значень <math display="inline">\mathrm{shortestPath}(i, j, k)</math> (для всіх пар ''<math>(i,j)</math>''), виходячи з відомих <math display="inline">\mathrm{shortestPath}(i, j, k-1)</math>, потрібно <math>2n^2</math> операцій. Оскільки ми починаємо з <math>\textrm{shortestPath}(i, j, 0) = w(i, j)</math> та рахуємо послідовність <math>n</math> матриць <math display="inline">\mathrm{shortestPath}(i, j, 1),\ \mathrm{shortestPath}(i, j, 2),\ \ldots\ , \mathrm{shortestPath}(i, j, n)</math>, кількість операцій становить <math>n \cdot 2n^2 = 2n^3</math>, і складність алгоритму становить [[Нотація Ландау#Відношення «Θ»|<math>\Theta(n^3)</math>]].

== Застосування ==
Алгоритм Флойда&nbsp;— Воршелла можна використовувати для вирішення таких задач:
* [[Задача про найкоротший шлях|Знаходження найкоротших шляхів у напрямленому графі]].
* Знаходження [[Транзитивне замикання|транзитивних замикань]] у [[Орієнтований граф|напрямленому графі]]. В оригінальному формулюванні (Воршелла), граф є незважений і представлений [[Бінарна матриця|булевою матрицею]]. Операції додавання і мінімуму замінені на логічні [[Кон'юнкція|AND]] i [[Диз'юнкція (логіка)|OR]].
* Знаходження [[Регулярний вираз|регулярних виразів]], що позначають [[Регулярна граматика|регулярні граматики]], які приймаються [[Скінченний автомат|скінченним автоматом]] ({{нп|Алгоритм Кліні|Алгоритм Кліні||Kleene's algorithm}}, який є узагальненням алгоритму Флойда&nbsp;— Воршелла).<ref>{{citation|title=Handbook of Graph Theory|series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2003|page=65|url=http://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204|accessdate=2 червня 2015|archive-date=14 липня 2014|archive-url=https://web.archive.org/web/20140714234201/http://books.google.com/books?id=mKkIGIea_BkC&pg=PA65}}.</ref>
* [[Невироджена матриця|Невиродженість матриці]] в [[Метод Гауса|методі Гауса]]<ref>{{cite web | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.7650 | title = Algebraic Structures for Transitive Closure | first = Rafael | last = Penaloza | accessdate = 2 червня 2015 | archive-date = 19 жовтня 2012 | archive-url = https://web.archive.org/web/20121019203507/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.7650 }}</ref>
* Оптимальна маршрутизація. У такій постановці задача полягає у знаходженні шляху з максимальним потоком між двома вершинами. Це означає, що замість мінімумів, як у псевдокоді вище, шляхи оптимізуються по максимумах. Вагами ребер задаються фіксовані обмеження на величину потоку. Загальний потік вздовж шляху характеризується ребром з найменшим пропусканням, тому операція додавання замінюється на взяття мінімуму.
* Знаходження найдовшого шляху.
* Швидкі обрахунки у {{нп|Pathfinder network|Pathfinder network|en|Pathfinder network}}.
* Розрахунок канонічних форм {{нп|Матриця меж різності|матриць меж різності (DBM)|en|Difference bound matrix}}.

== Реалізація ==
Реалізація алгоритму доступна багатьма мовами:
* [[C++]], в бібліотеці [http://www.boost.org/libs/graph/doc/ boost::graph] {{Webarchive|url=https://web.archive.org/web/20080113203926/http://www.boost.org/libs/graph/doc/ |date=13 січня 2008 }}
* [[C Sharp|C#]], в [http://www.codeplex.com/quickgraph QuickGraph] {{Webarchive|url=https://web.archive.org/web/20100317031339/http://www.codeplex.com/quickgraph |date=17 березня 2010 }} та [https://www.nuget.org/packages/QuickGraphPCL/3.6.61114.2 QuickGraphPCL] {{Webarchive|url=https://web.archive.org/web/20200611163124/https://www.nuget.org/packages/QuickGraphPCL/3.6.61114.2 |date=11 червня 2020 }}
* [[Java (мова програмування)|Java]], у бібліотеці [http://commons.apache.org/sandbox/commons-graph/ Apache Commons Graph] {{Webarchive|url=https://web.archive.org/web/20130512104032/http://commons.apache.org/sandbox/commons-graph/ |date=12 травня 2013 }}
* [[JavaScript]], у бібліотеці {{нп|Cytoscape}}
* [[MATLAB]], у пакеті [http://www.mathworks.com/matlabcentral/fileexchange/10922 Matlab_bgl] {{Webarchive|url=https://web.archive.org/web/20130817093138/http://www.mathworks.com/matlabcentral/fileexchange/10922 |date=17 серпня 2013 }}
* [[Perl]], в модулі [https://metacpan.org/module/Graph Graph] {{Webarchive|url=https://web.archive.org/web/20131008150307/https://metacpan.org/module/Graph |date=8 жовтня 2013 }}
* [[Python]], в бібліотеці [[NetworkX]] та модулі [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html#scipy.sparse.csgraph.floyd_warshall scipy.sparse.csgraph] {{Webarchive|url=https://web.archive.org/web/20200611184646/http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html#scipy.sparse.csgraph.floyd_warshall |date=11 червня 2020 }} бібліотеки [[SciPy]]
* [[R (мова програмування)|R]], в пакетах [http://cran.r-project.org/web/packages/e1071/index.html e1071] {{Webarchive|url=https://web.archive.org/web/20150627070602/http://cran.r-project.org/web/packages/e1071/index.html |date=27 червня 2015 }} та [https://cran.r-project.org/web/packages/Rfast/index.html Rfast] {{Webarchive|url=https://web.archive.org/web/20200718043904/https://cran.r-project.org/web/packages/Rfast/index.html |date=18 липня 2020 }}

== Порівняння з іншими алгоритмами ==
Алгоритм Флойда&nbsp;— Воршелла добре підходить для обчислення шляху між усіма парами вершин у щільних графах, в яких більшість або всі пари вершин з'єднані ребрами. Для [[Щільний граф|розріджених графів]] з невід'ємними вагами ребер краще використовувати [[алгоритм Дейкстри]] для кожної можливої вихідної вершини, оскільки складність алгоритму Дейкстри (<math>O(|E||V|+|V|^2\log|V|)</math> з використанням [[Фібоначчієва купа|купи Фібоначчі]]) є кращою, ніж <math>O(|V|^3)</math>&nbsp;— складність алгоритму Флойда&nbsp;— Воршелла, коли <math>|E|</math> набагато менше від <math>|V|^2</math>. Для розріджених графів з негативними ребрами, але без негативних циклів, може бути використаний [[алгоритм Джонсона]] з тим самим асимптотичним часом роботи, що й повторюваний алгоритм Дейкстри.

Є також відомі алгоритми, що використовують [[Алгоритм перемножування матриць|швидке множення матриць]] для пришвидшення процесу пошуку найкоротшого шляху між усіма парами вершин у щільних графах. Проте у них робиться додаткове обмеження на ваги ребер (вони повинні бути малими цілими).<ref>{{citation
 | last = Zwick | first = Uri | authorlink = Uri Zwick
 | date = May 2002
 | doi = 10.1145/567112.567114
 | issue = 3
 | journal = [[Journal of the ACM]]
 | pages = 289–317
 | title = All pairs shortest paths using bridging sets and rectangular matrix multiplication
 | volume = 49}}.</ref><ref>{{citation
 | last = Chan | first = Timothy M. | authorlink = Timothy M. Chan
 | date = January 2010
 | doi = 10.1137/08071990x
 | issue = 5
 | journal = [[SIAM Journal on Computing]]
 | pages = 2075–2089
 | title = More algorithms for all-pairs shortest paths in weighted graphs
 | volume = 39}}.</ref> Крім того, через високі сталі коефіцієнти у виразі складності, вони можуть забезпечити пришвидшення відносно алгоритму Флойда&nbsp;— Воршелла лише для дуже великих графів.

== Посилання ==
{{Reflist}}

== Додатково ==
* [http://www.pms.informatik.uni-muenchen.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization Interactive animation of the Floyd–Warshall algorithm] {{Webarchive|url=https://web.archive.org/web/20020825104508/http://www.pms.informatik.uni-muenchen.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization |date=25 серпня 2002 }}
* [http://quickgraph.codeplex.com/ The Floyd–Warshall algorithm in C#, as part of QuickGraph] {{Webarchive|url=https://web.archive.org/web/20180121140629/http://quickgraph.codeplex.com/ |date=21 січня 2018 }}
* [http://students.ceid.upatras.gr/~papagel/english/java_docs/allmin.htm Visualization of Floyd's algorithm] {{Webarchive|url=https://web.archive.org/web/20150530010616/http://students.ceid.upatras.gr/~papagel/english/java_docs/allmin.htm |date=30 травня 2015 }}


{{Algorithms-stub}}

[[Категорія:Алгоритми на графах]]
[[Категорія:Динамічне програмування]]