Лекція 14. Пошук найкоротшого шляху. Алгоритм Джонсона

Лекция 14. Поиск кратчайшего пути. Алгоритм Джонсона. #Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Алгоритм Джонсона использует алгоритм Беллмана-Форда https://youtu.be/tvHEFBET0_k для предварительной обработки графа, заменяя отрицательный вес ребер на положительный. Далее к полученному графу многократно используемый алгоритм Дейкстры: https://youtu.be/3TEybSp0H6k .