Задача про найширший шлях

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

У цьому графі найширший шлях із пункту Maldon у пункт Feering має ширину 29 та проходить через Clacton, Tiptree, Harwich та Blaxhall

Наприклад, у графі, який представляє з'єднання між маршрутизаторами в інтернеті, в якому вага ребра представляє смугу пропускання з'єднання між двома маршрутизаторами, задача про найширший шлях відповідає задачі пошуку наскрізного шляху між двома вузлами інтернету, який має найширшу смугу. Найменша вага ребра в цьому шляху відома як місткість чи ширина шляху. Також задача про найширший шлях є важливою складовою методу Шульце визначення переможця в багатоходових виборах, вона використовується в ^[en], ^[en] і для обчислення максимальних потоків.

Тісно пов'язана задача про мінімаксний шлях запитує про шлях, який мінімізує максимальну вагу будь-якого з ребер (можна інтерпретувати як пошук найрівнішої дороги, що має мінімальні кути підйому та спуску). Цю задачу застосовують у плануванні дорожнього руху. Будь-який алгоритм для задачі про найширший шлях можна перетворити на алгоритм про мінімаксний шлях і, навпаки, шляхом обернення сенсу всіх порівнянь ваг, що вживаються в алгоритмі, або, еквівалентно, замінивши ваги від'ємними значеннями.

Неорієнтовані графи

У неорієнтованому графі найширший шлях можна знайти як шлях між двома вершинами в максимальному кістяковому дереві графа, а мінімаксний шлях можна знайти як шлях між двома вершинами в мінімальному кістяковому дереві.

У будь-якому графі, орієнтованому чи ні, є простий алгоритм знаходження найширшого шляху, якщо відома вага ребра з найменшим значенням — просто видаляємо всі ребра з меншим значенням і шукаємо шлях серед решти ребер за допомогою пошуку в ширину або пошуку в глибину. Існує заснований на цій перевірці алгоритм лінійного часу для знаходження найширшого s-t шляху в неорієнтованому графі, який не використовує максимального кістякового дерева. Основна ідея алгоритму полягає в тому, щоб застосувати алгоритм лінійного часу для знаходження шляху до медіани ваг ребер графа, потім або видалити всі менші ребра, або стягнути всі більші ребра відповідно до того, чи існує шлях, чи його немає, а потім рекурсивно опрацювати менший граф.

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

Розв'язок мінімаксної задачі між двома кутами решітки можна використати для пошуку слабкої відстані Фреше між двома ламаними. Тут кожна вершина решітки представляє пару відрізків, по одному з кожного ланцюга, а вага ребра представляє відстань Фреше, необхідну, щоб пройти від однієї пари відрізків до іншої.

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

Орієнтовані графи

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

Всі пари

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

Для обчислення найширшого шляху для всіх пар вузлів у щільних орієнтованих графах, таких, які виникають у застосуванні до голосування, ^[en] найшвидший підхід працює за час ${\displaystyle O(n^{(3+\omega )/2})}$, де ${\displaystyle \omega }$ — показник для алгоритмів швидкого множення матриць. За використання найкращих відомих алгоритмів матричного множення ці часові межі перетворюються на ${\displaystyle O(n^{2{,}688})}$. У ранніх алгоритмах, для прискорення знаходження найширших шляхів для всіх пар, використовували швидке матричне множення, див. статті ^[en], Вільямса і Юстера і розділ 5 книги Василевської. Посилальна реалізація методу Шульце використовує модифіковану версію простішого алгоритму Флойда — Воршелла, який працює за час ${\displaystyle O(n^{3})}$. Для розріджених графів можна ефективніше використовувати багаторазове застосування алгоритму пошуку найширшого шляху для одного джерела.

Одне джерело

Якщо ребра відсортовано за їхніми вагами, то модифікована версія алгоритму Дейкстри може обчислити вузькі місця між призначеною стартовою вершиною та іншими вершинами графа за лінійний час. Ключова ідея прискорення за допомогою звичайного варіанта алгоритму Дейкстри полягає в тому, що послідовність «вузьких місць» до кожної вершини в порядку появи цих вершин у алгоритмі є монотонною підпослідовністю послідовності ребер, сортованої за вагами. Тому чергу з пріоритетом алгоритму Дейкстри можна реалізувати як ^[en], масив, пронумерований числами від 1 до m (число ребер у графі), де комірка масиву i містить вершини, «вузькі місця» яких дорівнюють вазі ребра з позицією i у відсортованому порядку. Цей метод дозволяє розв'язати задачу про найширший шлях із такою ж швидкістю, як і сортування. Наприклад, якщо ваги ребер задано цілими числами, то граничний час для цілочисельного сортування списку m цілих чисел буде також оцінкою для цієї задачі.

Одне джерело та одна цільова вершина

