Алгоритми пошуку найкоротших шляхів. Лабораторна робота з НВЧ. Робота № 530871

Алгоритми пошуку найкоротших шляхів

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

ВУЗ:

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

Інститут:

Факультет:

СІ

Кафедра:

Не вказано

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

Рік:

2019

Тип роботи:

Лабораторна робота

Предмет:

НВЧ

Група:

ТК-31

Завантажити

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

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

Лабораторна робота НВЧ

Zenuk1998

20.05.2019 17:43

Коментарі

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

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

поділитись