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

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

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

Історія і назва

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

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

Алгоритм

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

Нехай є граф з вершинами , пронумерованими від до . Крім того, нехай є функція , яка повертає найкоротший шлях від  до , використовуючи вершини з множини як проміжні у шляху. Маючи таку функцію, нам потрібно знайти найкоротший шлях від кожного  до кожного , використовуючи лише вершини з множини .

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

1) шлях, у якому є тільки вершини з множини ,

або

2) шлях, який крізь вершини з множини проходить спочатку від до , а потім від до .

Найкоротший шлях від до , у якому є тільки вершини від до , визначається функцією . Якщо є коротший шлях від крізь до , то довжина цього шляху буде сумою (конкатенацією) найкоротшого шляху від до (крізь вершини з ) та найкоротшого шляху від до (також крізь вершини з ).

Якщо позначити вагу ребра від до через , можна визначити наступною рекурентною формулою:

База:

,

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

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

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

Приклад

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

Перед першою ітерацією циклу, тобто при , усі відомі шляхи відповідають одиничним ребрам у графі. Після кроку алгоритм знаходить шляхи, які проходять через вершину . Зокрема, шлях замінить шлях , що проходить через меншу кількість ребер, але є довшим (у сенсі ваги). Після знайдено шляхи, що проходять через вершини . Червоні та блакитні обведення показують, як шлях складається зі шляхів та , визначених на попередніх ітераціях. Шлях не розглядається, тому що найкоротшим шляхом від до на даному етапі є . Після знайдено шляхи, що проходять через . Нарешті, після , знайдено всі найкоротші шляхи.

При негативних циклах

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

  • Алгоритм Флойда-Воршелла багаторазово змінює довжини шляху між усіма парами вершин , включаючи ті, де ;
  • Початкова довжина шляху рівна 0;
  • Шлях може покращити початкову довжину, якщо він має довжину меншу за нуль, тобто позначає негативний цикл;
  • Таким чином, після виконання алгоритму, найкоротший шлях буде від'ємним, якщо існує негативний цикл — шлях від'ємної довжини від назад до .

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

Знаходження шляху

Алгоритм Флойда-Воршелла зазвичай знаходить тільки довжини шляхів між усіма парами вершин. За допомогою простих змін можна створити функцію для відновлення фактичного шляху між будь-якими двома кінцевими точками вершин. У наївному підході можна зберігати шлях від кожної вершини до кожної вершини, але це не обов'язково, і насправді дуже витратно щодо пам'яті. Натомість, дерево найкоротших шляхів може бути обчисленим для кожної вершини за час , використовуючи пам'яті для збереження кожного дерева, що дозволить ефективно відтворити шлях між будь-якими двома з'єднаними вершинами.

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

Аналіз

Нехай дорівнює кількості вершин . Щоб знайти усі значень (для всіх пар ), виходячи з відомих , потрібно операцій. Оскільки ми починаємо з та рахуємо послідовність матриць , кількість операцій становить , і складність алгоритму становить .

Застосування

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

Реалізація

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

Порівняння з іншими алгоритмами

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

Є також відомі алгоритми, що використовують швидке множення матриць для пришвидшення процесу пошуку найкоротшого шляху між усіма парами вершин у щільних графах. Проте у них робиться додаткове обмеження на ваги ребер (вони повинні бути малими цілими).[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..

Додатково


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.