Вопрос по теме алгоритм Дейкстры и графы
Будет ли давать алгоритм Дейкстры правильный ответ в графе, в котором ребро с отрицательным весом? Если нет то можете объяснить почему
Ответы (1 шт):
Нет, для графов с отрицательными весами алгоритм Дейкстры в общем случае не работает, что называется by design, например можно рассмотреть следующий граф:
/-\ 2 /-\ 1 /-\
|S| ------> |A| -------> |B|
\-/ \-/ \-/
\ ^
\ /
4 \ / -3
\ /
v /
/-\
|C|
\-/
Стартовая вершина S. На первом шаге алгоритм присвоит длину минимального пути до вершин A и С и отметит вершину S, как посещённую:
X 0 2 ∞
/-\ 2 /-\ 1 /-\
|S| ------> |A| -------> |B|
\-/ \-/ \-/
\ ^
\ /
4 \ / -3
\ /
v /
/-\
|C|
\-/
4
Далее он будет рассматривать вершину A (т.к. длина пути до неё минимальна) присвоит длину пути до вершины B и отметит A, как посещённую:
X 0 X 2 3
/-\ 2 /-\ 1 /-\
|S| ------> |A| -------> |B|
\-/ \-/ \-/
\ ^
\ /
4 \ / -3
\ /
v /
/-\
|C|
\-/
4
Дальше он будет рассматривать вершину B но т.к. достежимых вершин из неё нет, то просто отметит её как посещённую, и вершину С, но т.к. все вершины достижимые из неё посещены, то он также просто отметит её как посещённую:
X 0 X 2 X 3
/-\ 2 /-\ 1 /-\
|S| ------> |A| -------> |B|
\-/ \-/ \-/
\ ^
\ /
4 \ / -3
\ /
v /
/-\
|C|
\-/
X 4
Это и будет результатом работы алгоритма, но т.к. очевидно, что цена пути до вершины A по пути S→C→A составляет всего 1, а не 2 то результат работы алгоритма, очевидно, не верен.
Для поиска кратчайшего пути на графах с отрицательными весами рёбер есть другие алгоритмы, например Беллмана — Форда.