Page 23 - 4387

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

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

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

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

шляху між двома заданими вершинами графа за допомогою

алгоритму Дейкстри.
Завдання роботи – знайти за допомогою алгоритму

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

Тривалість лабораторної роботи – 4 год. (2 пари).

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

Алгоритм Дейкстри дозволяє знаходити в графі

найкоротший шлях між двома виділеними вершинами v і w при

позитивних довжинах дуг. Він вважається одним з найбільш

ефективних алгоритмів розв'язку задачі.

Принцип дії алгоритму Дейкстри такий.

Крок 1. Перед початком виконання алгоритму всі вершини

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

присвоюється число d(x), рівне довжині найкоротшого шляху з v

у х, що включає тільки позначені вершини.

Присвоїти d(v)=0 та d(x)=∞ для всіх х, відмінних від v.

Позначити вершину v та присвоїти у=v (у – остання з позначених

вершин).

Крок 2. Для кожної непозначеної вершини х наступним

чином перерахувати величину d(x):

d (x ) = min{d (x );d ( ) y + c (y , x )}. (3.1)

22