Флойд Варшалл реконструирует путь

Question

Я хочу восстановить путь от вершины источника до точки назначения в этой задаче графа.

Как я могу сохранить путь и как его получить после того, как я нашел минимальную стоимость от s до d?

Пожалуйста, помогите мне найти простой ответ?

Например, в точке,

adjmat[i][j] = Math.min(adjMat[i][j],adjMat[i][k]+adjMat[k][j]);

Мне нужно добавить путь, и мне нужно его получить.

Answer 1

Статья в Википедии об алгоритме Флойда-Варшалла содержит объяснение и псевдокод для вашей проблемы.

Answer 2

Используйте оптимальную матрицу с алгоритмом Флойда-Варшалла для восстановления пути.Он строит путь одновременно.См. Введение в теорию графов - Narsingh Deo для фактического алгоритма