Я реализовал алгоритм Флойда-Варшалла для страницы Википедии .Я хочу обнаружить отрицательные циклы на следующем графике испытаний:
A ? -1 ? B
? ↖ ?
2 -1 -1
? ↖?
D ? -1 ? C
Все ребра имеют вес -1, если только D -> A.
Запуск реконструкции пути
procedure Path(u, v)
if next[u][v] = null then
return []
path = [u]
while u ≠ v
u ← next[u][v]
path.append(u)
return path
приводит к бесконечному циклу, потому что путь к D является циклом, который не возвращается к D.Это содержимое моего next:
B -> A = C
C -> A = A
D -> A = A
A -> B = B
C -> B = A
D -> B = A
A -> C = B
B -> C = C
D -> C = A
A -> D = B
B -> D = C
C -> D = A
Например, путь от C до D будет C -> A -> B -> C -> A -> B ... Таким образом, D никогда не достигается, а цикл while в Path никогда не выйдет.
У меня вопрос, является ли это предполагаемым поведением и что-то, что я должен проверить, когда я запускаю реконструкцию пути.Я тщательно проверил свою реализацию и не могу найти никаких расхождений между эталонной реализацией в Википедии.