Кратчайший путь: Беллман-Форд против Джонсона

Question

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

Answer 1

Алгоритм Беллмана-Форда находит кратчайший путь от одного источника ко всем вершинам графа («кратчайшие пути из одного источника»).Алгоритм Джонсона находит кратчайший путь из каждой вершины в каждую другую вершину («кратчайший путь из всех пар»), поэтому он эквивалентен запуску Беллмана-Форда из каждой возможной начальной вершины вашего графа.

Answer 2

Я знаю, что опаздываю на эту вечеринку, но я просто наткнулся на вопрос, потому что я просто спрашивал себя об этом.

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

Хорошее объяснение можно найти здесь: http://www.geeksforgeeks.org/johnsons-algorithm/

Answer 3

Алгоритм Беллмана Форда используется для нахождения кратчайшего пути от одной вершины (источника) до всех остальных вершин, тогда как алгоритм Джонсона используется для нахождения всех пар кратчайшего пути. Если вы хотите реализовать алгоритм Джонсона в C, сообщите мне.