powqer's blog

By powqer, 13 years ago, In Russian
Дан взвешенный ориентированный граф. Необходимо найти циклы отрицательной длины, а точнее пары вершин, путь между которыми может быть неограниченно мал.
Мое решение:
1)Посчитать расстояния между всеми парами вершин алгоритмом Флойда.(в итоге получим матрицу путей d[i][j])
2)Если для двух вершин v1 и v2 справедливо, что d[v1][v2]+d[v2][v1]<0, то
d[v1][v2]=d[v2][v1]=d[v1][v1]=d[v2][v2]=-INF.
Просьба объяснить что неверно в таком рассуждении и, если это не трудно, привести контрпример.
Заранее спасибо.
  • Vote: I like it
  • 0
  • Vote: I do not like it