Алгоритм Флойда — Воршелла

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Алгоритм Флойда — Воршелла
Клас Задача про найкоротший шлях (для зважених графів)
Структура даних Граф
Найгірша швидкодія
Найкраща швидкодія
Просторова складність у найгіршому випадку

В інформатиці, алгоритм Флойда-Воршелла використовується для розв'язання задачі про найкоротший шлях у зваженому графі з додатними або від'ємними вагами ребер (але без від'ємнозначних циклів).[1][2] При звичайній реалізації алгоритм видасть довжини (сумарні ваги) найкоротших шляхів між всіма парами вершин, хоча він не видасть інформацію про самі шляхи. Різні версії алгоритму також використовуються для знаходження транзитивного замикання в відношенні , або (враховуючи Метод Шульце), для знаходження найбільшого шляху (англ. widest path problem) між всіма парами вершин у зваженому графі.

Історія і назва[ред.ред. код]

Алгоритм Флойда-Воршелла — це приклад динамічного програмування. Його було опубліковано в звичній сьогодні формі Робертом Флойдом 1962 року.[3] Проте, це практично той самий алгоритм, що було опубліковано Бернардом Роєм[en] 1959 року[4] і Стівеном Воршеллом 1962 року[5] для знаходження транзитивного замикання в графі,[6] і є досить тісно пов'язаним з алгоритмом Кліні[en] (опублікованим 1956 року) для перетворення детермінованих скінченних автоматів у регулярні вирази.[7] Сучасне формулювання алгоритму, як трьох вкладених циклів було вперше подано Пітером Інгерманом 1962 року.[8]

Алгоритм також називають Алгоритм Флойда, Алгоритм Роя-Воршелла, Алгоритм Роя-Флойда, або Алгоритм WFI.

Алгоритм[ред.ред. код]

Алгоритм Воршелла порівнює всі можливі шляхи в графі між кожною парою вершин. Він виконується за Θ(|V|³) порівнянь. Це доволі примітивно, враховуючи, що в графі може бути до Ω(|V |²) ребер, і кожну комбінацію буде перевірено. Він виконує це шляхом поступового поліпшення оцінки по найкоротшому шляху між двома вершинами, поки оцінка не стає оптимальною.

Розгляньмо граф G з ребрами V, пронумерованими від 1 до N. Крім того розгляньмо функцію shortestPath(ijk), яка повертає найкоротший шлях від i до j, використовуючи вершини з множини {1,2,…,k} як внутрішні у шляху. Тепер, маючи таку функцію, нам потрібно знайти найкоротший шлях від кожного i до кожного j, використовуючи тільки вершини від 1 до k + 1.

Для кожної з цих пар вершин, найкоротший шлях може бути або (1)- шлях, у якому є тільки вершини з множини {1, …, k}, або (2)- шлях, який проходить від i до k + 1 а потім відk + 1 до j.Найкоротший шлях від i to j that only uses vertices 1 через k визначається функцією shortestPath(ijk), і якщо є коротший шлях відi до (k + 1 до j), то довжина цього шляху буде сумою(конкатенацією) найкоротшого шляху відi до k + 1 (використовуючи вершини{1, …, k}) і найкоротший шлях від k + 1 до j (також використовуючи вершини з {1, …, k}).

 — це вага ребра між i таj.Можна визначити shortestPath(ijk + 1) наступною рекурсивною формулою база:

рекурсивна частина:

Ця формула є основною частиною алгоритму Флойда-Воршелла. Алгоритм спочатку обчислює shortestPath(ijk) для всіх пар(ij) де k = 1, потім k = 2, і т. д. Цей процес продовжується, поки k = N, і поки не знайдено всі найкоротші шляхи для пар (ij). Псевдокод для цієї версії алгоритму:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← 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] ← dist[i][k] + dist[k][j]
11         end if

Приклад[ред.ред. код]

Алгоритм виконується на малюнку нижче:

Floyd-Warshall example.svg


Перед першою ітерацією циклу k=0 і відомі шляхи відповідають одиночним ребрам у графі. Коли k=1, знайдено шляхи, яку проходять через вершину 1, зокрема: шлях 2→1→3 , замінить шлях 2→3, що проходить через меншу кількість ребер, але є довшим. При k=2, знаходяться шляхи, що проходять через вершини {1,2} . Червоні і голубі квадратики показують, як шлях 4→2→1→3 складається з 4→2 і 2→1→3, визначеними на попередніх ітераціях. Шлях 4→2→3 не розглядається, бо 2→1→3 поки що найкоротший шлях. При k=3,знаходяться шляхи, що проходять через {1,2,3}. Нарешті, при k=4, знайдено всі найкоротші шляхи.

При негативних циклах[ред.ред. код]

Негативний цикл- це цикл, в якому сума всіх ребер є меншою нуля. Немає найкоротшого шляху між парами вершин i, j, між якими є негативні ребра, бо шлях між ними тоді може бути нескінченно малий. Для нормального результату, алгоритм Флойда передбачає відсутність негативних циклів. Тим не менш, якщо є негативні цикли, алгоритм Флойда-Воршалла може бути використаний, щоб виявити їх. Інтуїтивно це таким чином:

  • Алгоритм Флойда-Воршалла багаторазово змінює довжини шляху між усіма парами вершин (ij), включаючи ті, де i = j;
  • Спочатку довжина шляху (i,i) =0;
  • Шлях {(i,k), (k,i)} може тільки поліпшити це, якщо він має довжину менше, ніж нуль, тобто позначає негативний цикл;
  • Таким чином, після виконання алгоритму, шлях (i,i) буде негативним, якщо існує шлях негативної довжини від i назад до i.

