Кратчайший путь -> Как справиться с отрицательным весом? - PullRequest
Новая
       54

Кратчайший путь -> Как справиться с отрицательным весом?

0 голосов
/ 03 декабря 2018

У меня есть вершины V = {s, u, v, x}, а также края E = {(s, u), (s, x), (s, v), (u, v), (v, x), (x, u)), а также следующие веса: 

W(s, u) = 1
W(v, x) = W(x, u) = W(s, v)=2
W(u, v) = -3
W(s, x) = -1

Теперь я выполняю Initialize (G, w, s), делая s начальной точкой, и инициализирую sd = 0. Iнужны кратчайшие пути пути u, v, x.Поскольку все они связаны с s, я могу просто использовать вес W (s, u), W (s, v), W (s, x).Но xd будет -1.Это даже применимо?Могу ли я теперь использовать это расстояние, чтобы правильно выполнить Relax (s, x, w) и получить правильный вывод?

Заранее спасибо

1 Ответ

0 голосов
/ 03 декабря 2018

Как говорит алгоритм Дейкстры с отрицательными весами , пока нет отрицательных циклов, Беллмана-Форда будет сходиться.Если есть отрицательный цикл, он обнаружит этот факт.

Если есть отрицательные циклы, то для него нет решения, кроме как связать стоимость перехода от А к В с набором отрицательных ребер, которые былипо пути, чтобы вы могли их отследить и больше не посещать.Это теоретически правильно, но дорого как по памяти, так и по времени работы.

...