Как отмечали другие, Floyd-Warshall выполняется за время O (n 3) и выполняет поиск Дейкстры от каждого узла к каждому другому узлу, предполагая, что вы используете кучу Фибоначчи для поддержки своей реализации Дейкстры , занимает O (mn + n 2 log n). Однако вы не всегда можете безопасно запускать алгоритм Дейкстры на произвольном графе, потому что алгоритм Дейкстры не работает с отрицательными весами ребер.
Существует поистине замечательный алгоритм под названием алгоритм Джонсона, который представляет собой небольшая модификация запуска алгоритма Дейкстры из каждого узла, которая позволяет этому подходу работать, даже если граф содержит отрицательные ребра (при условии, что нет отрицательных циклов). Алгоритм работает при первом запуске Беллмана-Форда на графике для его преобразования. в граф без отрицательных ребер, затем с помощью алгоритма Дейкстры, начиная с каждой вершины. Поскольку Беллман-Форд работает за время O (mn), общее асимптотическое время выполнения по-прежнему равно O (mn + n 2 log n), поэтому, если m = o (n 2 ) (обратите внимание, что это мало от n), этот подход асимптотически быстрее, чем использование Floyd-Warshall.
Единственная загвоздка здесь в том, что это предполагает, что у вас есть алгоритм Дейкстры, поддерживаемый кучей Фибоначчи. Если у вас нет доступной кучи Фибоначчи и вы не желаете вкладывать 72 часа, необходимые для ее создания, отладки и тестирования, вы все равно можете использовать двоичную кучу для алгоритма Дейкстры; он просто увеличивает время выполнения до O (m log n), поэтому эта версия алгоритма Джонсона работает за O (mn log n). Это уже не всегда асимптотически быстрее, чем Флойда-Уоршалла, потому что если m = (n 2), то Флойд-Уоршалл работает за O (n 3), в то время как алгоритм Джонсона работает в O (n 3 войти n). Однако для разреженных графов, где m = o (n 2 / log n), эта реализация алгоритма Джонсона все еще асимптотически лучше, чем Флойда-Уоршалла.
Короче:
- С кучей Фибоначчи алгоритм Джонсона всегда асимптотически не хуже, чем у Флойда-Уоршалла, хотя его сложнее закодировать.
- С двоичной кучей алгоритм Джонсона обычно асимптотически не хуже, чем Флойда-Уоршалла, но не является хорошим вариантом при работе с большими плотными графами.
Надеюсь это поможет!
person
templatetypedef
schedule
01.09.2011
