Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми пошуку найкоротших шляхів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
Не вказано
Кафедра:
Кафедра Телекомунікації
Інформація про роботу
Рік:
2017
Тип роботи:
Лабораторна робота
Предмет:
Телекомунікаційні та інформаційні мережі
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра “Телекомунікації”
Лабораторна робота №4 на тему:
“ Алгоритми пошуку найкоротших шляхів ”
з дисципліни "Телекомунікаційні та інформаційні мережі. Частина 1"
Мета роботи: Навчитись застосовувати алгоритми пошуку найкоротших шляхів та застосовувати їх в телекомунікаційних мережах
Хід роботи
1) Вигляд згенерованого графа
/
За алгоритмом Дейкстри
/
2) Змінемо вагу деяких шляхів на від'ємну
/
За алгоритмом Беллмана - Форда
/
3) Вказати який з алгоритмів виконується швидше:
а) В даному випадку швидкість знаходження найкоротшого шляху за кількістю кроків є однаковою для обох алгоритмів.
б) В алгоритмі Беллмана - Форда кількість відвіданих вершин на кожному кроці дорівнює одиниці, в той час як у алгоритмі Дейкстри деякі вершини відвідуються повторно.
4) Чи знайдені маршрути за алгоритмом Дейкстри та Беллмана-Форда однакові?
а) Знайдені маршрути за різними алгоритмами є різними, тому що у графі Беллмана - Форда присутні від'ємні ваги ребер.
б) Лише для ребра (1,2). Вага шляху дорівнює трьом.
5) Вважаючи, що коефіцієнти ребер вказують на пропускну здатність в Мбіт/с, знайти пропускну здатність кожного шляху визначеного за алгоритмом Дейкстри та Беллмана-Форда.
а) Які шляхи мають максимальну пропускну здатність, чому?
Для алгоритма Дейкстри – 1-6-5-2-3-4.
Для алгоритма Беллмана-Форда – 1-5-3-4.
б) Чи є шляхи які на якомусь відрізку мережі використовують менше половини пропускної здатності ребра?
Так.
в) Чи можливе одночасне існування потоків із вершини N до всіх інших із розрахованою пропускною здатністю кожного шляху? Чому?
Так, тому що є шляхи які між собою не накладаються.
Висновок
На даній лабораторній роботі було розглянуто два алгоритми для пошуку мінімального шляху, для зваженого графу, а саме алгоритм Дейкстри та Беллмана-Форда. Алгоритми за своєю структурою є досить схожі, за винятком того, що Беллмана-Форда враховує від'ємні ваги ребер. Такі алгоритми доцільно використовувати в побудові мереж зв'язку, умовно вагою графа можна позначати відстань чи пропускну здатність системи передачі, що дає можливість обрати найбільш ефективний шлях передачі даних до потрібної точки.
21.12.2017 23:56
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора