я найменшої довжина шляху з вершини i у вершину j, причому шлях не проходити через вершини з номерами великими k.
Обчислення на k -ій ітерації віконується за формулою:
=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. Бондаренко М.Ф. Комп ютерна дискретна математика.- Харків: Компанія СМІТ raquo ;, 2004. - 480 с.
. Нікольській Ю.В. Дискретна математика.- К .: Видавнича група BHV, 2007. - 368 с.
. Новиков Ф.А. Дискретна математика для програмістів.- С.-Пб .: Пітер, 2006. - 364 с.
. Донський В.І. Дискретна математика.- Сімферополь: СОНАТ raquo ;, 2000. - 360 с.
. Сигорський В.П. Математичний апарат інженера. Изд. 2-е, стереотип. Texнiкa raquo ;, 1977, 768 с.
. Іванов Б.Н. Дискретна математика: Алгоритми і програми: Навчальний посібник. М .: Лабораторія базових знань, 2001. - 288 с.
Додаткова література
1. Акімов О.Е. Дискретна математика: логіка, групи, графи.- М .: Лабораторія базових знань, 2001. - 376 с.
