Поиск всех кратчайших путей и расстояний с помощью Флойда-Уоршалла

Во-первых, небольшая предыстория: я работаю над созданием простого класса графа с базовыми алгоритмами графа (Dijkstra, Floyd-Warshall, Bellman-Ford и т. Д.) Для использования в качестве справочного листа для предстоящего соревнования по программированию.

Пока у меня есть работающая версия Floyd-Warshall, но недостатком является то, что пока я получаю только самую короткую. значение расстояния между двумя узлами, а не кратчайший путь . Я бы предпочел, чтобы построение пути происходило внутри самого алгоритма, вместо того, чтобы вызывать другую функцию для его восстановления.

Вот некоторая информация о структурах данных, которые я использую:

vector > graph // содержит значения расстояния от каждого узла до каждого другого узла (graph [1] [3] содержит длину ребра от узла №1 до узла №3, если ребра нет, то значение равно INF

vector > путь // содержит "ступеньки" о том, как достичь заданного узла. path [st_node] [end_node] содержит значение следующего узла на пути от end_node -> st_node

Вот пример данных графика, который я использую:

INF 10  INF INF INF INF
INF INF 90  15  INF INF
INF INF INF INF INF 20
INF INF INF INF 20  INF
INF INF  5  INF INF INF
INF INF INF INF INF INF

, и вот желаемые значения, которые должны быть в "пути" переменная (полученная при запуске Dijkstra с каждого из узлов):

INF  0   4   1   3   2
INF INF  4   1   3   2
INF INF INF INF INF  2
INF INF  4  INF  3   2
INF INF  4  INF INF  2
INF INF INF INF INF INF

Вот ссылка на код, который я сейчас использую для алгоритма: (через PasteBin) .

Любая помощь была бы очень оценен!

Редактировать: Я пробовал код Википедии для генерации матрицы путей, и вот результат:

INF INF  4   1   3   4
INF INF  4  INF  3   4
INF INF INF INF INF INF
INF INF  4  INF INF  4
INF INF INF INF INF  2
INF INF INF INF INF INF

Он вроде работает, но имеет проблемы, когда дело доходит до представления «отдельных» шагов. Например, путь от узла 0 к узлу 1 везде не определен. (Но тем не менее, спасибо Nali4Freedom за предложение)