Алгоритм Джонсона отрицательные ребра - матрица расстояний

Question

Результирующая матрица = матрица, на которой mat [i] [j] - кратчайший путь с вершиной i в качестве источника и вершиной j в качестве пункта назначения.

Я написал собственную реализацию алгоритма Джонсона, и ябыло интересно, как это обрабатывает отрицательные края?В итоге, матрица расстояний, которую я получаю, не совпадает с матрицей, которую я получаю от Флойд-Варшалла.Это очевидно, когда мы перевесим график.Означает ли это, что алгоритм Джонсона не помогает нам найти стоимость самого короткого пути, а только какой из путей является самым коротким?Кроме того, если в полученной матрице есть путь между вершиной A и вершиной B стоимости 0, а другой - между вершиной A и вершиной C стоимости 0, означает ли это, что B и C одинаково далеки от A?

Answer 1

Алгоритм Джонсона должен действительно возвращать те же пути, которые вы получите с Флойд-Варшаллом - если вы этого не видите, это, вероятно, означает, что в вашей реализации где-то есть ошибка.

Вы правы в том, что алгоритм Джонсона повторно взвешивает ребра графа, но делает это довольно умным способом.В частности, в новом графе, в то время как стоимость каждого пути в новом графе может отличаться от первоначального графа, относительные затраты путей в новом графе одинаковыкак в исходном графике.В этом смысле, любые пути, возвращающиеся в качестве кратчайшего пути в новом графе, обязательно будут также кратчайшими путями из вашего исходного графа. стоимость этих путей в новом графике, тем не менее, не будет соответствовать вашему исходному графику, и поэтому в качестве шага постобработки в алгоритме Джонсона вы должны настроить расходы, произведенные для инвертирования эффектаизменение весов.

Не видя код, который вы запускаете, трудно сказать, что конкретно пошло не так.Возможно, вам повезет больше, если вы зададите дополнительный вопрос с некоторым конкретным кодом, конкретным тестовым примером, который вы используете, конкретными результатами, которые вы получаете, и почему вы считаете, что они неверны.