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