Найкоротші шляхи між усіма парами вершин

У цьому розділі ми розглянемо два класи, які вирішують задачу пошуку найкоротших шляхів для всіх пар вершин. Алгоритми, які ми реалізуємо, безпосередньо узагальнюють два базових алгоритму, які були розглянуті в "Орграф і DAG-графи" для завдання транзитивного замикання. Перший метод полягає у виконанні алгоритму Дейкстри з кожної вершини для отримання найкоротших шляхів з цієї вершини в усі інші. Якщо реалізувати чергу з пріоритетами за допомогою пірамідального дерева, то при такому підході час виконання в гіршому випадку буде пропорційно VE lgV, а використання d-арного пірамідального дерева дозволяє поліпшити цю межу для багатьох типів мереж до VE. Другий метод, який дозволяє безпосередньо вирішити це завдання за час, пропорційне V3, є розширенням алгоритму Уоршалла, і називається алгоритм Флойда (Floyd).

Обидва класи реалізують інтерфейс АТД абстрактних найкоротших шляхів для знаходження найкоротших відстаней і шляхів. Цей інтерфейс, який показаний в програмі 21.2, є узагальненням інтерфейсу абстрактного транзитивного замикання зваженого орграфа для з'ясування зв'язності в Орграф, який був вивчений в "Орграф і DAG-графи" . У реалізаціях обох класів конструктор вирішує завдання пошуку найкоротших шляхів для всіх пар вершин і зберігає результат в приватних членах даних. Ці дані використовуються функціями відповідей на запити, які повертають довжину найкоротшого шляху з однієї заданої вершини в іншу, а також перше або останнє ребро в дорозі. Основне призначення реалізації такого АТД - його практичне використання для реалізації алгоритмів пошуку найкоротших шляхів для всіх пар вершин.

Програма 21.3 являє собою приклад клієнтської програми, яка обчислює зважений діаметр (weighted diameter) мережі за допомогою інтерфейсу АТД для пошуку всіх найкоротших шляхів. Вона переглядає всі пари вершин і знаходить таку пару, для якої довжина найкоротшого шляху максимальна, а потім обходить шлях, ребро за ребром. на Мал. 21.13 показаний шлях, обчислений цією програмою для нашої демонстраційної евклідової мережі.

Програма 21.2. АТД найкоротших шляхів для всіх пар вершин

Всі наші рішення задачі пошуку найкоротших шляхів для всіх пар вершин мають вигляд класів з конструктором і двома функціями відповідей на запити. Перша функція, dist, повертає довжину найкоротшого шляху з першого аргументу в другій, а друга - одна з двох можливих функцій обчислення шляхи: або path, що повертає покажчик на перше ребро в найкоротшому шляху, або pathR, що повертає покажчик на останнє ребро в найкоротшому шляху. Якщо такий шлях не існує, то функція path повертає 0, а результат dist не визначений.

Ми використовуємо функції path або pathR в залежності від того, що зручніше для розглянутого алгоритму; можливо, на практиці одну з них (або обидві) слід помістити в інтерфейс, а в реалізаціях використовувати різні допоміжні функції, як описано в розділі 21.1 і в вправах в кінці цього розділу.

template <class Graph, class Edge> class SPall {public: SPall (const Graph &); Edge * path (int, int) const; Edge * pathR (int, int) const; double dist (int, int) const; };

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

Мал.21.13.

Діаметр мережі

Діаметр мережі - це найбільший елемент в матриці всіх найкоротших шляхів мережі, тобто довжина найдовшого з найкоротших шляхів, показаного тут для нашої демонстраційної евклідової мережі.

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

Якщо очікується лише кілька запитів, то можна обійтися без попередньої обробки, і просто виконувати для кожного запиту алгоритм для одного джерела; проте в найбільш поширених ситуаціях потрібні більш досконалі алгоритми (див. вправи 21.48-21.50). Це завдання узагальнює задачу, якій присвячена більша частина "Орграф і DAG-графи" - підтримка швидких запитів досяжності при обмеженні на доступну пам'ять.

