ності алгоритму Флойда
№ п/пВходние данниеВиходние данниеТестОжідаемий результатДействітельний результатMatr [N] [N] Matr [N] [N] Matr [N] [N] 10 inf 3 inf 2 0 inf inf inf 7 0 1 6 inf inf 00 10 3 4 2 0 5 6 7 7 0 1 6 16 9 00 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0 +20 inf 1 лютого inf 0 inf 5 січня inf 0 4 2 5 4 00 7 1 2 7 0 8 5 1 8 0 3 2 5 3 00 7 1 2 7 0 8 5 1 8 0 3 2 5 3 0 + 30 7 9 inf inf 14 7 0 10 15 inf inf 9 10 0 11 inf 2 inf 15 листопада 0 6 inf inf inf inf 6 0 14 вересня inf 2 inf 9 00 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 00 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 0 + 4 0 inf -3 inf 2 0 inf inf inf 7 0 1 6 inf inf 00 4 -3 -2 2 0 -1 0 7 7 0 1 6 10 3 00 4 -3 -2 2 0 -1 0 7 7 0 1 6 10 3 0 + 50 inf -3 inf 2 0 inf inf inf 7 0 -1 -6 inf inf 0В графі є цикл негативного веса.В графі є цикл негативного ваги. +
Протокол тестування правильності роботи програми за алгоритмом Беллмана-Форда міститься в таблиці 2. У вхідних даних вводиться матриця відстаней, так само матрицю очікуємо отримати і у вихідних даних. Будемо вважати, що неіснуюче ребро між двома вершинами буде дорівнювати inf = 1000. Перший приклад характеризує орієнтований граф, другий же неорієнтоване. У 3 - му випадку граф складається з 6 вершин. В 4 та 5 прикладах використовуються ребра негативного ваги, де останній задає граф з циклом негативного ваги.
Таблиця 2 - Тестування правильності алгоритму Беллмана-Форда
№ п/пВходние данниеВиходние данниеТестОжідаемий результатДействітельний результатMatr [N] [N] Matr [N] [N] Matr [N] [N] 10 inf 3 inf 2 0 inf inf inf 7 0 1 6 inf inf 00 10 3 4 2 0 5 6 7 7 0 1 6 16 9 00 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0 +20 inf 1 лютого inf 0 inf 5 січня inf 0 4 2 5 4 00 7 1 2 7 0 8 5 1 8 0 3 2 5 3 00 7 1 2 7 0 8 5 1 8 0 3 2 5 3 0 + 30 7 9 inf inf 14 7 0 10 15 inf inf 9 10 0 11 inf 2 inf 15 листопада 0 6 inf inf inf inf 6 0 14 вересня inf 2 inf 9 00 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 00 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 0 + 4 0 inf 3 inf -2 0 inf inf inf 7 0 -1 6 inf inf 00 10 3 2 -2 0 -1 0 5 7 0 -1 6 16 9 00 10 3 2 -2 0 -1 0 5 7 0 -1 6 16 9 0 + 50 inf -3 inf 2 0 inf inf inf 7 0 -1 -6 inf inf 0В графі є цикл негативного веса.В графі є цикл негативного ваги. +
Проаналізувавши обидва протоколи ми побачимо, що обидві програми працюють коректно і виводять одне і теж правильне рішення.
5.2 Аналіз за часом
Аналіз за часом проводиться функцією clock () із стандартної бібліотеки
