Дипломная работа: Математична модель транспортної системи підприємства

У ряді відомих алгоритмів робиться додаткове припущення про те, що G (V, Е) не містить циклів негативної довжини.

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

Проте у розрахунковому відношенні більш ефективними виявилися спеціальні, так називані комбінаторні алгоритми, аналізовані в даному розділі. У цих алгоритмах вихідні дані подані у виді списків дуг, тобто для кожної вершини дається список тих дуг (i, j), що інцидентні їй, разом із їхніми довжинами . Оцінки числа операцій алгоритмів приведені в табл. 3.Спочатку роздивимося основні алгоритми рішення задачі пошуку найкоротшого шляху між двома вершинами: 1 (джерело) і п (стік).

Таблиця 3 - Оцінки числа операцій алгоритмів

Автор алгоритму	Оцінка числа операцій	Автор алгоритму		Оцінка числа операцій
Найкоротший шлях між двома вершинами		Найкоротші шляхи між усіма парами вершин
Беллман [14] Дийкстра [15] Беллман-Форд [16]	0(n2) 0(m log n) 0(m n)	Дийкстра [17] Спира [18] Флойд-Варшал [19,20] Фридман [21]	0(mn log n) 0(n2(log n)2) 0(n2) 0(n)2,5

Метод Белмана. Скористаємося рівнянням Белмана для визначення найкоротшого шляху між вершинами 1 і n. Визначимо - довжину найкоротшого шляху з вихідної вершини 1 у вершину j за умови, що вершини пронумеровані числами 1, 2, 3,..., п. Шлях найкоротшої довжини знаходиться з такого рівняння:

j=2,3,…,n;u_j =0

У результаті розрахунків знаходиться (якщо воно існує) дерево найкоротших відстаней із коренем у вершині 1, у якому довжина єдиного шляху з 1 у j дорівнює uj, j=2, 3,..., п.

Алгоритми Дийкстра. Роздивимося мережу G (V, Е), у котрої довжини lijусіх дуг позитивні. Тоді відомий алгоритм Дийкстра може бути записаний у такий спосіб.

Крок 0. Покласти

якщо (i ,j ) у іншому випадку,

S={1,2,3…,n}

Крок 1. Знайти, для котрого = , якщо uk =+ - стіп; не існує шляху у вершини, що залишилася в S. Положимо S = S - {k}. Якщо S = - стіп; обчислення закінчені.

Крок 2. Покласти = min{} для всіх (k, j) Е. Перейти до кроку 1.