基于Dijkstra算法记录两点间最短路径的C++实现求助

嘿，你已经走对了大半路——你甚至提前声明了parent数组来存储路径树，只是还差最后几步把路径从这个数组里提取出来！我来帮你把这部分补上。

问题分析 #

你的代码核心逻辑已经正确，但有两个关键细节需要调整：

• parent数组初始化错误：你现在在循环里反复设置parent[u_id] = -1，应该给每个节点的前驱都初始化为-1，这样除起点外，其他节点的前驱一开始都是未知状态。
• 缺少路径回溯逻辑：计算完最短距离后，需要从目标节点v_id出发，通过parent数组反向回溯到起点u_id，再反转路径得到正序的起点到终点路径。

修改后的完整代码 #

#include <vector>
#include <climits>
#include <algorithm>
#include <iostream>
using namespace std;

// 假设你的vertex和directed_graph类定义如下（根据你的代码推测）
template<typename T>
struct vertex {
    int id;
    T weight;
    vertex(int i, T w) : id(i), weight(w) {}
};

template<typename T>
class directed_graph {
public:
    vector<vector<T>> get_adjacency_matrix() { return adj_matrix; }
    bool contains(int id) { return id >= 0 && id < num_verts; }
    T get_vert_weight(int id) { return vert_weights[id]; }
    int num_vertices() { return num_verts; }
    void add_edge(int u, int v, T weight) {
        adj_matrix[u][v] = weight;
    }
    directed_graph(int n) : num_verts(n), adj_matrix(n, vector<T>(n, 0)), vert_weights(n, 0) {}
private:
    int num_verts;
    vector<vector<T>> adj_matrix;
    vector<T> vert_weights;
};

// 你的min_distance函数（假设实现如下）
int min_distance(int dist[], bool sptSet[], int n) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < n; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

template<typename T>
vector<vertex<T>> shortest_path(directed_graph<T> g, int u_id, int v_id) {
    vector<vertex<T>> shortest_path_result;
    vector<vector<T>> graph = g.get_adjacency_matrix();
    
    // 检查起点或终点是否不存在
    if (!g.contains(u_id) || !g.contains(v_id)) {
        return shortest_path_result;
    }
    
    int num_verts = g.num_vertices();
    int *dist = new int[num_verts];
    bool *sptSet = new bool[num_verts];
    int *parent = new int[num_verts]; // 改用动态数组避免栈溢出
    
    // 正确初始化所有数组
    for (int i = 0; i < num_verts; i++) {
        parent[i] = -1; // 每个节点的前驱初始化为-1
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    dist[u_id] = 0;
    
    // Dijkstra核心逻辑（这部分你已经写对了）
    for (int count = 0; count < num_verts - 1; count++) {
        int u = min_distance(dist, sptSet, num_verts);
        sptSet[u] = true;
        
        for (int v = 0; v < num_verts; v++) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                parent[v] = u;
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    
    // 回溯提取最短路径
    if (dist[v_id] == INT_MAX) {
        cout << u_id << " -> " << v_id << " : n/a（无路径）" << endl;
        delete[] dist;
        delete[] sptSet;
        delete[] parent;
        return shortest_path_result;
    }
    
    // 从终点往起点回溯
    int current = v_id;
    while (current != -1) {
        shortest_path_result.push_back(vertex<T>(current, g.get_vert_weight(current)));
        current = parent[current];
    }
    // 反转得到正序路径（起点到终点）
    reverse(shortest_path_result.begin(), shortest_path_result.end());
    
    // 输出结果（可选，可根据需求调整）
    cout << u_id << " -> " << v_id << " 的最短距离: " << dist[v_id] << endl;
    cout << "路径: ";
    for (size_t i = 0; i < shortest_path_result.size(); i++) {
        if (i > 0) cout << " -> ";
        cout << shortest_path_result[i].id;
    }
    cout << endl;
    
    // 释放动态分配的内存
    delete[] dist;
    delete[] sptSet;
    delete[] parent;
    
    return shortest_path_result;
}

// 测试代码
int main() {
    directed_graph<int> g1(9); // 0-8共9个节点
    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);
    
    // 测试从0到4的最短路径
    auto path = shortest_path(g1, 0, 4);
    return 0;
}

关键修改点说明 #

1. 修复parent数组初始化：将parent[u_id] = -1改为parent[i] = -1，确保每个节点的前驱都被正确初始化。
2. 动态分配数组：改用动态分配的parent数组，避免顶点数量较多时的栈溢出问题（也可以用vector<int> parent(num_verts, -1)更安全）。
3. 路径回溯与反转：从目标节点开始，通过parent数组反向遍历到起点，再反转数组得到正序的起点到终点路径。
4. 边界处理：如果目标节点不可达，返回空路径并给出提示，同时释放所有动态分配的内存避免泄漏。

测试结果 #

运行测试代码后，从0到4的最短路径会输出为0 -> 1 -> 7 -> 6 -> 5 -> 4，最短距离为28，符合预期。

内容的提问来源于stack exchange，提问作者Dov Royal