Алгоритм Флойда-Варшалла кратчайшего пути

Question

Я реализовал алгоритм Флойда-Варшалла. В соответствии с их матрицами я могу получить правильный результат о кратчайшем пути между двумя местами и их расстоянии. У меня вопрос, как распечатать кратчайшее расстояние от i до j. Я провел несколько исследований и нашел такой алгоритм. Может кто-нибудь объяснить мне, как это должно быть, или как это работает, или высказать другое предложение?

PrintShortestPath(P,i,j){
    if(i==j) print i
    else if (P[i][j]==NULL)
        print "No path from i to j"
    else{
        PrintShortestPath(P,i,P[i][j])
        print j
    }
}

Answer 1

Алгоритм Флойда учитывает все пути между двумя узлами и позволяет найти самый дешевый, найденный на данный момент. Ваш код идет об этом рекурсивно. Вот еще одна реализация с хорошим объяснением этого в C: http://www.fearme.com/misc/alg/node88.html

Вы можете также рассмотреть алгоритм Дейкстры, который может быть лучше для разреженных графов.

--L.

Answer 2

Матрица P в опубликованном вами алгоритме является матрицей предшественника. Он перечисляет для каждого пути i -> j предшественника.

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

• P[i,j] инициализируется до NULL для i,j
• В самом внутреннем цикле FW обновите P[i,j], если вы найдете более короткий путь, проходящий от узла k (используйте P[k,j]).

Я могу быть более точным, если вы отправите свое решение для расстояния.