![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Ітераційна процедура
Для даного вузла
Для визначення найближчого до джерела вузла оберемо тимчасову позначку з мінімальним значенням та оголосимо її постійною позначкою: [ Після цього до тих пір, доки стоку не буде приписана постійна позначка, необхідно виконати наступні дві процедури: 1. Розглянути вузли, що залишилися з тимчасовою позначкою. Порівняти величину кожної тимчасової позначки із сумою величини останньої з постійних позначок і довжини дуги, що веде з відповідного постійно позначеного вузла у вузол, що розглядається. Мінімальна з цих двох величин визначається як нова тимчасова позначка вузла. 2. Серед тимчасових позначок обрати ту, значення якої мінімальне, і оголосити її постійною позначкою. Якщо при цьому постійна позначка приписується вузлу Цю процедуру можна оформити у вигляді таблиці розв’язання, в якій стовпці відповідають вузлам мережі, рядки - крокам ітеративного процесу, а її елементи - постійним та тимчасовим позначкам (див. Приклад 1). Приклад 1. Знайти найкоротші шляхи з першого вузла до решти вузлів в мережі, граф якої приведено на рис. 1.1. Будемо вважати, що джерелом в мережі є вузол 1, а стоком – вузол 5.
Процедуру вирішення задачі зведено в таблицю 1.1. Таблиця 1.1
|