Что такое отрицательный вес ребра?

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


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