алгоритм Беллмана – Форда :
Кратчайший путь от источника ко всем остальным узлам в взвешенном ориентированном графе, даже с весом -eve ребра (не цикл). медленнее, но универсальнее, чем Dijsktra.
Сложность: O (| V |. | E |)
BFS: Найти путь от одной заданной вершины к другим узлам в невзвешенном неориентированном графе.
Сложность: O (| V | + | E |) . это быстрее, когда вы знаете вершины впереди и используете соответствующую структуру данных, т.е. FIFO Que для определения, какая вершина уже обработана, чем сложность, может быть уменьшена до O (| V |)
DFS: Найти кратчайший путь от источника к другим узлам. в дереве, а также в графике. График может содержать цикл, что означает, что узел можно посещать снова и снова. поэтому мы можем использовать логический массив для отслеживания посещенных узлов. в противном случае алгоритм не остановится.
более того, заглядывайте все глубже и глубже и заходите как можно дальше до конца ветки в дереве.
Сложность: O (| V | + | E |) . и Сложность: O (| V |) место для хранения вершин.
Алгоритм использования Варшала:
Найти все пары кратчайшего пути в направленном невзвешенном графе с весом ребра + eve, -eve (не цикл). но это не возвращает детали самих путей.
он может быть использован для определения веса цикла на графике. когда это находит, это заканчивается. он сравнивает все возможные пути через граф между каждой парой вершин. поэтому он использует динамический подход, а не жадный подход.
Сложность: O (| V ^ 3 |)
Алгоритм Джонсона: найти все пары кратчайших путей в ориентированном взвешенном разреженном графе, когда вес ребра равен + eve, -eve, но не -eve цикла.
сначала он использует алгоритм Бельмана-Форда для вычисления преобразованного графа из исходного графа. это удаляет все весовые края. затем Дейкстра применяется для поиска путей.
Сложность: O (V ^ 2 Log V + VE)
Алгоритм Дейкстры:
исходная версия этого алгоритма не использует Priority Que, поэтому сложность равна O (| V ^ 2 |) , но более новая версия использует эту структуру данных, поэтому сложность становится равной O (E + V log V) . и это более быстрый алгоритм кратчайшего пути из одного источника. это работает, назначая предварительный вес посещенному узлу и бесконечность непосещенным узлам для посещенного узла, ищет его все не посещенные края и выбирает с минимальным весом. и добавьте его в набор путей.
Алгоритм Крушкала: , чтобы найти MST, где он находит край наименьшего возможного веса, который соединяет любые два дерева в лесу на неориентированном, взвешенном графике.
это жадный алгоритм.
это также находит Минимальный Охватывающий Лес.
Сложность: O (E log V)
Алгоритм Прима: находит подмножество ребер, которые образуют дерево на неориентированном взвешенном графе. но не могу найти MS Forest, как алгоритм Крушкала.
Алгоритм Броувки: Проблема этого алгоритма состоит в том, что веса должны быть уникальными в графе. он находит MST, исследуя каждую вершину, затем помещая с меньшим весом. этот алгоритм параллелен по своей природе, но не быстрее, чем алгоритм Прима.
Та же сложность, что и у алгоритма Крушкала.