Page 50 - 4387

ЛАБОРАТОРНА РОБОТА № 7

Реалізація алгоритму подвійного пошуку k перших

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

7.1 Мета і завдання роботи роботи

Мета роботи – засвоїти принцип пошуку k перших

найкоротших шляхів з деякої фіксованої вершини до усіх інших
вершин графа.

Завдання роботи – знайти за допомогою алгоритму
подвійного пошуку k перших найкоротших шляхів між заданою

вершиною та усіма іншими вершинами графа.
Тривалість лабораторної роботи – 12 год. (6 пари).

7.2 Основні теоретичні положення

Алгоритм подвійного пошуку дозволяє знаходити k перших

найкоротших шляхів з деякої фіксованої вершини до усіх інших

вершин вхідного графа.

В алгоритмі подвійного пошуку використовуються дві

спеціальні алгебраїчні операції. Вони називаються узагальненими

операціями, оскільки виконуються не над числами, а над

векторами. Перейдемо до розгляду даних операцій. Перша з них

називається узагальненою операцією мінімізації, друга –

узагальненою операцією додавання. Дані операції є двомісними,

тобто вони можуть виконуватися тільки над двома векторами.

Нехай А=(а , а , ..., а ) та B=(b , b , ..., b ) – два вектори із
k
1
2
1
k
2
k
множини R (множини векторів (d , d , ..., d ), що задовольняють
2
k
1
умову d <d <...<d ). Узагальнена операція мінімізації (порівняння)
k
2
1
49