Лучший алгоритм поиска кратчайшего пути
Едва ли дополнение в VS, но одном каждом VS использует потребности: Обработчик Предварительных просмотров Кода Предоставляет обработчику предварительных просмотров подсветку синтаксиса для исходных файлов. Обработчик работает в области предварительного просмотра Проводника и на вкладке предварительного просмотра для вложений в Outlook.
4 ответа
Алгоритм Дейкстры находит кратчайший путь между узлом и каждым другим узлом в графе. Вы запускаете его один раз для каждого узла. Веса должны быть неотрицательными, поэтому при необходимости вы должны сначала нормализовать значения в графе.
Floyd-Warshall вычисляет кратчайшие маршруты между всеми парами узлов за один проход! Вес цикла должен быть неотрицательным, а график должен быть направленным (ваша диаграмма - нет).
Алгоритм Джонсона использует алгоритм Дейкстры для поиска всех пар за один проход, и быстрее для разреженных деревьев (см. ссылку для анализа).
Floyd Warshall находит пути между всеми парами вершин, но Дейкстра находит путь только от одной вершины ко всем остальным.
Флойд Уоршалл - это O (| V | 3 ), а Дикстра - это O (| E | + | V | log | V |), но вам придется запустить его V раз, чтобы найти все пары, что дает сложность O (| E * V | + | V 2 | log | V |) Я думаю. Это означает, что, возможно, многократно использовать Dijsktra быстрее, чем алгоритм FW, я бы попробовал оба подхода и посмотрел, какой из них самый быстрый в фактическом случае.
Дейкстра находит кратчайший путь только из одной вершины, Флойд-Уоршалл находит его между всеми из них.
Используйте алгоритм Флойда-Уоршалла, если вы хотите найти кратчайший путь между всеми парами вершин, поскольку он имеет (намного) большее время работы, чем алгоритм Дейкстры.
Алгоритм Флойда-Уоршалла имеет худшую производительность O (| V | 3 ), тогда как у алгоритма Дейкстры худшая производительность O (| E | + | V | log | V | )