Возврат после запуска алгоритма Джонсона

Question

У меня есть вопрос, который мне задавали на прошлых экзаменах в моей школе, и я не могу найти на него ответ.

Можно ли узнать окончательную матрицу после выполнения алгоритма Джонсона на графике, чтобы узнать, имел ли он ранее отрицательные циклы или нет? Почему?

---

Алгоритм Джонсона

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

Алгоритм состоит из (из Википедии ):

• Сначала к графу добавляется новый узел q, соединенный ребрами с нулевым весом с каждым другим узлом.
• Во-вторых, алгоритм Беллмана – Форда , начиная с новой вершины q, используется для нахождения для каждой вершины v минимального веса h(v) пути от q до v. Если этот шаг обнаруживает отрицательный цикл, алгоритм завершается.
• Затем ребра исходного графа заново взвешиваются с использованием значений, вычисленных по алгоритму Беллмана – Форда : ребру от u до v, имеющему длину w(u, v), присваивается новый длина w(u,v) + h(u) − h(v).
• Наконец, q удаляется, и Алгоритм Дейкстры используется для нахождения кратчайших путей от каждого узла s до каждой другой вершины в пересчитанном графе.

Answer 1

Если вопрос предполагается интерпретировать как:

Возможно ли, зная обновленные неотрицательные веса ребер после запуска алгоритма Джонсона на графике, узнать, было ли у него изначально ребра с отрицательным весом или нет? Почему?

Тогда нет, вы не можете сказать.

Запуск алгоритма Джонсона на графике, который имеет только неотрицательные веса ребер, оставит веса без изменений. Это потому, что все кратчайшие расстояния q -> v будут равны 0. Поэтому, учитывая веса ребер после запуска Джонсона, начальные веса могли быть точно такими же.

Answer 2

Если я правильно понял ваш вопрос, который должен был выглядеть следующим образом:

Можно ли узнать окончательную матрицу парных расстояний после запуска алгоритма Джонсона на графе, чтобы узнать, было ли у него изначально ребра с отрицательным весом или нет? Почему?

Как прокомментировали здесь другие, мы должны сначала предположить, что в графике нет отрицательных циклов веса, поскольку в противном случае алгоритм Джонсона останавливается и возвращает значение False (из-за внутреннего обнаружения формы Беллмана отрицательных циклов веса).

Тогда ответ таков: если в графе существует какое-либо отрицательное весовое ребро e = (u, v), то кратчайшее взвешенное расстояние между u -> v не может быть> 0 (поскольку в худшем случае вы можете путешествовать отрицательное ребро е между этими вершинами).

Поэтому, по крайней мере, одно из ребер имело отрицательный вес в исходном графе, если любое значение на конечных попарных расстояниях составляет <0 </p>