Як знайти «маршрути» найкоротших шляхів усіх пар за допомогою алгоритму Флойда-Воршалла в C#

вступ

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

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

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

Трохи відомої теорії…

Перш ніж заглибитися в код і тести, давайте переглянемо теорію того, як працює алгоритм Флойда-Воршалла.

Ось текстовий опис алгоритму:

1. Ми починаємо з представлення графа ( G ) розміром N як матриці ( W ) розміром N x N , де кожна комірка W[i,j] містить вагу ребра від вершини i до вершини j (див. Малюнок 1). У випадках, коли між вершинами немає ребер, для клітинки встановлюється спеціальне значення NO_EDGE (показано темними клітинками на малюнку 1).

   
   

2. Відтепер ми говоримо – W[i,j] містить відстань між вершинами i та j .

   
   

3. Далі ми беремо вершину k і повторюємо всі пари вершин W[i,j] перевіряючи, чи відстань i ⭢ k ⭢ j менша за відому на даний момент відстань між i та j .

   
   

4. Найменше значення зберігається в W[i,j] , а крок №3 повторюється для наступного k доки всі вершини G не будуть використані як k .

Ось псевдокод:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm

Після завершення кожна клітинка W[i,j] матриці W або містить відстань найкоротшого шляху між вершинами i та j , або значення NO_EDGE , якщо шляху між ними немає.

Як я вже згадував на початку, наявність лише цієї інформації унеможливлює реконструкцію маршрутів між цими вершинами. Тож… що ми маємо зробити, щоб мати змогу реконструювати ці маршрути?

Ну… це може здатися очевидним, але… нам потрібно зібрати більше даних!

… Трохи тієї ж теорії, але з іншого боку

Суть алгоритму Флойда-Варшалла полягає у відсіку відомої відстані W[i,j] з відстанню потенційно нового шляху від i до j через проміжну вершину k .

Я приділяю таку увагу цій деталі, тому що це ключ до того, як ми можемо зберегти інформацію про маршрут. Візьмемо попередній граф з 5 вершин (див. Малюнок 2) і виконаємо на ньому алгоритм Флойда-Воршалла.

Спочатку ми знаємо про всі ребра графа, що дає нам такі шляхи: 0 ⭢ 1 :2 , 0 ⭢ 4 :10 , 1 ⭢ 3 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 і 3 ⭢ 4 :3 .

Ми також знаємо, що немає ребер, що ведуть до вершини 0 , тому виконання алгоритму для k = 0 не має сенсу. Також очевидно, що існує єдине ребро ( 0 ⭢ 1 ), що веде від вершини 0 до вершини 1 , що також робить виконання всіх i != 0 ( i «звідки» тут) абсолютно безглуздим, а оскільки вершина 1 має ребра з 2 і 4 , також немає сенсу виконувати алгоритми для будь-якого j , яке не є 2 або 4 ( j тут «до»).

Тому нашим першим кроком буде виконання алгоритму для k = 1 , i = 0 і j = 2,4 .

Ми знайшли два шляхи: новий шлях ( 0 ⭢ 1 ⭢ 2 ) і ярлик ( 0 ⭢ 1 ⭢ 4 ). Обидва проходять через вершину 1 . Якщо ми не збережемо цю інформацію (той факт, що ми дійшли до 2 і 4 через 1 ) десь прямо зараз, вона буде втрачена назавжди (а це зовсім протилежне тому, чого ми хочемо).

Отже, що нам робити? Ми оновимо матрицю W новими значеннями (див. Малюнок 3a), а також збережемо значення k (що є k = 1 ) у клітинках R[0,2] і R[0,4] нової матриці R того самого розміру як матриця W , але ініціалізована значеннями NO_EDGE (див. Малюнок 3b).

Зараз не зосереджуйтесь на тому, що таке матриця R Давайте просто продовжимо і виконаємо алгоритм для наступного k = 2 .

Тут ми зробимо той самий аналіз (щоб зрозуміти, які комбінації має сенс виконувати), як і для k = 1, але цього разу ми використаємо матрицю W замість графа G Подивіться на матрицю W , особливо в стовпці №2 і рядку №2 (Малюнок 4).

Тут ви бачите, що є два шляхи до вершини 2 від вершини 0 і від вершини 1 (стовпець №2) і два шляхи від вершини 2 до вершини 3 і до вершини 4 (рядок №2). Знаючи це, має сенс виконувати алгоритм лише для комбінацій k = 2 , i = 0,1 та j = 3,4 .

Як ми вже робили раніше, ми оновлюємо клітинки W[0,3] , W[0,4] , W[1,3] , W[1,4] новими відстанями та клітинками R[0,3] , R[0,4] , R[1,3] і R[1,4] з k = 2 (див. Малюнок 5).

Залишилося обробити лише k = 3 (оскільки немає ребер, що ведуть від вершини 4 до будь-якої іншої вершини на графі).

Знову ж таки, давайте подивимося на матрицю W (Малюнок 6).

Відповідно до матриці W є три шляхи до вершини 3 з вершин 0 , 1 і 2 (стовпець №3), а також один шлях з вершини 3 до вершини 4 (рядок №3). Тому ми маємо такі шляхи для обробки:

Це була остання ітерація алгоритму. Все, що залишилося, це оновити клітинки W[0,4] , W[1,4] , W[2,4] новими відстанями та встановити клітинки R[0,4] , R[1,4] , R[2,4] до 3 .

Ось що ми маємо в кінці алгоритму (Малюнок 7).

Як ми знаємо з попереднього посту , матриця W тепер містить усі пари найкоротших шляхів у графі G Але що зберігається всередині матриці R ?

Повернення додому

Щоразу, коли ми знаходили новий найкоротший шлях, ми оновлювали відповідну клітинку матриці R поточним значенням k . Хоча спочатку ця дія може виглядати загадковою, вона має дуже просте значення – ми зберігаємо вершину, з якої ми досягли вершини призначення: i ⭢ k ⭢ j (тут ми досягаємо j безпосередньо з k ).

Цей момент є вирішальним. Оскільки знання вершини, з якої ми прийшли, дозволяє нам перебудувати маршрут, рухаючись назад (як омар) від вершини j («до») до вершини i («від»).

Ось текстовий опис алгоритму перебудови маршруту від i до j :

1. Підготуйте порожній динамічний масив X .
2. Почніть зі зчитування значення z із комірки R[i,j] .
3. Якщо z дорівнює NO_EDGE , то маршрут від i до j знайдено, і ми повинні перейти до кроку №7.
4. Додайте z до динамічного масиву X .
5. Прочитайте значення комірки R[i,z] у z .
6. Повторюйте кроки №3, №4 і №5, доки не буде досягнуто умови виходу в №3.
7. Додайте i до X.
8. Додайте j до X .
9. Тепер динамічний масив X містить маршрут від i до j .

У псевдокоді це виглядає ще простіше:

 algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm

Давайте спробуємо це на нашому графі G і перебудуємо маршрут від вершини 0 до вершини 4 (див. Малюнок 8).

Ось текстовий опис наведеної вище ілюстрації:

1. Ми починаємо зі зчитування значення з R[0,4] , що призводить до 3 . Згідно з алгоритмом, це означає, що маршрут йде до вершини 4 з вершини 3 (показано СИНИМ кольором).

   
   

2. Оскільки значення R[0,4] не є NO_EDGE , ми продовжуємо і читаємо значення R[0,3] , що призводить до 2 (показано ЗЕЛЕНИМ кольором).

   
   

3. Знову ж таки, оскільки значення R[0,3] не є NO_EDGE , ми продовжуємо і читаємо значення R[0,2] , що призводить до 1 (показано ЧЕРВОНИМ).

   
   

4. Нарешті ми зчитуємо значення R[0,1] , яке призводить до значення NO_EDGE , що означає, що більше немає вершин, крім 0 і 4 , які вносять свій внесок у маршрут. Таким чином, результуючий маршрут: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 , що, якщо ви подивитеся на граф, справді відповідає найкоротшому шляху від вершини 0 до вершини 4 .

Вдумливий читач може запитати:

Це дуже гарне запитання. Ми впевнені, тому що оновлюємо матрицю R новим значенням, коли оновлюємо значення найкоротшого шляху в матриці W . Отже, зрештою, кожен рядок матриці R містить дані, пов’язані з найкоротшими шляхами. Ні більше, ні менше.

Тепер ми закінчили з теорією, настав час впровадження.

Реалізація в C#

У попередній публікації , окрім реалізації оригінальної версії алгоритму Флойда-Воршалла, ми також інтегрували різні оптимізації: підтримку розріджених графів, паралелізму та векторизації, і, зрештою, ми також об’єднали їх усі.

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

Інтеграція в оригінальний алгоритм

У це може бути важко повірити, але для інтеграції запам’ятовування маршруту в оригінальну версію алгоритмів все, що нам потрібно зробити, це:

1. Розширте підпис функції, щоб включити матрицю R як окремий параметр – int[] routes .

   
   

2. Зберігайте k у routes кожного разу, коли змінюється найкоротший шлях (рядки: 2 і 14).

Це все. Всього півтора рядка коду:

 public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Інтеграція в векторизований алгоритм

Інтеграція у векторизовану (з підтримкою розріджених графів) версію потребує трохи більше зусиль, однак концептуальні кроки ті самі:

1. Розширте підпис функції, щоб включити матрицю R як окремий параметр – int[] routes .

   
   

2. На кожній ітерації ініціалізуйте новий вектор k значень (рядок: 6).

   
   

3. Зберігайте вектор k значень у routes кожного разу, коли змінюється найкоротший шлях (рядки: 31-32).

   
   

4. Оновіть невекторизовану частину алгоритму так само, як ми оновили оригінальний алгоритм (рядок: 41).

 public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Бенчмаркінг

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

Ось два набори тестів: із і без (обидва виконують оригінальну та векторизовану версії алгоритму). Усі тести були виконані за допомогою BenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) на машині, оснащеній процесором Intel Core i5-6200U CPU 2,30 ГГц (Skylake) і під керуванням Windows 10.

Усі експерименти проводилися на попередньо визначеному наборі графів, які використовувалися в попередній публікації : 300, 600, 1200, 2400 і 4800 вершин.

Нижче наведено результати тестування, де методи Baseline і BaselineWithRoutes відповідають оригінальній версії алгоритму, а методи SpartialVectorOptimisations і SpartialVectorOptimisationsWithRoutes відповідають векторизованій (з підтримкою розріджених графіків) версії алгоритму.

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

Виглядає це дуже заплутано (і якщо так – настійно раджу послухати цю передачу з Денисом Бахваловим і Андрієм Акіншиним, щоб краще зрозуміти, які хитрощі можуть впливати на вимірювання). Моя найкраща думка полягає в тому, що «заплутує» поведінка спричинена високою продуктивністю кешу ЦП (оскільки графіки недостатньо великі, щоб наситити кеші). Частково ця теорія базується на « жирному » зразку, де ми бачимо значне погіршення на найбільшому графіку. Однак я не перевіряв це.

Загалом тест показує, що якщо ми не говоримо про надзвичайно високопродуктивні сценарії та величезні графіки, цілком нормально інтегрувати запам’ятовування маршруту в обидва алгоритми за замовчуванням (але майте на увазі, що це подвоїть споживання пам’яті, оскільки нам потрібно виділити дві матриці W і R замість однієї).

Залишається лише реалізація алгоритму перебудови маршруту.

Реалізація алгоритму перебудови маршруту

Реалізація алгоритмів перебудови маршруту в C# проста і майже повністю відображає продемонстрований раніше псевдокод (ми використовуємо LinkedList<T> для представлення динамічного масиву):

 public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; }

Наведений вище алгоритм не є досконалим і, безумовно, може бути вдосконалений. Найпростіше вдосконалення, яке ми можемо зробити, це попередньо виділити масив розміром sz і заповнити його у зворотному порядку:

 public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); }

Хоча ця «оптимізація» зменшує кількість виділень до одного, вона не обов’язково робить алгоритм «швидшим» або «виділяє менше пам’яті», ніж попередній. Справа в тому, що якщо нам потрібно мати маршрут, упорядкований від i до j , нам завжди доведеться «перевертати» дані, які ми отримуємо з матриці R , і від цього неможливо уникнути.

Але якщо ми можемо представити дані у зворотному порядку, ми зможемо використовувати LINQ і уникнути будь-яких непотрібних розподілів:

 public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; }

Варіантів того, як «змінити» або «поліпшити» цей код, може бути ще багато. Тут важливо пам’ятати: будь-яка «зміна» має негативні сторони з точки зору пам’яті або циклів ЦП.

Сміливо експериментуйте! Можливості майже безмежні!

Висновок

У цьому дописі ми глибоко занурилися в теорію, що лежить в основі алгоритму Флойда-Воршалла, і розширили його можливістю запам’ятовувати «маршрути» найкоротших шляхів. Потім ми оновили реалізації C# (оригінальні та векторизовані) з попереднього допису . Зрештою, ми реалізували кілька версій алгоритму для перебудови «маршрутів».

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

Сподіваюся, вам сподобалося прочитати, і до зустрічі наступного разу!