Дан взвешенный ориентированный граф. Необходимо найти циклы отрицательной длины, а точнее пары вершин, путь между которыми может быть неограниченно мал.
Мое решение:
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.
Просьба объяснить что неверно в таком рассуждении и, если это не трудно, привести контрпример.
Заранее спасибо.
Мое решение:
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.
Просьба объяснить что неверно в таком рассуждении и, если это не трудно, привести контрпример.
Заранее спасибо.
0 -1 inf inf
-1 0 0 inf
inf 0 0 100
inf inf 100 0
Между 3 и 4 можно сделать сколь угодно маленький путь
AFAIK, правильно так:
"между вершинами i и j не существует кратчайшего пути тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется d[t][t]<0"
http://e-maxx.ru/algo/floyd_warshall_algorithm
А что именно непонятно? Само условие или почему это так?
Ещё раз, само условие выглядит так:
если существует такая t, что
d[i][t]<INF && d[t][t]<0 && d[t][j]<INF,
то кратчайший путь (i,j) - бесконечно маленький.
2) между вершинами v1 и v2 есть путь сколь угодно малого веса <=> есть вершина t, которая доступна из v1 и из которой доступна v2, т.ч. через t проходит цикл отрицательного веса (т.к. путей, проходящих через каждую вершину не более, чем однажды, конечное число)
1) + 2) = вышеописанный алгоритм