МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 4 На тему: “Задачі про потоки в мережах. Алгоритм Дейкстри” З дисципліни: “Дослідження операцій” Лектор: доц. каф. ПЗ Журавчак Л.М. Львів – 2010 Тема роботи: Задачі про потоки в мережах. Визначення найкоротшого шляху в графі. Алгоритм Дейкстри. Мета роботи: Ознайомитись із задачами про потоки в мережах. Навчитись визначати найкоротший шлях в графі за допомогою алгоритму Дейкстри. Теоретичні відомості Мережа складається з множини вузлів, зв'язаних дугами (або ребрами). Таким чином, мережа описується парою множин (N,A) де N— множина вузлів, а А— множина ребер. Наприклад, мережа, показана на рисунку 1 описується таким чином.
Рис. 1. Приклад мережі. З кожним типом мережі пов'язаний певний тип потоків (наприклад, транспортний потік нафти в нафтопроводах або автомобільні потоки в мережі міських доріг). В загальному випадку потоки в мережі обмежені пропускною спроможністю її ребер, яка може бути як скінченною, так і нескінченною. Ребро називається направленим, або орієнтованим (і в цьому випадку ребро називається дугою), якщо в одному напрямі можливий тільки додатній потік, а в протилежному — тільки нульовий. В орієнтованій мережі всі ребра орієнтовані. Шляхом називається послідовність різних ребер, що сполучають два вузли, незалежно від напряму потоку в кожному ребрі. Шлях формує цикл, якщо початковий і кінцевий вузли співпадають. Наприклад, на рис. 1 дуги (2,3), (3,4) і (4, 2) складають цикл. Орієнтований цикл — це цикл, в якому всі дуги орієнтовані в певному напрямі. Зв'язна мережа — така мережа, у якої будь-які два вузли зв'язано принаймні одним шляхом. На рис. 1 показаний саме такий тип мережі. Деревом називається зв'язна мережа, що містить підмножину вузлів початкової мережі і не має циклів. Алгоритм Дейкстри для визначення найкоротшого шляху Алгоритм Дейкстри розроблений для пошуку найкоротшого шляху між заданим початковим вузлом і будь-яким іншим вузлом мережі. В процесі виконання цього алгоритму при переході від вузла i до наступного вузла використовується спеціальна процедура відмітки ребер. Позначимо через ut найкоротшу відстань від початкового вузла 1 до вузла i, через dtj — довжину ребра (i, j). Тоді для вузла j визначимо мітку [ui,i] таким чином.
Мітки вузлів в алгоритмі Дейкстри можуть бути двох типів: тимчасові і постійні. Тимчасова мітка згодом може бути замінена на іншу тимчасову, якщо буде знайдений більш короткий шлях до даного вузла. Коли ж стане очевидним, що не існує більш короткого шляху від початкового вузла до даного, статус тимчасової мітки змінюється на постійний. Завдання 2. Знайти найкоротші шляхи між вузлом 1 і рештою вузлів мережі, представленої на малюнку.
Код та результати роботи








Висновок На цій лабораторній роботі я ознайомився із задачами про потоки в мережах; навчився визначати найкоротший шлях в графі за допомогою алгоритму Дейкстри. Алгоритм Дейкстри було реалізовано у програмному засобі MathCad.