Это дословное утверждение тривиально неверно: в графе, где все ребра имеют нулевой вес, нет циклов с отрицательным весом, но каждый путь самый короткий.То, что мы можем доказать, это следующая (но важная) другая версия:
Если нет циклов с отрицательным весом, то существует кратчайший путь от источника s краковина t, имеющая не более n - 1 ребер, где n - количество вершин в графе.
Вот доказательство.Предположим, что существует кратчайший путь из >= n ребер.Тогда этот путь имеет > n вершин.По принципу голубя, две вершины совпадают.Таким образом, мы можем удалить часть пути, преобразовав s -> (sequence-1) -> v -> (sequence-2) -> v -> (sequence-3) -> t в s -> (sequence-1) -> v -> (sequence-3) -> t.Длина цикла v -> (sequence-2) -> v была неотрицательной, поэтому наш новый путь не хуже старого.И поскольку старый утверждал, что он самый короткий, он тоже не может быть лучше.Вместе это означает, что мы удалили цикл с нулевым весом.
Важно то, что количество вершин уменьшилось во время нашей процедуры, поскольку мы удалили хотя бы одно вхождение v.Теперь повторяйте описанную выше процедуру до тех пор, пока путь не будет иметь ребер менее 1020 *.Это все еще кратчайший путь.Итак, мы доказали, что существует кратчайший путь с < n ребрами.