Использование Флойд-Варшалла для выявления положительных циклов

Question

Я видел, как люди говорили, что Флойд-Варшалл может быть модифицирован (легко) для обнаружения циклов. Примечание: я предполагаю, что график не имеет отрицательных циклов. Я хочу знать, как изменить алгоритм? И почему это правильно? Кроме того, какие циклы вы можете сделать это обнаружить? Самый короткий, самый длинный, длины k? - а какие корректировки в алгоритме нужно сделать?

Я прочитал этот вопрос, который заставил меня задуматься над этим вопросом: найти цикл наименьшей длины в ориентированном графе с положительными весами

Для приведенной выше ссылки, я не понимаю, почему сделать диагональ прил. matrix = INFINITY дает нам циклы наименьшей длины, проходящие через (i,i).

Наконец, этот сайт: http://en.algoritmy.net/article/45708/Floyd-Warshall-algorithm говорит:

 Floyd-Warshall algorithm can be easily modified to detect cycles. 
 If we fill negative infinity value at the diagonal of the matrix and run the 
 algorithm, then the matrix of predecessors will contain also all cycles in the graph 
 (the diagonal will not contain only zeros, if there is a cycle in the graph).

Так что я не думаю, что понимаю это, потому что это кажется неправильным, потому что, если память служит мне правильно, обнаружение всех циклов не может быть сделано за много времени. Я неправильно понимаю, что говорится? (Также не совсем уверен, что подразумевается под матрицей предшественников.)

Answer 1

Я полагаю, что матрица предшественников является конечным результатом вычисления расстояний от любой вершины до любой другой вершины, F_ij= длина кратчайшего маршрута от узла i до узла j, 0, если маршрута нет. Если диагонали матрицы смежности установлены в бесконечность, это эффективно запрещает собственные петли, поэтому единственный способ, которым F_ii может быть ненулевым, - это если есть путь от узла i к себе через хотя бы один другой узел, то есть цикл. В общем, любой алгоритм поиска пути можно превратить в алгоритм поиска петли. Возьмите узел, через который вы хотите найти петлю, скажем v, и разбейте его на два узла v_out и v_in, причем v-out имеет только ребра из v, а v_in имеет только ребра в v. Теперь используйте алгоритм для поиска путь от v_out к v_in, он станет циклом, если v_out и v_in объединятся с v.