Алгоритм Джонсона - функция h

Question

Алгоритм Джонсона использует алгоритм Беллмана-Форда в качестве подпрограммы для повторного взвешивания входного графа для устранения отрицательных весов на его ребрах (при условии отсутствия отрицательных циклов).В стандартной реализации после добавления дополнительного узла, соединенного со всеми остальными с 0 ребрами веса, мы определяем новый вес:

w '(u, v) = w(u, v) + h (u) - h (v)

Этот новый вес должен удовлетворять двум требованиям:

• инвариантность кратчайшего пути (кратчайшие пути одинаковы в пересчитанном графе)
• взвешивание неотрицательных ребер (все ребра должны иметь неотрицательный вес)

В своей стандартной реализации функция h, таким образом,определяется как вес кратчайшего пути (расстояние) от добавленного узла до целевого узла:

h (v) = d (s, v)

Итак, что мне интересно: есть ли смысл определять h в противном случае?Один из аспектов, о которых я думаю, - это то, что для этого требуется запуск Bellman-Ford.Это в основном из любопытства, поэтому для меня важны даже мелкие детали, если есть альтернативы «каноническому» определению h .

Answer 1

Здесь есть два угла атаки.

Первое - это изменение определения w '. Текущее определение не только сохраняет кратчайшие пути; это сохраняет различия между длинами путей, соединяющих одни и те же конечные точки. У меня нет никаких конкретных идей для использования здесь разрыва. К сожалению, любое повторное взвешивание, которое удовлетворяет более сильному свойству, имеет связанную функцию h.

Второе - это изменение определения h. Этот угол бесперспективен, поскольку, когда мы переписываем неотрицательное условие, оно выглядит как

h(w) <= h(v) + d(v, w) for all vw in E,

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