Действительно ли нам нужно добавить дополнительный узел в алгоритм Джонсона?

Question

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

Answer 1

Еще одна причина, по которой алгоритму Джонсона нужен дополнительный узел s, заключается в том, что этот узел гарантирует, что каждый другой узел в графе доступен через алгоритм Беллмана-Форда (т. Е. Каждый узел u несет минимум вес от s до u). Если это не может быть гарантировано, повторное взвешивание невозможно, и, следовательно, алгоритм не будет работать. Обратите внимание, что добавление нового узла s не вводит (новый) цикл отрицательного веса.

Answer 2

Таким способом можно ввести отрицательный цикл. Учитывая график

   -1
a ---> b,

выберите b в качестве корня.