Page 82 - 4496

 знайти мінімальний шлях між заданими вершинами;
 знайти максимальний шлях;
 знайти цикл Ейлера.

Найкоротші шляхи
Розглянемо завдання пошуку мінімального шляху між
двома заданими вершинами a п і a к у графі за умови, що
кожній дузі (i,j) зіставлена вага c i, j-ненегативне число й
оцінка аддитивна. Якщо ваги позначають довжину дуги, то
задача формулюється як завдання знаходження найкоротшого
шляху між заданими вершинами.
Розглянемо класичний алгоритм розв'язку цієї задачі -
алгоритм Дейкстри, в основі якого лежить наступна теза
Дейкстри: якщо найкоротший шлях проходить через вершину
a i, то довжина частини шляху від a п до a i повинна бути
мінімально можливою.
Алгоритм представимо наступною послідовністю
кроків.
1. Початкові присвоювання. Кожній вершині, крім
початкової, зіставимо вагу l(a i), яка дорівнює нескінченності,
назвемо цю вагу тимчасовою. Початковій вершині зіставимо
вагу, що дорівнює нулю: l(a п)=0, назвемо цю вагу постійною,
вершину a п назвемо поточною й позначимо як p.
2. Оновлення ваг. Усім вершинам, що пов'язані з
поточною по вихідних дугах, і що мають тимчасові ваги,
змінимо ваги за правилом l(а i)=min(l(а i), l(p)+с p,j)
3. Зміна поточної вершини. Серед вершин з
тимчасовою оцінкою знайдемо вершину з мінімальною вагою
й назвемо її поточною, а її вага - постійна. Якщо це є вершина
a п, то перейдемо до пункту 4, інакше - до пункту 2.
4. Виділення шляху зворотним ходом. Визначимо
кінцеву вершину як поточну; для кожної вершини, пов'язаною
з нею по дугах, що заходять, визначимо різницю між вагою
поточної вершини й вагою дуги. Вершину, вага якої збігається
із цією різницею, назвемо поточною, а дугу віднесемо до
шляху. Те, що така вершина завжди знайдеться, гарантується
способом побудови ваг вершин. Можливо, що таких вершин
буде декілька, що говорить про існування декількох розв'язків
завдання. Виберемо в цьому випадку кожну з них. Повторимо
цю процедуру доти, поки поточною не стане початкова
79