🔥 Как ускорить алгоритм Флойда-Уоршелла в C# с помощью разбиения на блоки

Алгоритм Флойда-Уоршелла решает задачу всех пар кратчайших путей с помощью динамического программирования. Он работает за O(n³), где n — количество вершин в графе. Это делает его эффективным для небольших графов, но с ростом их размера алгоритм становится не таким быстрым.

Вместо обработки всей матрицы расстояний за один шаг, граф делится на небольшие блоки. Эти блоки обрабатываются поочередно, что помогает улучшить локальность данных и повышает эффективность кэширования на уровне процессора. В результате алгоритм работает быстрее, особенно при работе с большими и разреженными графами.

Как это работает?
⚙️ Создаем матрицу смежности, где храним расстояния между вершинами графа.
⚙️ Делим матрицу на меньшие блоки и обновляем кратчайшие пути внутри блоков и между ними.
⚙️ Получаем итоговую матрицу кратчайших путей, где каждый элемент показывает кратчайший путь между парой вершин.

📎 Оригинал статьи