Алгоритми обробки графів
Алгоритми обробки графів аналогічні алгоритмам обробки нелінійних списків, до яких можуть бути віднесені графи. Як приклад приведемо програму, що знаходить найкоротший шлях між двома зазначеними вершинами зв'язного кінцевого графа.
АЛГОРИМ ДЕЙКСТРИ.Нехай дана частина карти дорожньої мережі і потрібно знайти найкращий маршрут від міста 1 до міста 5 (рис. 7.10).
Така задача виглядає досить просто, але "найкращий" маршрут можуть визначати багато факторів. Наприклад: відстань у кілометрах; час проходження маршруту з урахуванням обмежень швидкості; очікувана тривалість поїздки з урахуванням дорожніх умов і щільності руху; затримки, викликані проїздом через міста або об'їздом міст; число міст, яких необхідно відвідати, наприклад, з метою доставки вантажів. Задачі про найкоротші шляхи відносяться до фундаментальних задач комбінаторної оптимізації. Серед відомих алгоритмів для відшукання найкоротшого шляху один із кращих належить Дейкстрі.
Розглянемо граф, зображений на рис.7.11, що задає зв'язок між містами на карті доріг. Представимо граф матрицею суміжності A, у якій: A(і,j)-довжина ребра між вузлами і та j. Використовуючи отриману матрицю і матриці, що відбивають інші фактори, можна визначити найкоротший шлях. Алгоритм Дейкстри, що визначає найкоротшу відстань від даної вершини до кінцевої, створює множину вузлів, для яких найкоротший шлях від вихідного вузла вже відомий. На кожному кроці до множини вузлів додається той вузол (з тих що лишилися), відстань до якого сама менша ніж до інших (від вихідного вузла).
(1) (2) (3) (4) (5)
0 12 18 10 -
12 0 6 - 9
А = 18 6 0 7 3
10 - 7 0 15
- 9 3 15 0
” - ” - ребро відсутнє
Рис.7.11. Частина дорожньої карти, представлена у вигляді зваженого
графа і його матриці суміжності
В програмному прикладі 7.1 процедура визначає найкоротшу відстань від початкової вершини V0 до кінцевої вершини W у зв’язному графі з додатними вагами. Результатом роботи є дерево найкоротших шляхів з коренем V0.
Вхідні і вихідні перемінні:
V0 початкова вершина. W кінцева вершина.
A(I,J) довжина ребра, що з’єднує вершини I і J. Якщо ребро відсутнє, то A(I,J)=10000 (довільному великому числу).
N вершини в графі пронумеровані 1,...,N.
FROM(I) містить I-і асис в деpеві коротших шляхів від асист FROM(I) до асист TU(I)
LENGTH(I) довжина LENGTH(I).
EDGES число ребер у дереві найкоротших шляхів на даний момент.
Внутрішні перемінні
DIST(I) найкоротша відстань від UNDET(I) до часткового дерева найкоротших шляхів.
NEXT чергова вершина, що додається до дерева найкоротших шляхів.
NUMUN число невизначених вершин.
UNDET(I) список невизначених вершин.
VERTEX(I) вершини часткового дерева найкоротших шляхів, що лежать на найкоротшому шляху від UNDET(I) до V0.
{==== Програмний приклад 7.1 ======}
{ Алгоритм Дейкстры }
Program ShortWay;
Const n=5; max=10000;
Var a: Array [1..n,1..n] of Integer;
v0,w,edges: Integer;
from,tu,length: Array [1..n] of Integer;
Procedure adjinit; { Процедура задає ваги ребер графа за допомогою визначення його матриці суміжності A розміром N x N }
Var і,j: Integer;
Begin { „Обнуління” матриці (вершини не зв’язані) }
For i:=1 to n do
For j:=1 to n do a[i,j]:=max;
For i:=1 to n do a[i,i]:=0;
{ Завдання довжин ребер, що з’єднують суміжні вузли графа }
a[1,2]:=12; a[1,3]:=18; a[1,4]:=10; a[2,1]:=12; a[2,3]:=6; a[2,5]:=9; a[3,1]:=18; a[3,2]:=6; a[3,4]:=7; a[3,5]:=3; a[4,1]:=10; a[4,3]:=7; a[4,5]:=15; a[5,2]:=9; a[5,3]:=3; a[5,4]:=15;
End;
Procedure printmat; {Вивід матриці суміжності A зваженого графа }
Var і,j: Integer;
Begin writeln;
writeln(‘Матриця суміжності зваженого графа (‘,n,’х’,n,’):’);
writeln;
For i:=1 to n do
Begin write (‘¦’);
For j:=1 to n do
If a[i,j]=max Then write(‘ ----‘) Else write(a[i,j]:6);
writeln(‘ ¦’)
End; writeln;
writeln (‘ („-і-і” – ребро відсутнє)’)
End;
Procedure dijkst;
Label stpoint;
Var dist,undet,vertex: array[1..n] of Integer;
next,numun,i,j,k,l,jk: Integer;
Begin
edges:=0; next:=v0; numun:=n-1;
For i:=1 to n do
Begin undet[i]:=i; dist[i]:=a[v0,i]; vertex[i]:=v0 End;
undet[v0]:=n; dist[v0]:=dist[n];
goto stpoint;
Repeat { Виключення визначеної вершини зі списку невизначених}
dist[k]:=dist[numun]; undet[k]:=undet[numun];
vertex[k]:=vertex[numun];
dec(numun); { чи залишилися невизначені вершини ? }
{ Відновлення найкоротшої відстані до всіх невизначених вершин }
For i:=1 to numun do
Begin j:=undet[i]; jk:=l+a[next,j];
If dist[i]>jk Then Begin vertex[i]:=next; dist[i]:=jk End
End;
stpoint:{Запам’ятовування найкоротшого асист.до невизначеної вершини}
k:=1; l:=dist[1];
For i:=1 to numun do
If dist[i]<l Then Begin l:=dist[i]; k:=i End;
{ Додавання ребра до дерева найкоротших шляхів }
inc(edges); from[edges]:=vertex[k]; tu[edges]:=undet[k];
length[edges]:=l; next:=undet[k]
Until next = w { чи Досягли ми w }
End;
Procedure showway;
{ Вивід на екран дисплея найкоротшої відстані між вершинами V0 і W зваженого графа, визначеної процедурою dijkst }
Var i: Integer;
Begin writeln; writeln(‘Найкоротша відстань між’);
writeln(‘вузлами ‘,v0,’ і ‘,w,’ дорівнює ‘,length[edges])
End;
Begin { Основна програма }
adjinit; printmat; v0:=1;w:=5;
dijkst; showway; readln
End.
АЛГОРИМ ФЛОЙДА.Вирішує завдання пошуку найкоротшого шляху між двома вузлами графа.
Припустимо є граф, в якому з кожною дугою пов’язане додатне число (рис. 7.12). Для кожної пари вузлів знайти такий путь, щоб довжина його була мінімальною серед усіх можливих між цими вузлами.
Алгоритм Флойда використовує матрицю розміром n*n, в якій обчислюються всі самі короткі шляхи. Елементи діагоналі дорівнюють 0. Як що дуга відсутня, відповідний елемент матриці дорівнює ∞. Над матрицею виконується n ітерацій. Після k-ї ітерації матриця зберігає значення самих коротких шляхів між вузлами i та j, але такі, що не проходять через вузол k.
Рис. 7.12. Орієнтований граф
На рис. 7.13 показано значення матриці А після трьох ітерацій.
| 1 2 3 | 1 2 3 | 1 2 3 | 1 2 3 | ||||
| 0 8 5 3 0 ∞ ∞ 2 0 | 0 8 5 3 0 8 ∞ 2 0 | 0 8 5 3 0 8 5 2 0 | 0 7 5 3 0 8 5 2 0 |
A0[i,j] A1[i,j] A2[i,j] A3[i,j]
Рис. 7.13. Поступове значення матриці А
У програмному прикладі наведено реалізацію алгоритма Флойда.
{===== Програмний приклад 7.2 =======}
Procedure floyd (var A: tm; C:tm);
var i,j,k : integer;
Begin
for i:=1 to n do
for i:=1 to n do A[i,j]:=C[i,j];
for i:=1 to n do A[i,i]:=0;
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
if A[i,k]+A[k,j] < A[i,j]
then A[i,j]=A[i,k]+A[k,j] ;
end;
Час виконання алгоритму Флойда О(n2). Алгоритм Дейкстри з використанням матриці суміжності знаходить коротший шлях від однієї вершини до іншої за час порядку О(n2), для знаходження коротших шляхів для усіх n вершин знадобиться час О(n3). Тобто в цьому випадку час приблизно однаковий. Та, якщо кількість дуг в графі значно менше ніж n2, тоді має сенс використовувати алгоритм Дейкстри, для розріджених графів він працює скоріше.