Отже, для виявлення негативних циклів з використанням алгоритму Флойда-Воршелла, можна перевірити діагональ матриці шляхів, і присутність негативного числа означає, що графік містить, щонайменше, один негативний цикл.[9] Щоб уникнути проблем, потрібно у внутрішньому циклі перевіряти діагональ матриці шляхів.[10]Очевидно, що в неорієнтованому графі негативне ребро створює негативний цикл за участю інцидентних вершин. Якщо враховувати попередній приклад, як неорієнтований граф, то послідовність ребер 4 — 2 - 4 утворюють цикл довжини -2.

Знаходження шляху[ред.ред. код]

Алгоритм Флойда-Воршалла зазвичай знаходить тільки довжину шляху між усіма парами вершин. За допомогою простих змін, можна створити функцію для відновлення фактичного шляху між будь-якими двома кінцевими точками вершин. І хоча хтось може схилятись до ідеї зберігання шляху від кожної вершини до кожної вершини, це не обов'язково, і насправді дуже витратно щодо пам'яті. Натомість дерево найкоротших шляхів[en] може бути обчисленим для кожної вершини за час Θ(|E|) використовуючи Θ(|V|) пам'яті для збереження кожного дерева, що дозволить ефективно відтворити шлях між будь-якими двома з'єднаними вершинами.

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] ← w(u,v)  // the weight of the edge (u,v)
      next[u][v] ← 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] ← dist[i][k] + dist[k][j]
               next[i][j] ← next[i][k]

procedure Path(u, v)
   if next[u][v] = null then
       return []
   path = [u]
   while u ≠ v
       u ← next[u][v]
       path.append(u)
   return path

Аналіз[ред.ред. код]

Нехай |V|= n- кількість вершин. Щоб знайти усі n2 з shortestPath(i,j,k) (для всіх i та j) з даного shortestPath(i,j,k−1) потрібно 2n2 операцій. Ми починаємо з shortestPath(i,j,0) = edgeCost(i,j) рахуємо послідовність n матриць shortestPath(i,j,1), shortestPath(i,j,2), …, shortestPath(i,j,n), кількість операцій = n · 2n2 = 2n3. ому, складність алгоритму = Θ(n3).


Додатки[ред.ред. код]

Алгоритм Флойда-Воршелла можна використовувати для вирішення таких задач:

Реалізація[ред.ред. код]

Реалізація алгоритму доступна багатьма мовами:

Порівняння з іншими алгоритмами[ред.ред. код]

Алгоритм Флойда-Воршалла є хорошим для обчислення шляху між усіма парами вершин в щільних графах, в яких більшість або всі пари вершин, з'єднані ребрами. Для розріджених графів з невід'ємними вагами ребер, найкраще використовувати алгоритм Дейкстри від кожної можливої вихідної вершини, оскільки складність Дейкстри( використовуючи binary heap) є кращою, ніж  — складність алгоритму Флойда_Воршала, коли набагато менше від . Для розріджених графів з негативними ребрами, але без негативних циклів, алгоритм Джонсона може бути використаний, з тим же асимптотичним часом роботи як повторювання підходу Дейкстри.

Є також відомий алгоритм, що використовує швидке множення матриць для покращення процесу пошуку найкоротшого шляху в щільних графах. Проте тут робиться додаткове обмеження на ваги ребер(вони повинні біти малими цілими).[13][14]

Посилання[ред.ред. код]

  1. Томас Кормен; Чарльз Лейзерсон, Рональд Рівест (1990). Вступ в алгоритми (вид. 1st). MIT Press і McGraw-Hill. ISBN 0-262-03141-8.  Секція 26.2, «The Floyd–Warshall algorithm», ст. 558–565 та сек3ція 26.4, «A general framework for solving path problems in directed graphs», ст. 570–576.
  2. Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5th Edition. Addison Wesley. ISBN 0-07-119881-4. 
  3. Floyd, Robert W. (June 1962). Algorithm 97: Shortest Path. Communications of the ACM 5 (6). с. 345. doi:10.1145/367766.368168. 
  4. Roy, Bernard (1959). Transitivité et connexité.. C. R. Acad. Sci. Paris 249. с. 216–218. 
  5. Warshall, Stephen (January 1962). A theorem on Boolean matrices. Journal of the ACM 9 (1). с. 11–12. doi:10.1145/321105.321107. 
  6. Weisstein, Eric W. Floyd-Warshall Algorithm(англ.) на сайті Wolfram MathWorld.
  7. Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. У C. E. Shannon and J. McCarthy. Automata Studies. Princeton University Press. с. 3–42. 
  8. Ingerman, Peter Z. (November 1962). Algorithm 141: Path Matrix. Communications of the ACM 5 (11). с. 556. doi:10.1145/368996.369016. 
  9. Dorit Hochbaum (2014). Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths (PDF). Lecture Notes for IEOR 266: Graph Algorithms and Network Flows. Department of Industrial Engineering and Operations Research, University of California, Berkeley. 
  10. Stefan Hougardy (April 2010). The Floyd–Warshall algorithm on graphs with negative cycles. Information Processing Letters 110 (8-9). с. 279–281. doi:10.1016/j.ipl.2010.02.001. 
  11. Gross, Jonathan L.; Yellen, Jay (2003). Handbook of Graph Theory. Discrete Mathematics and Its Applications. CRC Press. с. 65. ISBN 9780203490204. .
  12. Penaloza, Rafael. Algebraic Structures for Transitive Closure. 
  13. Zwick, Uri (May 2002). All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM 49 (3): 289–317. doi:10.1145/567112.567114. .
  14. Chan, Timothy M. (January 2010). More algorithms for all-pairs shortest paths in weighted graphs. SIAM Journal on Computing 39 (5): 2075–2089. doi:10.1137/08071990x. .

Додатково[ред.ред. код]