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