Теоретичні відомості

Лабораторна робота № 3

Тема:Знаходження найкоротшого шляху до однієї вершини в орграфі (алгоритм

Дейкстри).

Мета:Навчитися знаходити найкоротший шлях до однієї вершини в орграфі.

Теоретичні відомості

Орієнтований граф(орграф) G=(V,E) складається з множини вершин V і множини дуг Е. Вершини також називаються вузлами, а дуги — орієнтованими ребрами. Дуги представляються у вигляді упорядкованої пари вершин (υ, ω), де вершина υ називається початком, а ω ― кінцем шляху. Кажуть, що вершина ω суміжна з вершиною υ.

Помічений граф – це орграф, у якого кожна дуга або кожна вершина має відповідні мітки. Міткою може бути ім’я, вага або вартість (дуги), або значення даних будь-якого заданого типу.

Нехай задано орграф G=(V,E), у якого всі дуги мають додатні мітки (вартості дуг), а одна вершина визначена як джерело. Задача полягає в знаходженні вартості найкоротших шляхів від джерела до всіх інших вершин графу G (тут довжина шляху визначається як сума вартості дуг, що складають цей шлях). Ця задача часто називається задачею знаходження найкоротшого шляху з одним джерелом.

Припустимо, що в орграфі G вершини названі цілими числами, тобто множина вершин V={1, 2…, n}, причому вершина 1 є джерелом. Масив С – двохвимірний масив вартостей, де елемент С[i, j] рівний вартості дуги i→j.

Якщо дуги i→j не існує, тоді С[i, j] кладемо рівним ∞, тобто більшим за будь-яку фактичну вартість дуг. На кожному кроці D[i] містить довжину поточного найкоротшого особливого шляху до вершини і.

Для розв’язку поставленої задачі будемо використовувати “жадібний” алгоритм, який часто називається алгоритмом Дейкстри. Алгоритм будує множину S вершин, для яких найкоротші шляхи від джерела вже відомі. На кожному кроці до множини S додається та з решти вершин, відстань до якої від джерела менша, ніж для інших вершин, які залишилися. Якщо вартості всіх дуг додатні, то можна бути впевненими, що найкоротший шлях від джерела до конкретної вершини проходить тільки через вершини множини S. Назвемо такий шлях особливим. На кожному кроці алгоритму використовується також масив D, в який записуються довжини найкоротших особливих шляхів для кожної вершини. Коли множина S буде містити всі вершини орграфа, тобто для всіх вершин будуть знайдені “особливі” шляхи, тоді масив D міститиме довжини найкоротших шляхів від джерела до кожної вершини.

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