Формулювання завдання. Надано орієнтований граф G = (X, A), кожній дузі (ребру) (u, w) цього графу відповідає невід'ємна вага C u w. Загальна задача знаходження найкоротших шляхів полягає в знаходженні для кожної впорядкованої пари вершин (u, w) будь-якого шляху від вершини u у вершину w, довжина якого є мінімальною серед всіх можливих шляхів від u до w.

Можна розв'язувати цю задачу, послідовно застосовуючи алгоритм Дейкстри для кожної вершини, що оголошується як джерело. Але для розв'язання поставленої задачі можна скористатися алгоритмом, запропонованим Флойдом.

Припустимо, що всі вершини орграфа послідовно пронумеровані від 1 до n. Алгоритм Флойда використовує матрицю A(n,n), в якій знаходяться довжини найкоротших шляхів:

Aij = Cij, якщо i ?j;

Aij = 0, якщо i = j;

Ai j = Ґ, якщо відсутній шлях з вершини i у вершину j.

Над матрицею A виконується n ітерацій. Після k-ої ітерації Aij містить значення найменшої довжини шляху з вершини i у вершину j, причому шлях не проходить через вершини з номерами великими k.

Обчислення на k -ій ітерації виконується за формулою:

Akij = min (A k-1ij, A k-1ik, A k-1kj) (5.5)

Верхній індекс k означає значення матриці A після k-ої ітерації.

Для обчислення Akij проводиться порівняння величини Ak-1ij (тобто вартість шляху від вершини i до вершини j без участі вершини k або іншої вершини з вищим номером) з величиною Ak-1ik + Ak-1kj (вартість шляху від вершини i до вершини k плюс вартість шляху від вершини k до вершини j). Якщо шлях через вершину k дешевше, ніж Ak-1ij, то величина Akij змінюється.

Розглянемо помічений орграф, наданий на рис. 2.6.

Рисунок 5.35 - Помічений орграф

Матриця A (3х3) на нульовій ітерації (k = 0):

Матриця A ( 3 х 3 ) після першої ітерації (k = 1):

Матриця A (3 х 3) після другої ітерації (k = 2):

Матриця A (3 х 3) після третьої ітерації (k = 3):

Кінець алгоритму.

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

Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів останнім часом інтенсивно розвивається. Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від знаходження оптимального маршруту між двома об'єктами на місцевості (наприклад, найкоротший шлях від будинку до університету), в системах автопілоту, для знаходження оптимального маршруту при перевезеннях, комутації інформаційного пакету в Internet і т.д.

Література

Основна

1. Новиков Ф.А. Дискретная математика для программистов. - С.-Пб.: Питер, 2001. - 304 с.

2. Бондаренко М.Ф. Комп'ютерна дискретна математика. - Харків: "Компанія СМІТ", 2004. - 480 с.

3. Нікольський Ю.В. Дискретна математика. - К.: Видавнича група BHV, 2007. - 368 с.

4. Новиков Ф.А. Дискретная математика для программистов. - С.-Пб.: Питер, 2006. - 364 с.

5. Донской В.И. Дискретная математика. - Симферополь: "СОНАТ", 2000. - 360 с.

6. Сигорский В.П. Математический аппарат инженера. Изд. 2-е, стереотип. "Texнiкa", 1977, 768 с.

7. Иванов Б.Н. Дискретная математика: Алгоритмы и программы: Учебное пособие. М.: Лаборатория базовых знаний, 2001. - 288 с.

Додаткова література

1. Акимов О.Е. Дискретная математика: логика, группы, графы. - М.: Лаборатория базових знаний, 2001. - 376 с.

Размещено на Allbest.ru