Просто поставлю это, это домашний вопрос, но я хотел бы получить второе мнение о моих мыслях, чтобы увидеть, был ли мой мыслительный процесс правильным.
Скажем, у нас есть неориентированный граф G = (V, Е).Мы знаем, что алгоритм Флойда-Варшалла находит все кратчайшие пути (наименьший вес) в графе, если G не имеет отрицательных циклов.
Итак, предположим, что у нас есть граф, в котором имеет отрицательныйцикл.Возникает вопрос, есть ли алгоритм, который мы можем создать, чтобы Флойд-Варшалл мог работать с этим графом?
Моя логика: если у нас есть граф с отрицательным циклом, конечное наименьшее (наиболее отрицательный) вес (т. е. на ребре есть вес -4, а на ребре нет веса меньше -4).Поэтому за время O (| E |) я пересекаю график, чтобы найти наименьший вес.Затем я могу добавить абсолютное значение наименьшего веса для каждого ребра.Мы изменили бы график, добавив этот наименьший вес к каждому ребру.Таким образом, не будет никаких отрицательных циклов, поскольку каждый вес должен быть положительным.Теперь мы можем запустить Floyd-Warshall на нашем графике.
Что касается моей логики, есть ли недостатки, которые очевидны?Будет ли это жизнеспособным решением?