Перша розглянута нами реалізація функції АТД пошуку найкоротших шляхів для всіх пар вершин вирішує цю задачу, використовуючи алгоритм Дейкстри для вирішення завдання з одним джерелом для кожної вершини. C ++ дозволяє записати цей метод безпосередньо (див. Програму 21.4): для вирішення завдання з одним джерелом для кожної вершини створюється вектор об'єктів SPT. Цей метод узагальнює метод на основі BFS для невиважених неорієнтованих графів, який був розглянутий в "Види графів і їх властивості" . Він також схожий на використання DFS в програмі 19.4, де обчислюється транзитивне замикання невиваженого орграфа з початком в кожній вершині.

Програма 21.3. Обчислення зваженого діаметра мережі

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

template <class Graph, class Edge> double diameter (Graph & G) {int vmax = 0, wmax = 0; allSP <Graph, Edge> all (G); for (int v = 0; v <GV (); v ++) for (int w = 0; w <GV (); w ++) if (all.path (v, w)) if (all.dist (v, w )> all.dist (vmax, wmax)) {vmax = v; wmax = w; } Int v = vmax; cout << v; while (v! = wmax) {v = all.path (v, wmax) -> w (); cout << << v; } Return all.dist (vmax, wmax); }

Лемма 21.7. За допомогою алгоритму Дейкстри можна знайти все найкоротші шляхи в мережі з невід'ємними вагами за час, пропорційне , Де d = 2, якщо E <2 V і d = E / V в іншому випадку.

Доведення. Безпосередньо випливає з леми 21.6.

Як і в задачах про найкоротших шляхах з одного джерела і завдання обчислення MST, ця межа занадто обережна; для типових графів час виконання зазвичай одно VE.

Для порівнянь цієї реалізації з іншими корисно розглянути матриці, неявно утворені структурою вектора векторів приватних членів даних. Вектори wt утворюють саме матрицю відстаней, розглянуту в розділі 21.1: елемент цієї матриці на перетині рядка s і шпальти t містить довжину найкоротшого шляху з s в t. Як показано на Мал. 21.8 і 21.9, вектори spt утворюють транспоновану матрицю шляхів: елемент на перетині рядка s і шпальти t вказує на останнє ребро в найкоротшому шляху з s в t.

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

Рекомендований метод вирішення задачі пошуку найкоротших шляхів для всіх пар вершин в насичених графах був розроблений Р. Флойдом (R. Floyd). Він точності повторює метод Уоршалла, тільки замість використання логічної операції АБО для відстеження існування шляхів він перевіряє відстані для кожного ребра, щоб визначити, чи є це ребро частиною нового, більш короткого шляху.

Програма 21.4. Алгоритм Дейкстри для пошуку всіх найкоротших шляхів

Цей клас використовує алгоритм Дейкстри, щоб побудувати SPT для кожної вершини. Це дозволяє виконувати функції pathR і dist для будь-якої пари вершин.

#include "SPT.cc" template <class Graph, class Edge> class allSP {const Graph & G; vector <SPT <Graph, Edge> *> A; public: allSP (const Graph & G): G (G), A (GV ()) {for (int s = 0; s <GV (); s ++) A [s] = new SPT <Graph, Edge> (G , s); } Edge * pathR (int s, int t) const {return A [s] -> pathR (t); } Double dist (int s, int t) const {return A [s] -> dist (t); }};

Як вже було сказано, у відповідній абстрактної постановці алгоритми Флойда і Уоршалла ідентичні (див. "Орграф і DAG-графи" і 21.1).

Програма 21.5 містить функцію АТД пошуку найкоротших шляхів для всіх пар вершин, яка реалізує алгоритм Флойда. У ній явно використовуються матриці з розділу 21.1 як приватні члени даних: вектор векторів d розміром V х V для матриці відстаней і ще один вектор векторів p розміром V х V для таблиці шляхів. Для кожної пари вершин s і t конструктор заносить в d [s] [t] довжину найкоротшого шляху з s в t (яка повертається функцією-членом dist), а в p [s] [t] - індекс наступної вершини на найкоротшому шляху з s в t (який повертається функцією-членом path). Реалізація заснована на операції релаксації шляху, розглянутої в розділі 21.1.

Програма 21.5. Алгоритм Флойда для пошуку всіх найкоротших шляхів

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

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

