Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми пошуку найкоротших шляхів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
СІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
НВЧ
Група:
ТК-31
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
/
Лабораторна робота №4
«Алгоритми пошуку найкоротших шляхів»
Тема роботи: Алгоритми пошуку найкоротших шляхів.
Мета роботи: Навчитись застосовувати алгоритми пошуку найкоротших шляхів та застосовувати їх в телекомунікаційних мережах.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Google Вам допоможе (
ХІД РОБОТИ
1) За допомогою лабораторного макету побудувати випадковий неорієнтований зважений граф з V=6 та E=10 та побудувати дерево шляхів з вершини N за алгоритмом Дейкстри;
2) Для того ж графа побудувати дерево шляхів з вершини N за алгоритмом Беллмана-Форда;
3) Вказати який з алгоритмів виконується швидше:
а) порівняти за кількістю кроків для знаходження найкоротшого шляху;
б) порівняти за кількістю відвіданих вершин на кожному кроці;
4) Чи знайдені маршрути за алгоритмом Дейкстри та Беллмана-Форда однакові?
а) Якщо ні, вказати які та чому;
б) Чи існують маршрути з однаковою метрикою? Які?
5) Вважаючи, що коефіцієнти ребер вказують на пропускну здатність в Мбіт/с, знайти пропускну здатність кожного шляху визначеного за алгоритмом Дейкстри та Беллмана-Форда.
а) Які шляхи мають максимальну пропускну здатність, чому?
б) Чи є шляхи які на якомусь відрізку мережі використовують менше половини пропускної здатності ребра?
в) Чи можливе одночасне існування потоків із вершини N до всіх інших із розрахованою пропускною здатністю кожного шляху? Чому?
20.05.2019 17:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора