овжини під зваженому графі
Довжиною шляху між двома вершинами у зваженому графі називається сума ваг ребер, що складають цей шлях. На відміну від незваженого графа наявність ребра між двома вершинами не гарантує, що найкоротший шлях між ними складається з цього ребра. Найчастіше сумарна вага шляху, що складається з двох, трьох і більш ребер може виявитися менше ваги одного ребра, тому навіть для повного графа (тобто графа, між кожною з пар вершин якого існує ребро, а в випадку орієнтованого графа - два ребра, направлених в протилежні сторони) завдання пошуку найкоротшого їх шляхів має сенс. Поняття найкоротшого шляху поки будемо розглядати тільки для графів, всі ребра яких мають ненегативний вагу.
Найбільш просто знайти найкоротший шлях між кожною з пар вершин можна з допомогою алгоритму Флойда [5 - 7], заснованого на тій же ідеї, що і алгоритм Уоршолла. Нехай в елементі матриці A [ i , j ] зберігається довжина найкоротший шляху з вершини i у вершину j , який проходить через деякі вершини з номерами, що не переважаючими k - 1. Якщо ж довжини шляху з вершини i у вершину k і шляху з вершини k в вершину j то такі, що їх сума менше, ніж значення даного елемента матриці, то його слід перевизначити. Тобто у реалізації алгоритму Уоршолла слід замінити операцію and на "+", а or - на знаходження мінімуму з двох величин. Для реалізації алгоритму масив a спочатку слід заповнити елементами матриці суміжності, позначаючи відсутність ребра між двома вершинами "Нескінченністю" - числом, завідомо переважаючим довжину будь-якого шляху в розглянутому графі, але меншим, ніж максимальне значення використовуваного типу даних, щоб було можливо виконувати з ним арифметичні операції. У цьому випадку можна уникнути додаткових перевірок.
Якщо ж нам потрібно знайти сам найкоротший шлях, а не його довжину, то при кожному поліпшенні шляху між двома вершинами ми у відповідному елементі допоміжного масиву (у програмі - w) будемо запам'ятовувати номер тієї вершини, через яку найкоротший шлях проходить, а потім за допомогою елегантного рекурсивної процедури будемо його друкувати. Ідея рекурсії полягає в тому, що якщо ми знаємо, що найкоротший шлях від вершини i до вершини j проходить через вершину k , то ми можемо звернутися до тієї ж самої процедури з частинами шляху від i до k і від k до j . Рекурсивний спуск закінчується, коли на найкоротшому шляху між двома вершинами не опиниться проміжних вершин.
Наведемо фрагмент програми, що реалізує алгоритм Флойда ідрукує найкоротші шляхи між усіма парами вершин графа.
procedure way (i, j: integer);
{друкує шлях між вершинами i та j}
begin
if w [i, j] = 0 then write ('', j)
{друкуємо тільки вершину j,
щоб уникнути повторів}
else
begin
way (i, w [i, j]); way (w [i, j], j)
end
end;
begin
... {заповнюємо матрицю суміжності}
for k: = 1 to nn do
for i: = 1 to nn do
for j: = 1 to nn do
if a [i, k] + a [k, j]
begin
a [i, j]: = a [i, k] + a [k, j];
w [i, j]: = k
end;
for i: = 1 to nn do
for j: = 1 to nn do
begin
write (i);
if i <> j then way (i, j);
writeln
end
end.
Алгоритм Флойда хороший всім, крім одного: він вимагає зберігати матрицю суміжності, а це не завжди можливо. Крім того, для визначення довжини найкоротшого шляху між двома конкретними вершинами, його спростити неможливо (Тобто все одно доведеться рахувати шляху між усіма парами вершин). Якщо вага будь-якого ребра в графі обчислюється за деякою формулою (наприклад, як відстань між двома точками на площині, якщо такими є вершини нашого графа), то матрицю суміжності можна не створювати взагалі, а в процесі виконання програми звертатися до функції обчислення ваги ребра, що з'єднує вершини i і j : a ( i , j ).
У цьому випадку для визначення найкоротшого шляху між вершинами s і t використовують алгоритм Дейкстри [5 - 7]. Всі вершини в процесі роботи цього алгоритму розбиті на дві множини: ті, до яких найкоротший шлях з вершини s вже відомий (у програмі вони помічені значеннями true одновимірного булевского масиву b) і всі інші. Cначала в першому безлічі знаходиться тільки вершина s . На кожному кроці до нього додається одна з вершин, поточне відоме відстань до якої мінімально серед всіх вершин з другої множини, позначимо її p . Спочатку поточні відстані (у програмі вони зберігаються в одновимірному масиві l) від s до інших вершин дорівнюють ВҐ, а відстань до s дорівнює 0, p також дорівн...