Берман і Гандлер припустили, що аварійні машини і машини швидкої допомоги, повертаючися з точки виклику на базу, повинні використовувати мінімаксний шлях. У цих випадках час повернення менш важливий, ніж час відповіді, якщо інший виклик трапиться, поки машина повертається. За використання мінімаксного шляху, в якому вагами служить найбільший час шляху від ребра до найвіддаленішої точки можливого виклику, можна спланувати маршрут так, що найбільший час можливої затримки між отриманням виклику і прибуттям машини буде найменшим. Улла, Лі та Гассун використали максимальні шляхи для моделювання ланцюжка домінівних реакцій у метаболічних мережах. У їхній моделі вагою ребра служить вільна енергія метаболічної реакції, яку представляє ребро.

Інше застосування найширших шляхів виникає в алгоритмі Форда — Фалкерсона для задачі про максимальний потік. Поступово збільшуючи потік уздовж шляху з максимальною ємністю в залишковій мережі потоку, що приводить до невеликої межі ${\displaystyle O(m\log U)}$ числа прирощень, необхідних для пошуку максимального потоку. Тут ємності ребер є цілими числами, що не перевищують U. Проте, цей аналіз залежить від знаходження точного максимуму ємності. Підходить будь-який шлях із ємністю, що відрізняється від максимальної на постійний коефіцієнт. Комбінування цих ідей наближення з методом збільшення найкоротшого шляху алгоритму Едмондса — Карпа приводить до алгоритму максимального потоку з часом роботи ${\displaystyle O(mn\log U)}$.

Шляхи максимальної місткості і мінімаксні шляхи з одним джерелом і однією цільовою вершиною можна знайти дуже ефективно навіть у моделях обчислень, які дозволяють лише порівняння ваг ребер вхідного графа, а не арифметику з ними. Алгоритм працює зі множиною S ребер, про яку відомо, що вона містить ребро вузького місця оптимального шляху. Спочатку S складається з усіх m ребер графа. На кожній ітерації алгоритму S розбивають на впорядковану послідовність підмножин ${\displaystyle S_{1},S_{2},\dots }$ приблизно однакового розміру. Число підмножин у розбитті вибирають так, що всі точки розбиття між підмножинами можна знайти шляхом кратного знаходження медіан за час O(m). Алгоритм потім перераховує ваги всіх ребер графа за індексом підмножини, що містить ребро, і використовує модифікований алгоритм Дейкстри на графі з оновленими вагами. Ґрунтуючись на результатах цих обчислень, можна обчислити за лінійний час, яка з підмножин містить вагу ребра вузького місця. Потім алгоритм замінює S підмножиною S_i, що містить вагу вузького місця, і починає нову ітерацію з цією множиною S. Число підмножин, на яке можна розбити S, може зростати експоненційно з кожним кроком, так що кількість ітерацій пропорційна ітерованому логарифму ${\displaystyle O(\log ^{\star }n)}$, а повний час виконання буде ${\displaystyle O(m\log ^{\star }n)}$. У моделі обчислення, де вага кожного ребра є машинним цілим числом, використання ітерованих логарифмів у цьому алгоритмі можна замінити на техніку розбиття списку Гана та Торупа, що дозволяє розбити S на ${\displaystyle O({\sqrt {m}})}$ менших частин S_i за один крок, що приводить до лінійної спільної межі за часом.

Множини евклідових точок

Темно-сині стрічки відокремлюють пари цілих гауссових чисел, для яких мінімаксна довжина шляху 2 або більше

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

У теорії чисел нерозв'язана задача про ^[en] запитує, чи обмежена мінімаксна довжина мінімаксних шляхів у гауссових простих чисел. Тобто чи існує стала B, така, що для будь-якої пари p і q в нескінченній множині евклідових точок, визначених гауссовими простими, мінімаксний шлях у гауссових простих між p і q має довжину ребер, що не перевищує B?

Примітки

1. Pollack, 1960, с. 733–736.
2. Shacham, 1992, с. 1217–1221.
3. Wang, Crowcroft, 1995, с. 2129–2133.
4. Schulze, 2011, с. 267–303.
5. Fernandez, Garfinkel, Arbiol, 1998, с. 293–304.
6. Ullah, Lee, Hassoun, 2009, с. 144–150.
7. Ahuja, Magnanti, Orlin, 1993, с. 210–212.
8. Berman, Handler, 1987, с. 115–122.
9. Hu, 1961, с. 898–900.
10. Punnen, 1991, с. 402–404.
11. Malpani, Chen, 2002, с. 175–180.
12. Camerini, 1978, с. 10–14.
13. Kaibel, Peinhardt, 2006.
14. Fernandez, Garfinkel, Arbiol, 1998.
15. Alt, Godau, 1995, с. 75–91.
16. Leclerc, 1981, с. 5–37, 127.
17. Demaine, Landau, Weimann, 2009, с. 341–353.
18. Точніше, єдина можливість, коли метод Шульце не працює, це коли два кандидати мають шляхи однакової ширини.
19. См. Jesse Plamondon-Willard, Board election to use preference voting, May 2008; Mark Ryan, 2008 Wikimedia Board Election results, June 2008; 2008 Board Elections, June 2008; and 2009 Board Elections, August 2009.
20. Duan, Pettie, 2009, с. 384–391.
21. Vassilevska, 2008.
22. Vassilevska, Williams, Yuster, 2007, с. 585–589.
23. Berman, Handler, 1987.
24. Ullah, Lee, Hassoun, 2009.
25. Gabow, Tarjan, 1988, с. 411–417.
26. Han, Thorup, 2002.
27. Han, Thorup, 2002, с. 135–144.
28. Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004, с. 233–249.
29. Gethner, Wagon, Wick, 1998, с. 327–337.

