Хранение кратчайшего пути
Я имею в виду этот урок: http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/
Автор упоминает это:
Мы можем изменить решение для печати кратчайших путей, также сохранив информацию о предшественнике в отдельной 2D-матрице.
Я немного запутался в том, что эта информация предшественника.
Итак, как мне сохранить путь для отображения позже?
Решение
Если вы хотите восстановить путь от узла x_1 до x_n, вы можете сделать это, перейдя к узлу x_2 и восстановив путь от x_2 до x_n. Путь от x_2 до x_n не изменяется при изменении x_1. Итак, вы хотите сохранить информацию о том, какой узел будет следующим при переходе от x_1 к x_n. Это можно сделать с помощью | V | x | V | матрица, где запись [i] [j] дает индекс следующего узла на пути от i до j.
В этой части кода
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
Вы должны добавить назначение в следующую матрицу узла.
Другие решения
Других решений пока нет …