Задачі про потоки в мережах. Алгоритм Дейкстри. Звіт з Інші. Робота № 110148

Задачі про потоки в мережах. Алгоритм Дейкстри

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2010

Тип роботи:

Звіт

Предмет:

Інші

Група:

ПІ

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 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.

Звіт Інші

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись