11 April - 17 April

КН, групи 5 и 6:  (Floyd-Warshall, Ford-Bellman)

Тази седмица взехме алгоритъма на Floyd-Warshall за намиране на най-кратките пътища между всеки два върха в граф за O(N^3), където N е броят на върховете в графа. Алгоритъмът е коректен дори когато в графа има ребра с отрицателна дължина, за разлика от Dijkstra, където алгоритъмът не изкарва верни резултати и е неприложим.
Също така, разгледахме и алгоритъма на Ford-Bellman за намиране на краткия път между един конкретен връх и всички останали за O(N*M), където N е броят на върховете в графа, а M е броят ребра. Този алгоритъм е приложим също, когато искаме да проверим дали в графа има отрицателен цикъл (такъв със сума на ребрата си по-малка от 0). Ако има такъв, който е достижим от началния връх, тогава не можем да говорим за минимален път в графа. Защо? Защото можем да се въртим до безкрай в отрицателния цикъл и така минималният ни път да става все по-малък.
И двата алгоритъма могат да се прилагат върху ориентирани и неориентирани графи.

Задача, която решихме: Имайки матрица на съседство на граф, да се направи съответната и матрица на достижимост (на позиция (i, j) стои 1, ако от връх i можем да достигнем връх j, или 0 в противен случай).