使用 Dijkstra 算法跟踪两个节点之间的最短路径

Question

我对 c++ 很陌生，并且在修改 Dijkstra 的算法以跟踪两个节点之间的最短路径时遇到了麻烦，而不仅仅是最短距离。我让它正确计算最短距离。这是计算最短距离的函数：

vector<vertex<T>> shortest_path(directed_graph<T> g, int u_id, int v_id) {
vector<vertex<T>> shortest;
vector<vector<T>> graph = g.get_adjacency_matrix();
if (!g.contains(u_id) && !g.contains(v_id)) {
return shortest;
}
shortest.push_back(vertex<T>(u_id, g.get_vert_weight(u_id)));
int *dist = new int[g.num_vertices()]; // Will hold the shortest distance from u_id to i
bool *sptSet = new bool[g.num_vertices()]; // Will be true if vertex i is including in shortest path tree from u_id to i
int parent[g.num_vertices()]; // parent to store the shortest path tree
// initialise all distances as INFINITE and set stpset as false
for (int i = 0; i < g.num_vertices(); i++) {
parent[u_id] = -1;
dist[i] = INT_MAX;
sptSet[i] = false;
}
dist[u_id] = 0; // Distance of source vertex to itself is always 0
for (int count = 0; count < (g.num_vertices() - 1); count++) { // find shortest path for all vertices
int u = min_distance(dist, sptSet, g.num_vertices()); // pick the min distance vertex from the set of vertices not yet processed
sptSet[u] = true; // mark the picked vertex as processed
for (int v = 0; v < g.num_vertices(); v++) { // update dist value of the adjacent vertices of the picked vertex
// update dist[v] only if its not in sptset, there is an edge from u to v, and total weight of path from u_id to v
// through u is smaller than current distance value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
parent[v] = u;
dist[v] = dist[u] + graph[u][v];
}
}
}
for (int i = 0; i < g.num_vertices(); i++) {
if (dist[i] != INT_MAX) {
cout << u_id << " -> " << i << " : " << dist[i] << endl;
} else {
cout << u_id << " -> " << i << " : n/a" << endl;
}
}
return shortest;
}

这是我一直用于测试的图表：

g1.add_edge(0, 1, 4);
g1.add_edge(7, 0, 8);
g1.add_edge(1, 7, 11);
g1.add_edge(7, 8, 7);
g1.add_edge(1, 2, 8);
g1.add_edge(8, 2, 2);
g1.add_edge(7, 6, 1);
g1.add_edge(8, 6, 6);
g1.add_edge(6, 5, 2);
g1.add_edge(5, 2, 4);
g1.add_edge(2, 3, 7);
g1.add_edge(3, 5, 14);
g1.add_edge(4, 3, 9);
g1.add_edge(5, 4, 10);

有人可以帮我解决最短的路径吗？

Answer 1

您可以使用parent数组来重建从目标节点到源节点的路径，例如：

vector<int> path;
int idx = v_id;
while (idx != u_id) {
path.emplace_back(idx);
idx = parent[idx];
}
path.emplace_back(idx);
reverse(path.begin, path.end());
cout << "PATH: ";
for (int x : path) {
cout << x << " ";
}