template <class Graph, class Edge> class allSP {const Graph & G; vector <vector <Edge *>> ​​p; vector <vector <double>> d; public: allSP (const Graph & G): G (G), p (GV ()), d (GV ()) {int V = GV (); for (int i = 0; i <V; i ++) {p [i] .assign (V, 0); d [i] .assign (V, V); } For (int s = 0; s <V; s ++) for (int t = 0; t <V; t ++) if (G.edge (s, t)) {p [s] [t] = G.edge (s, t); d [s] [t] = G.edge (s, t) -> wt (); } For (int s = 0; s <V; s ++) d [s] [s] = 0; for (int i = 0; i <V; i ++) for (int s = 0; s <V; s ++) if (p [s] [i]) for (int t = 0; t <V; t ++) if (s! = t) if (d [s] [t]> d [s] [i] + d [i] [t]) {p [s] [t] = p [s] [i]; d [s] [t] = d [s] [i] + d [i] [t]; }} Edge * path (int s, int t) const {return p [s] [t]; } Double dist (int s, int t) const {return d [s] [t]; }};

Лемма 21.8. За допомогою алгоритму Флойда можна знайти все найкоротші шляхи в мережі за час, пропорційне V3.

Доведення. Час виконання очевидно зі структури коду. Доведення коректності алгоритму ми проведемо по індукції точно так же, як для алгоритму Уоршалла. i-я ітерація циклу обчислює найкоротший шлях в мережі з s в t, який не містить вершин з індексами більше i (крім, можливо, кінцевих вершин s і t). Вважаючи, що це твердження істинне для i-ой ітерації циклу, покажемо, що воно істинне і для (i + 1) -ої ітерації. Будь найкоротший шлях з s в t, який не містить вершин з індексами, великими i + 1, або (1) є шляхом з s в t, який знайдений в попередній ітерації циклу і по індуктивному припущенню имееет довжину d [s] [t] і не містить вершин з індексами більше i; або (2) складено із шляхів з s в i і з i в t, жоден з яких не містить вершин з індексами більше i, і в цьому випадку внутрішній цикл встановлює d [s] [t].

на Мал. 21.14 показана докладна траса виконання алгоритму Флойда для нашої демонстраційної мережі. Якщо перетворити кожен порожній елемент в 0 (вказівка ​​на відсутність ребра), а кожен непорожній елемент - в 1 (вказівка ​​на наявність ребра), то ці матриці описують роботу алгоритму Уоршалла точно так же, як на Мал. 19.15 . У разі алгоритму Флойда непусті елементи не тільки вказують існування шляху, а й дають інформацію про відомого найкоротшому шляху. Елемент в матриці відстаней містить довжину відомого найкоротшого шляху, який з'єднує вершини, відповідні цьому рядку і стовпцю; відповідний елемент в матриці шляхів дає наступну вершину на цьому шляху. У міру заповнення матриць непорожніми елементами алгоритм Уоршалла просто перевіряє ще раз, з'єднують нові шляхи пари вершин, які вже з'єднані відомими шляхами. На відміну від цього, алгоритм Флойда повинен перевірити (і при необхідності оновити) кожен новий шлях, щоб переконатися, що він призводить до більш коротким шляхах.

Порівнюючи оцінки часу виконання в гіршому випадку для алгоритмів Дейкстри і Флойда, можна отримати той же результат для алгоритмів пошуку найкоротших шляхів для всіх пар вершин, що і для відповідних алгоритмів транзитивного замикання в "Орграф і DAG-графи" . Зрозуміло, що для розріджених мереж більш підходить виконання алгоритму Дейкстри з кожної вершини, оскільки час роботи близько до VE. У міру зростання насиченості графа з ним все більше конкурує алгоритм Флойда, який завжди вимагає часу, пропорційного V3 (див. Вправу 21.67); він широко використовується зважаючи на простоту реалізації.

Більш істотна відмінність між цими алгоритмами, яке докладно розглядається в розділі 21.7, полягає в тому, що алгоритм Флойда ефективний навіть на мережах, де можливі негативні ваги (за умови, що немає негативних циклів). Як було сказано в розділі 21.2, метод Дейкстри в таких графах не обов'язково знаходить найкоротші шляхи.

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

Мал.21.14.

алгоритм Флойда

Ця послідовність показує побудова матриць найкоротших шляхів для всіх пар вершин за допомогою алгоритму Флойда. Для i від 0 до 5 (зверху вниз), ми розглядаємо для всіх s і t всі шляхи з s в t, в яких немає проміжних вершин, великих i (заштриховані вершини). Спочатку єдиними такими шляхами є ребра мережі, тому матриця відстаней (в центрі) представляє собою матрицю суміжності графа, а в матрицю шляхів (праворуч) для каждогоребра st заноситься p [s] [t] = t. Для вершини 0 (вгорі) алгоритм знаходить, що шлях 3-0-1 коротше сигнального значення, яке означає відсутність ребра 3-1, і відповідним чином оновлює матриці. Це не робиться для шляхів на зразок 3-0-5, яка не коротше відомого шляху 3-5. Далі алгоритм розглядає шляхи, що проходять через 0 і 1 (другий ряд зверху) і знаходить нові коротші шляхи 0-1-2, 0-1-4, 3-0-1-2, 3-0-1-4 і 5 -1-2. У третьому ряду зверху показані поновлення, відповідні більш коротким шляхах через 0, 1, 2 і т.д.

Чорні числа, записані поверх сірих в матрицях, вказують на ситуації, де алгоритм знаходить більш короткий шлях, ніж знайдений раніше. Наприклад, в рядку 3 і стовпці 2 в нижньому ряду поверх 1.37 записано 0.91, оскільки алгоритм виявив, що шлях 3-5-4-2 коротше шляху 3-0-1-2.

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

вправи

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

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

21.41. Покажіть в стилі Мал. 21.9 результат застосування алгоритму Дейкстри для обчислення всіх найкоротших шляхів в мережі, визначеної у вправі 21.1.

21.42. Покажіть в стилі Мал. 21.14 результат застосування алгоритму Флойда для обчислення всіх найкоротших шляхів в мережі, визначеної у вправі 21.1.

21.43. Об'єднайте програму 20.6 з програмою 21.4 для реалізації інтерфейсу АТД пошуку найкоротших шляхів для всіх пар вершин (на основі алгоритму Дейкстри) в насичених мережах, який підтримує виклики функції path, але не обчислює явно зворотний мережу. Чи не визначайте окрему функцію для вирішення завдання з одним джерелом - помістіть код з програми 20.6 безпосередньо у внутрішній цикл і зберігайте результати безпосередньо в приватних членах даних d і p, як в програмі 21.5.

21.44. Емпірично порівняйте в стилі таблиці 20.2 алгоритм Дейкстри (програма 21.4 і вправу 21.43) і алгоритм Флойда (програма 21.5) для різних мереж (див. Вправи 21.4-21.8).

21.45. Емпірично визначте, скільки разів алгоритми Флойда і Дейкстри оновлюють значення в матриці відстаней для різних мереж (див. Вправи 21.4-21.8).

21.46. Наведіть матрицю, в якій елемент в рядку s і стовпці t дорівнює кількості різних простих спрямованих шляхів, що з'єднують s і t на Мал. 21.1 .

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

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

21.49. Розробіть реалізацію абстрактного класу АТД пошуку найкоротших шляхів для розріджених графів, яка використовує обсяг пам'яті, істотно менший O (V2), але підтримує запити за час, набагато менше O (V). Вказівка. Обчисліть все найкоротші шляхи для підмножини вершин.

21.50. Розробіть реалізацію абстрактного класу АТД пошуку найкоротших шляхів для розріджених графів, яка використовує обсяг пам'яті, істотно менший O (V2), і підтримує (за допомогою рандомізації) запити за лінійне очікуваний час.

21.51. Розробіть реалізацію абстрактного класу АТД пошуку найкоротших шляхів, в якій використовується ледачий підхід застосування алгоритму Дейкстри: SPT-дерево (і пов'язаний з ним вектор відстаней) для вершини s будується при першому запиті клієнтом найкоротшого шляху з s, а на випадок повторних запитів вибирається готова інформація.

21.52. Змініть АТД найкоротших шляхів і алгоритм Дейкстри, щоб обчислювати найкоротші шляхів в мережах, в яких ваги мають і вершини, і ребра. Чи не переробляйте уявлення графа (метод описаний у вправі 21.4), а змініть код.

21.53. Побудуйте невелику модель авіамаршрутів і часів перельоту - можливо, на основі ваших подорожей. Скористайтеся рішенням вправи 21.52 для обчислення найбільш швидкого шляху від одного з пунктів до іншого. Потім протестуйте отриману програму на реальних даних (див. Вправу 21.5).