Почему алгоритм Дейкстры не работает с отрицательными весами?
Алгоритм Дейкстры : это алгоритм поиска графа, который использует жадный подход для поиска кратчайшего пути от исходного узла ко всем остальным оставшимся узлам. Он решает задачу поиска кратчайшего пути из одного источника для взвешенного графа. Этот алгоритм отслеживает веса ребер для поиска пути, минимизирующего общее расстояние.
Временная сложность: O(V + E*log(V)), когда используется приоритетная очередь (где V — узлы, а E — ребра)
Ограничения алгоритма Дейкстры : для правильной работы этого алгоритма:
- График должен быть взвешенным и направленным.
- Веса должны быть неотрицательными.
Преимущества алгоритма Дейкстры :
- Он имеет линейную временную сложность, поэтому его можно легко использовать для больших задач.
- Он полезен при поиске кратчайшего расстояния, поэтому он также используется в картах Google и при расчете трафика.
- Он используется в таких областях, как телефонные сети и географические карты.
Недостатки алгоритма Дейкстры :
- Он не может обрабатывать отрицательные веса.
- Это своего рода слепой подход, так что это пустая трата времени.
Почему алгоритм Дейкстры не работает с отрицательными весами?
Давайте рассмотрим простой пример, чтобы лучше понять, почему алгоритм Дейкстры не работает для отрицательных весов.
Рассмотрим циклический ориентированный граф с узлами A, B и C , который соединен ребрами, веса которых представляют стоимость использования этого ребра. Ниже приведены веса, указанные на диаграмме выше:
А -> В = 5, А -> С = 6, С -> В = -3 . Здесь один вес C -> B отрицателен.
- Рассмотрим узел A как исходный узел, и задача состоит в том, чтобы найти кратчайшее расстояние от исходного узла A до всех других узлов, присутствующих в графе, т. е. узлов B и C.
- Итак, сначала отметьте расстояние как 0 в узле A (поскольку расстояние от A до A равно 0 ), а затем отметьте этот узел как посещенный, что означает, что он был включен в кратчайший путь.
- Поскольку в начале расстояние исходного узла до всех остальных узлов неизвестно, поэтому инициализируйте его как infinity . Обновите это расстояние, если найдено любое расстояние короче бесконечности (что в основном является жадным подходом)
- Затем обновите расстояние от исходного узла A до B , указав вес ребра, соединяющего его с A , который равен 5 (поскольку 5 < бесконечность).
Аналогичным образом также обновите расстояние от A до C , которое ранее было бесконечностью, до 6 (поскольку 6 < бесконечности). - Теперь проверьте кратчайшее расстояние от исходного узла A и, поскольку 5 — наименьшее расстояние от A до B , пометьте узел B как « посещенный ».
Точно так же следующий кратчайший путь равен 6 , поэтому узел C также помечается как посещенный. В этот момент посещаются все три узла графа. - Теперь возникает самый важный шаг, так как можно видеть, что, следуя этому алгоритму, кратчайшее расстояние от A -> B равно 5 , но если пройти расстояние через узел C , то есть путь A -> C -> B , расстояние будет равно 3 (поскольку A–>C = 6 и C–>B = -3 ), поэтому 6 + (-3) = 3. Поскольку 3 меньше 5 , но алгоритм Дейкстры дает неверный ответ как 5 , что это не самое короткое расстояние. Следовательно , алгоритм Дейкстры не работает для отрицательных случаев.
Вывод:
- Поскольку Дейкстра следует жадному подходу, после того, как узел помечен как посещенный, его нельзя пересмотреть, даже если есть другой путь с меньшей стоимостью или расстоянием. Эта проблема возникает только в том случае, если в графе существует отрицательный вес или ребро.
- Таким образом, этот алгоритм не может найти минимальное расстояние в случае отрицательных весов , поэтому для нахождения кратчайшего расстояния в случае отрицательных весов используется альтернативный алгоритм Беллмана-Форда, поскольку он останавливает цикл, когда он встречает отрицательный цикл.