Во-первых, немного предыстории: я работаю над созданием простого класса графов с базовыми алгоритмами графов (Дейкстра, Флойд-Варшалл, Беллман-Форд и т. Д.) Для использования в качестве справочного листа для предстоящего конкурса по программированию. *
Пока у меня есть работающая версия Флойд-Варшалла, но недостатком является то, что пока у меня только самое короткое значение расстояния между двумя узлами, а не кратчайший путь, Желательно, чтобы построение пути происходило внутри самого алгоритма, а не вызывало другую функцию для его восстановления.
Вот некоторая информация о структурах данных, которые я использую:
vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF
vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from 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
и вот нужные значения в переменной «path» (получаемые при запуске 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 за предложение)