Презентация на тему Пошук найкоротшого шляху. Графи

щоб довжина телефонних ліній була мінімальною.
Те ж завдання:

дано зв'язний граф з N вершинами, веги ребер задані ваговою матрицею W. Потрібно знайти набір ребер, що з'єднує всі вершини графа (остовне дерево) і має найменшу вагу.

якому на кожному кроці приймається рішення, краще в даний

момент.

Крок в задачі Прима-Краскала – це вибір ще невибраного ребра і додавання його до рішення.

не вибрано, і 2) ребро не утворює циклу з

вибраними ребрами.
Рішення: присвоїти кожній вершині свій колір і перефарбовувати вершини при додаванні ребра.

3

2

4

5

Алгоритм:
пофарбувати всі вершини в різні кольори;
зробити N-1 раз в циклі:
вибрати ребро (i,j) мінімальної довжини з усіх ребер, що з'єднують вершини різного кольору;
перефарбувати всі вершини, що мають колір j, в колір i.
вивести знайдені ребра.

4

i, j: integer; { номери вершин }

end;

const N = 5;
var W: array[1..N,1..N] of integer;
Color: array[1..N] of integer;
i, j, k, min, col_i, col_j: integer;
Reb: array[1..N-1] of rebro;
begin
... { тут треба ввести матрицю W }
for i:=1 to N do { розфарбувати в різні кольори }
Color[i] := i;
... { основний алгоритм – заповнення масиву Reb }
... { вивести знайдені ребра (масив Reb)}
end.

Основна програма:

вагова матриця

колір вершин

min := MaxInt;
for i:=1 to N do

for j:=i+1 to N do
if (Color[i] <> Color[j]) and
(W[i,j] < min) then begin
min := W[i,j];
Reb[k].i := i;
Reb[k].j := j;
col_i := Color[i];
col_j := Color[j];
end;
for i:=1 to N do
if Color[i] = col_j then
Color[i] := col_i;
end;

Основний алгоритм:

потрібно вибрати всього N-1 ребро

цикл по всіх парах вершин

враховуємо тільки пари з різним кольором вершин

запам'ятовуємо ребра і кольори вершин

перефарбовуєм вершини кольору col_j

...
for i:=1 to N do
for

j:=i+1 to N do
...
end;

три вкладених цикли, в кожному кількість кроків <=N

зростає не швидше, ніж N3

Необхідна пам'ять:

var W: array[1..N,1..N] of integer;
Color: array[1..N] of integer;
Reb: array[1..N-1] of rebro;

O(N2)

Кількість операцій:

містами, частина яких можуть мати односторонній рух. Знайти найкоротші

відстані від заданого міста до всіх інших міст.

Та же завдання: дано зв'язний граф з N вершинами, ваги ребер задані матрицею W. Знайти найкоротші відстані від заданої вершини до всіх інших.

присвоїти всім вершинам мітку ∞;
серед нерозглянутих вершин знайти вершину j з найменшою міткою;
для кожної необробленої вершини i: якщо шлях до вершини i через вершину j менше існуючої мітки, замінити мітку на нову відстань;
якщо залишилися необроблені вершини, перейти до кроку 2;
мітка = мінімальна відстань.

Алгоритм Дейкстри (E.W. Dijkstra, 1959)

вершина вже розглянута, і a[i]=0, якщо ні.
масив b, такий

що b[i] – довжина поточного найкоротшого шляху з заданої вершини x в вершину i;
масив c, такий що c[i] – номер вершини, з якої потрібно йти в вершину i в поточному найкоротшому шляху.
Ініціалізація:
заповнити масив a нулями (вершини не оброблені);
записати в b[i] значення W[x][i];
заповнити масив c значеннями x;
записати a[x]=1.

стоп.
серед всіх нерозглянутих вершин (a[i]=0) знайти вершину j, для

якої b[i] – мінімальне;
записати a[j]:=1;
для всіх вершин k: якщо шлях в вершину k через вершину j коротший, ніж знайдений раніше найкоротший шлях, запам'ятати його: записати b[k]:=b[j]+W[j,k] і c[k]=j.

Крок 1:

вершини 0 в вершину 4:
4


5
2
0



Складність алгоритму Дейкстри:
O(N2)
два вкладених цикли

по N кроків

Виведення маршруту в вершину i (використання масиву c):
встановити z:=i;
поки c[i]<>x присвоїти z:=c[z] і вивести z.

яких може мати односторонній рух. Знайти всі найкоротші відстані,

від кожного міста до всіх інших міст.

for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then
W[i,j] := W[i,k] + W[k,j];

Якщо з вершини i в вершину j коротше їхати через вершину k, ми їдемо через вершину k!

N
for j := 1 to N
c[i,j]

:= i;
...
for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then begin
W[i,j] := W[i,k] + W[k,j];
c[i,j] := c[k,j];
end;

i–ий рядок будується так само, як масив c в алгоритмі Дейкстри

в кінці циклу c[i,j] – передостання вершина в найкоротшому маршруті
з вершини i в вершину j

c[i,j] := c[k,j];

O(N3)

з першого міста і, відвідавши по разу в невідомому

порядку міста 2,3,...N, повернуться назад в перше місто. У якому порядку треба обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротший?

Точні методи:
простий перебір;
метод гілок і меж;
метод Літтла;
…
Наближені методи:
метод випадкових перестановок (Matlab);
генетичні алгоритми;
метод мурашиних колоній;
…

великий час рахунку для великих N

O(N!)

не гарантується оптимальне рішення