Задача визначення найкоротших шляхів у зваженому графі

Лекція 11

Алгоритми на графах

Основні поняття теорії графів

Способи зображення графа в оперативній пам'яті

Задача визначення найкоротших шляхів у зваженому графі

Алгоритм пошуку вглибину

Алгоритм пошуку вшир

11.1. Поняття графа та його зображення в пам'яті комп'ютера

Граф — це сукупність непорожньої множини V вершин і множини Е невпорядкованих або впорядкованих пар вершин: G = (V, Е), V ≠ Æ, Е ÌV´V. Невпорядкована пара вершин називається ребром, впорядкована пара вершин — дугою. При цьому першу вершину з пари прийнято називати початком дуги, а другу - її кінцем. Граф, що не містить дуг, називається неорієнтованим, а граф, що містить дуги — орієнтованим або орграфом. Ребро (дуга) і будь-яка його (її) вершина називаються інцидентними. З'єднані ребром вершини називаються суміжними. Якщо вершина v є початком певної дуги, а вершина w — її кінцем, то вершину w вважають суміжною з вершиною v, але не навпаки.

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

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

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

1, вершина j суміжна з вершиною i

Adj[i,j]=

0, вершина j не суміжна з вершиною i

Матриця інциденцій Іпс неорієнтованого графу є матрицею розмірності п´т, в якій

1, вершина u_i інцидент ребру e_j

Inc[i,j]=

0, вершина u_i не інцидентна ребру e_j

Матриця інциденцій Іпс орграфу є матрицею розмірності п´т, в якій

1, вершина u_i інцидент дузі e_j і є її кінцем

Inc[i,j]=

0, вершина u_i і дуга e_j не інцидентні

-1, вершина u_i інцидент дузі e_j і є її початком

Приклад 11.1

На рис. 11.1 зображено орієнтований граф D та неорієнтований граф G Нижче наведено матриці їх суміжності та інциденцій.

 

e₂ e₂

 

e₅ e₅

e₁ e₃ e₁ e₃

 

 

 

e₄ e₄

 

D G

 

Рис. 11.1. Орієнтований D та неорієнтований G графи

Матриці суміжності цих графів такі:

 

Adj_G=							Adj_D=

Матриці інциденцій графів D і G є такими:

 

									-1
										-1			-1
Inc_G=								Inc_D=
											-1	-1

Граф, в якому кожному ребру (i, j) відповідає число ω_ij називається зваженим, а число ω_ij називається вагою ребра (i, j).

11.2. Найкоротші шляхи у графі

Для будь-яких двох вершин u_i та u_j графу G може існувати декілька шляхів, що з'єднують їх.

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

Приклад 11.2

Реалізуємо алгоритм Дейкстри для знаходження найкоротшого шляху у графі, матриця суміжності якого записана у текстовому файлі graf.dat. Перше число файлу визначає кількість вершин.

Program ex11_1; {пошук найкоротших шляхів за алгоритмом Дейкстри}

const

MaxSize = 150; {найбільша кількість вершин графу}

infinity = 10000; {позначення нескінченності }

type

VertexSet = set of 1..MaxSize;

var

weigth:array [1..MaxSize, 1..MaxSize] of Integer;

T: VertexSet; {множина вершин, до яких визначено

найкоротші шляхи }

Path, {масив довжин найкоротших шляхів до

кожної вершини графу }

vertex:array [1..MaxSize] of Integer;

{масив вершин найкоротшого шляху }

n: Integer; {кількість вершин графу }

start, finish:integer; {початкова та кінцева вершини шляху }

f:text; {файл вхідних даних, містить кількість вершин графу та матрицю суміжності}

{========== формування матриці суміжності ===========}

procedure ReadData;

var i.j: Integer; {параметри циклів}

begin

assign(f, 'graf.dat');

reset(f);

readln(f,n);

for і:=1 to n do

for j:=l to n do

Read(f.weigth[i,j]);

close(f);

end;

{=============== алгоритм Дейкстри ====================}

procedure FindMinPath;

var

Min, {довжина найкоротшого шляху}

i.j: Integer; {параметри циклів }

begin

{=== підготовка до пошуку найкоротшого шляху ===}

for і:=1 to n do

Path[i]:=infinity;{найкоротший шлях не визначено}

j:=start; {перша вершина найкоротшого шляху}

T:=[j]; {множина Т містить вершину start }

Path[j]:=0; {шлях зі start у start має довжину 0}

{====== пошук найкоротшого шляху ========}

while not(finish in Т) do

begin

for і:=1 to n do {перевіряти всі вершини}

begin

{якщо поточна вершина не належить множині Т.

знайти найменшу суму довжин шляхів до неї}

if not(i in Т) and

(Path[i]>Path[j]+weigth[ j, i ])

then

begin

Path[i]:=Path[j]+weigth[j,і];

Vertex[i]:=j;

end;

end;

{-------- пошук нового елемента множини Т ---------------------}

Min:=infinity;

j:= 0;

for і:=1 to n do

if not (i in T) and (Min>Path[i])

then

begin

Min:=Path[i]; {вважати шлях до поточної }

j:=i;

end;

if Min>=infinity then

begin

Writeln (‘There is no way from vertex ', start,'to vertex ', finish);

readln; halt(0); {перервати програму }

end

else T:=T+[j]; {включити вершину до множини Т}

end; {кінець циклу while }

end; {кінець процедури }

{=========== виведення найкоротшого шляху ============}

procedure WriteMinPath;

var і; Integer;

begin

writeln('Path:');

i:=finish; {задати номер кінцевої вершини }

while і<> start do {поки не досягнуто номера }

begin {початкової вершини }

write(I, '<-'); {виводити номери вершин шляху }

i:=Vertex[i]; {перейти до попередньої вершини }

end;

writeln(start); {вивести номер першої вершини }

writeln('Length=', Path[finish]);{вивести довжину шляху}

end;

{=============== основний блок програми ===============}

begin

ReadData; {ввести дані з файла }

repeat {ввести номер початкової вершини}

writeln('Enter start vertex <=',n);

readln(start);

until start<=n;

repeat

writeln('Enter finish vertex <=’, n);

readln(finish);

until finish<=n;

FindMinPath;

WriteMinPath;

readln;

end.

11.3. Обхід графу

Численна кількість алгоритмів на графах ґрунтується на переборі всіх або частини їх вершин. Такий перебір називається обходом графу. Найвідоміші алгоритми обходу графу — це пошук вглибину та вшир.

11.3.1. Пошук вглибину

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

Приклад 11.3

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

Для зображення графу використаємо список суміжності. Тип вершини назвемо TVer. Запис типу TVer міститиме такі поля: поточний номер вершини, кількість суміжних із нею вершин, масив покажчиків на суміжні вершини, ознаку відвідування вершин. Сам граф задамо масивом a, елементи якого будуть покажчиками на записи TVer.

Ініціалізація масиву вершин даними, що зчитані з вхідного файла, виконується у процедурі Init, з якої викликається процедура зв'язування суміжних вершин LinkVertex.

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

program ex11_2; {пошук вглибину }

uses crt;

type

PtrVer - ^ÙTVer; {тип покажчика на вершину графу }

TVer = record {тип вершини графу }

vertex:аггау[1..50] of PtrVer; {масив суміжних вершин}

k, {кількість суміжних вершин }

number:integer; {номер вершини }

mark: boolean; {ознака відвідування вершини }

end;

var a:array[l..50] of PtrVer; {масив покажчиків на вершини графу }

n: integer; {кількість вершин графу }

t:text; {текстовий файл зі списком суміжності }

key:char; {символ обраної користувачем дії }

start, {номер початкової вершини обходу графу }

finish:integer; {номер кінцевої вершини}

{======== встановлення зв'язків між вершинами графу =====}

procedure LinkVertex(var v, u:PtrVer);

begin

inc(v^Ù. k); v^Ù.vertex [v^Ù. k]:=u;

inc(u^Ù, k); u^Ù.vertex [u^Ù. k]:=u;

{======ініціалізація графу з файла========}

procedure Init;

var i,

iv, iu:integer; Ver:PtrVer;

begin

reset(t);

readln(t, n);

for i:=1 to n do

begin

new(Ver);

Ver^Ù.number:=i;

Ver^Ù.k:=0;

a[i]:=Ver;

end;

while not eof(t) do

begin

readln(t, iv, iu);

LinkVertex(a[iv], a[iu]);

end;

close (t);

end;

{============== пошук вглибину =================}

procedure DepthFirstSearch;

var

w:array [1..50] of integer; {масив номерів вершин маршруту}

i, j:integer; {лічильники циклів}

{================ алгоритм пошуку вглибину ==========

procedure Search(V:Ptrver); {V - покажчик на початкову вершину}

begin

if V^Ù.number = finish then

begin

write (‘Path: » ');

for i:=1 to j do

write (‘w[i], ' -> ');

writeln;

exit;

end

else {якщо кінцевої вершини не досягнуто,}

for і:=1 to v^{^}.k do {перегляд усіх суміжних вершин} begin

if not v^{^}.vertex[i]^{^}.mark then

begin

v^{^}.vertex[i] ^{^}.mark:=true; {помітити вершину }

j:=j+1; {збільшити лічильник помічених вершин}

w[j]:=v^{^}.vertex[і] ^{^}.number; {запам'ятати номер вершини}

Search(v^{^}.vertex[i]); {перейти до наступних вершин}

v^{^}.vertex[i] ^{^}.mark:=false; {зняти помітку з пройденої вершини}

end;

end;

end;

{основний блок процедури пошуку вглибину}

begin

clrscr;

writeln('«« depth first search »»');

write('initial vertex : '); readln(start);

write('terminal vertex : '); readln(finish);

for i:=l to n do {усі вершини вважати непоміченими}

а[і]^{^}.mark-.-false;

a[start] ^{^}.mark:=true; {помітити початкову вершину}

j:=1; {задати номер початкової вершини у маршруті}

w[j]:=start;

Search(a[start]); {виклик рекурсивної процедури пошуку} readln;

end:

{========= основний блок програми -==========}

begin

assign(t,'graph.lin');

Init; {створити граф }

repeat

clrscr;

writeln ('Number of vertexes = ', n);

writeln ('press <Enter> to solve'); writeln('<Esc> - to exit');

key:=readkey;

case key of

#13 : DepthFirstSearch;

#27 : halt;

end;

until false;

end.

11.3.2. Пошук ушир

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

Отже, спочатку переглядається стартова вершина, потім - суміжні з нею вершини, що входять до списку перегляду. Кожна ітерація алгоритму полягає у послідовному виборі всіх вершин зі списку перегляду і додаванні до цього списку вершин, що є суміжними з вибраними. При цьому вершини не можуть переглядатися двічі, а тому під час перегляду вершину слід помічати. Помічені вершини надалі не розглядаються.

Список перегляду найзручніше зображувати у вигляді черги. При перегляді вершини всі суміжні з нею непомічені вершини додаються до черги, а сама вершина з черги вилучається. Пошук виконується доти, доки не буде знайдено кінцевої вершини або доки список перегляду не стане порожнім.

Приклад 11.4

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

Процедури Init і LinkVeriex у тексті програми не наводимо, оскільки вони цілковито збігаються з відповідними процедурами програми ех11_3. Пошук ушир вершини finish, що розпочинається з вершини start, виконує процедура BreadthFirstSearch («пошук ушир»). Усі вершини, що є суміжними з поточною і не були помічені, додаються до черги за допомогою процедури AddList. Черга переглядається, починаючи від вершини PCur, тому виконання оператора PCur: =PCur^{^}.Next є дією, логічно еквівалентною видаленню вершини з черги. У разі знаходження кінцевої вершини або вичерпування всіх можливостей пошуку, чергу слід очистити за допомогою процедури Clear. Нарешті, рекурсивна процедура Output здійснює виведення знайденого шляху. Для посилання на попередню вершину шляху вико­ристовується покажчик Prev.

program exll_3; {пошук ушир }

uses crt;

type

PtrVer = ^{^}TVer; {тип покажчика на вершину графу }

TVer = record {тип вершини графу }

vertex:array [l.,50]of PtrVer;{масив суміжних вершин}

к, number:integer; {кількість вершин та номер вершини }

mark: boolean; {ознака відвідування вершини }

end;

PElem = ^{^}TElem; {тип покажчика на елемент черги }

TElem = record {тип елемента черги }

PVer: PtrVer; {покажчик на поточну вершину }

PFrom : PElem; {покажчик на попередню вершину }

Prev, _t {покажчик на попередній елемент черги }

Next:PElem; {покажчик на наступний елемент черги } end;

var PBeg, PEnd, {покажчики на початок і кінець черги }

PCur:PElem; {покажчик на поточний елемент черги }

t:text; {текстовий файл зі списком суміжності }

key:char; {символ вибраної користувачем дії }

start, {номер початкової вершини обходу графу}

finish:integer: {номер кінцевої вершини обходу } а:аггау[1..50] of PtrVer; {масив покажчиків на

вершини графу }

n: integer; {кількість вершин графу }

{====== додавання елемента до черги ========}

procedure AddList(v:PtrVer; q:РЕЇ em);

var р: PElem: {поточний покажчик }

begin

new(p): {виділити пам'ять для елемента черги}

p^{^}.PVer:=v; {покажчик на поточну вершину }

р^.PFrom:=q; {покажчик на попередню суміжну вершину }

р^.Prev.=PEnd^{^}.Prev;

р^.Next:=Pend;

PEnd^{^}.Prev^{^}.Next:=p;

Pend^.Prev.=p;

end;

{============ видалення елемента з черги ============}

procedure DelList(е:рЕІem);

var р: PElem;

begin

if е = nil then exit; {якщо елемент порожній,вийти з програми }

e^.Next^.Prev:=e^{^}.Prev;; {переадресувати покажчики } е^{^}.Prev^.Next:=е^.Next;

dispose(e); {звільнити пам'ять з-під елемента}

end;

{========== виведення поточного елемента черги ========}

procedure Output(e:pElem);

begin

if е = nil then exit; {якщо елемент порожній, вийти з програми }

output(e^.PFrom); {вивести решту черги }

if e^.PVer^.number <> finish then {елемент не }

write(e^.PVer^.number,’ ->’) {останній }

else write(e^.PVer^.number,’ ‘); {елемент останній}

end;

1================ видалення черги ====================}

procedure Clear;

var PCurrent, PDel:PElem;

begin

PCurrent:=PBeg^.Next;

while PCurrent <> Pend do {поки не досягнуто }

begin {кінця черги }

PDel:=PCurrent; {покажчик на елемент, що видаляється}

PCurrent:=PCurrent^.Next;{переадресувати покажчикна наступний елемент}

DelList(PDel); {видалити елемент }

end;

end;

{========*=============== пошук ушир ======================}

procedure BreadthFirstSearch;

var i:integer; {параметр циклу}

begin

Clrscr;

writeln('«« breadth first search »»');

write (initial vertex : '); readln(start);

write ('terminal vertex ; '); readln(finish);

AddList(a[start], nil); {додати в чергу вершину }

for і:=1 to n do {задати ознаки відвідування }

a[i] ^.mark:=false; {вершин графу }

PCur:=PBeg^.Next; {вибрати початок черги }

while PCur <> PEnd do {поки не досягнуто кінця черги}

begin

PCur^.PVer^.mark:=true; {відмітити вершину графу }

If PCur^.Pver^.number = finish then

begin {якщо вершина остання в черзі, то}

write (‘ Path : » ');

output(pCur); {вивести чергу}

clear; {очистити чергу}

readln;

exit; {вийти з циклу}

end;

{якщо вершина графу не остання}

for і:=1 to PCur^.PVer^.k do

begin {якщо вершина не відмічена}

If not PCur^.PVer^.vertex[i] ^.mark then

AddList (PCur^.PVer^.vertex[i], PCur);

end;

PCur:=PCur^.Next; {перейти до наступної вершини}

end;

write1n (‘ Path not found ‘);

readln;

clear: {очистити чергу}

end;

{============ основний блок програми ================}

begin

assign(t,’graph.lin’);

new(PBeg); new(PEnd);

PBeg^.Prev:=ni1; ' PBeg^.Next:=PEnd;

PEnd^.Prev:=PBeg; PEnd^.Next:=ni1;

init;

Repeat

clrscr;

writeln (‘Number of vertexes = ‘, n);

writeln (‘press <Enter> to solution’);

writeln (‘<Esc> - to exit’);

key:=readkey;

case key of

#13 : BreadthFirstSearch;

#27 : halt;

end;

until false;

end.