Література

• Maurice Pollack. The maximum capacity through a network // . — 1960. — Т. 8, вип. 5. — С. 733–736. — DOI:10.1287/opre.8.5.733.
• Shacham N. Multicast routing of hierarchical data // IEEE International Conference on Communications (ICC '92). — 1992. — Т. 3. — DOI:10.1109/ICC.1992.268047.
• Zheng Wang, Crowcroft J. Bandwidth-delay based routing algorithms // IEEE Global Telecommunications Conference (GLOBECOM '95). — 1995. — Т. 3. — DOI:10.1109/GLOCOM.1995.502780.
• Markus Schulze. A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method // . — 2011. — Т. 36, вип. 2. — С. 267–303. — DOI:10.1007/s00355-010-0475-4.
• Ullah E., Lee K., Hassoun S. An algorithm for identifying dominant-edge metabolic pathways // IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009). — 2009. — С. 144–150.
• Oded Berman, Gabriel Y. Handler. Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations // . — 1987. — Т. 21, вип. 2. — С. 115–122. — DOI:10.1287/trsc.21.2.115.
• Hu T. C. The maximum capacity route problem // . — 1961. — Т. 9, вип. 6. — DOI:10.1287/opre.9.6.898.
• Navneet Malpani, Jianer Chen. A note on practical construction of maximum bandwidth paths // . — 2002. — Т. 83, вип. 3. — С. 175–180. — DOI:10.1016/S0020-0190(01)00323-4.
• Abraham P. Punnen. A linear time algorithm for the maximum capacity path problem // . — 1991. — Т. 53, вип. 3. — DOI:10.1016/0377-2217(91)90073-5.
• Camerini P. M. The min-max spanning tree problem and some extensions // . — 1978. — Т. 7, вип. 1. — DOI:10.1016/0020-0190(78)90030-3.
• Volker Kaibel, Matthias A. F. Peinhardt. On the bottleneck shortest path problem. — Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2006. — (ZIB-Report 06-22)
• Elena Fernandez, Robert Garfinkel, Roman Arbiol. Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths // . — 1998. — Т. 46, вип. 3. — С. 293–304. — DOI:10.1287/opre.46.3.293.
• Helmut Alt, Michael Godau. Computing the Fréchet distance between two polygonal curves // International Journal of Computational Geometry and Applications. — 1995. — Т. 5, вип. 1–2. — С. 75–91. — DOI:10.1142/S0218195995000064.
• Bruno Leclerc. Description combinatoire des ultramétriques // Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines. — 1981. — Вип. 73. — С. 5–37, 127.
• Erik D. Demaine, Gad M. Landau, Oren Weimann. On Cartesian trees and range minimum queries // Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009. — 2009. — Т. 5555. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-02927-1_29.
• Ran Duan, Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths // Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09). — 2009.
• Virginia Vassilevska, Ryan Williams, Raphael Yuster. All-pairs bottleneck paths for general graphs in truly sub-cubic time // . — New York : ACM, 2007. — DOI:10.1145/1250790.1250876.
• Virginia Vassilevska. Efficient Algorithms for Path Problems in Weighted Graphs. — Carnegie Mellon University School of Computer Science, 2008. — (Ph.D. thesis, Report CMU-CS-08-147)
• Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. 7.3 Capacity Scaling Algorithm // Network Flows: Theory, Algorithms and Applications. — Prentice Hall, 1993. — .
• Harold N. Gabow, Robert E. Tarjan. Algorithms for two bottleneck optimization problems // Journal of Algorithms. — 1988. — Т. 9, вип. 3. — DOI:10.1016/0196-6774(88)90031-4.
• Yijie Han, Thorup M. Integer sorting in O(n√log log n) expected time and linear space // . — 2002. — DOI:10.1109/SFCS.2002.1181890.
• Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh. Approximating geometric bottleneck shortest paths // . — 2004. — Т. 29, вип. 3. — DOI:10.1016/j.comgeo.2004.04.003.
• Ellen Gethner, Stan Wagon, Brian Wick. A stroll through the Gaussian primes // American Mathematical Monthly. — 1998. — Т. 105, вип. 4. — С. 327–337. — DOI:10.2307/2589708.