double arrow

Рёбра отрицательного веса

Иногда веса ребер могут быть отрицательными. При этом важно, есть ли циклы отрицательного веса. Если из вершины s можно добраться до цикла отрицательного веса, то потом можно обходить этот цикл сколь угодно долго, и вес будет всё уменьшаться, так что для вершин этого цикла кратчайших путей не существует:

В таком случае можно считать, что вес кратчайшего пути есть −∞.

Если же циклов отрицательногов веса нет, то любой цикл можно выбросить не удлиняя пути. Путей без циклов конечное число, так что вес кратчайшего пути корректно определен.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: