![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Постановка задачі
Розглянемо телекомунікаційну мережу у вигляді графу G = (N, A), де N = {1, 2, …, n} – множина вузлів, A – множина дуг. Вважаємо, що ця мережа має одне інформаційне джерело – вузол s та один стік – вузол t. Цілочисельна функція fij, визначена на множині A, називається потоком в мережі G = (N, A), якщо:
Згідно цього визначення, якщо вузол j не виступає ні стоком, на джерелом, то величина потоку, що втікає в нього, повинна дорівнювати величині потоку, що витікає з нього, тобто виконуватися правило збереження потоку (1.2). Однією з найбільш важливих потокових задач є задача знаходження шляху з джерела до стоку такого, що вартість (час) проходження потоку заданої величини по цьому шляху буде мінімальна. Припустимо, що кожній дузі (i, j) заданої мережі відповідає деяке число Задача, що вирішується в даній роботі, полягає в знаходженні такого шляху з джерела s до стоку t, для якого вартість проходження одиниці потоку буде мінімальна. Математично ця задача може бути записана так: мінімізувати за умови, що
Згідно з обмеженням (1.4), одиниця потоку витікає з джерела. Рівняння (1.5) гарантує збереження даної одиниці потоку при проходженні в мережі. Згідно з рівнянням (1.6), одиниця потоку потрапляє до стоку. В якості найкоротшого шляху може бути взята послідовність суміжних дуг Алгоритм базується на приписуванні вузлам тимчасових, або постійних позначок. Спочатку кожному вузлу, окрім джерела, приписується тимчасова позначка, яка дорівнює довжині найкоротшої дуги, що веде з джерела в даний вузол. Джерелу приписується постійна позначка, значення якої дорівнює нулю. Кожному вузлу, у який не можна потрапити безпосередньо з джерела, приписується тимчасова позначка
|