Поток минимальной стоимости.

Да, алгоритм, который последовательно ищет кратчайшие пути - не будет работать, поскольку он предполагает перед каждым поиском кратчайшего пути, что поток минимальной стоимости для текущего потока уже найден. Однако если есть цикл отрицательного веса, то это означает, что уже при нулевом потоке можно добиться отрицательной стоимости, т.е. поиск этого "начального" потока уже не тривиален.

Но есть и другой алгоритм - последовательного поиска циклов отрицательного веса. Он уже работает и в таких случаях, хотя в такой реализации заметно медленнее первого алгоритма. Кстати, его можно ускорить, если искать не просто любой цикл отрицательного веса, а цикл с минимальным средним весом.