pan> алгоритм флойд Беллман псевдокод
Аналіз алгоритму Беллмана-Форда.
Час виконання програми, має порядок O ( nm ), де n - це кількість вершин, а m - це кількість дуг.
Найкращим випадком для алгоритму стане граф в якому 2 вершини і відсутні дуги, тобто вводиться матриця відстаней складається з нулів. p align="center"> 4. Програма реалізації алгоритмів
Нижче проілюстрована робота алгоритму Флойда, а сам код написаний в Додатку А. Заповнення матриці відстаней здійснюємо за допомогою читання текстового файлу В«algF. txtВ», заповнена матриця представлена ​​на малюнку 11.
В
Малюнок 11 - Введення матриці з файлу
На малюнку 12 представлено висновок матриці найкоротших відстаней заданого графа, крім матриці показано час роботи програми в секундах.
В
Рисунок 12 - Висновок результатів роботи програми за алгоритмом Флойда
На малюнку 13 показана матриця найкоротших шляхів, програма реалізована за допомогою алгоритму Беллмана-Форда. Заповнення матриці відстаней здійснюємо за допомогою читання текстового файлу В«algBF. TxtВ» У тому ж малюнку показано час роботи програми. Повний код програми знаходиться в Додатку Б. У реалізації цього алгоритму довелося додати зовнішній цикл, в якому будуть пробігати всі вершини: for ( start_v = 1; start_v <= n; start_v + + ) , таким чином цей алгоритм тепер знаходить немає від однієї вершини до всіх інших, а від кожної вершини до всіх інших.
В
Малюнок 13 - Висновок результатів роботи програми за алгоритмом Беллмана-Форда
5. Тестування програм реалізації алгоритмів
.1 Тестування правильності
Протокол тестування правильності роботи програми за алгоритмом Флойда міститься в таблиці 1. У вхідних даних вводиться матриця відстаней, так само матрицю очікуємо отримати і у вихідних даних. Будемо вважати, що неіснуюче ребро між двома вершинами буде дорівнювати inf = 1000. Перший приклад характеризує орієнтований граф, другий же неорієнтоване. У 3 - му випадку граф складається з 6 вершин. В 4 та 5 прикладах використовуються ребра негативного ваги, де останній задає граф з циклом негативного ваги.
Таблиця 1 - Тестування правиль...
