如何基于邻接表用Dijkstra算法获取指定起止节点的最短路径

原实现仅计算了各节点到源点的距离，要获取指定起止节点的完整路径，核心是添加前驱节点追踪机制，具体修改步骤如下：

1. 新增前驱数组 #

在算法初始化阶段，创建一个与节点数量一致的parent数组，用于记录每个节点在最短路径上的前一个节点。初始化时，源点的前驱设为自身（或-1），其余节点设为无效值。

2. 松弛操作时同步更新前驱 #

在更新节点距离的逻辑中，当发现通过当前节点能得到更短路径时，除了更新目标节点的距离，还要将目标节点的前驱设为当前节点。

3. 回溯前驱数组生成路径 #

新增一个路径回溯函数，从目标节点出发，沿着前驱数组反向追溯到源点，再反转结果得到从源点到目标节点的完整路径。

修改后的代码示例 #

假设原代码采用邻接表存储图结构，以下是关键修改部分：

// 定义前驱数组（V为节点总数）
int parent[V];

void dijkstra(vector<vector<pair<int, int>>> &graph, int src) {
    // 初始化距离数组（原代码保留）
    int dist[V];
    fill(dist, dist + V, INT_MAX);
    dist[src] = 0;

    // 初始化前驱数组
    fill(parent, parent + V, -1);
    parent[src] = src;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto &edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                parent[v] = u; // 更新前驱节点
                pq.push({dist[v], v});
            }
        }
    }
}

// 回溯生成并打印路径
void printShortestPath(int dest) {
    if (parent[dest] == -1) {
        cout << "目标节点不可达" << endl;
        return;
    }

    vector<int> path;
    int curr = dest;
    // 回溯到源点
    while (curr != parent[curr]) {
        path.push_back(curr);
        curr = parent[curr];
    }
    path.push_back(curr); // 添加源点
    reverse(path.begin(), path.end());

    cout << "最短路径节点序列: ";
    for (int node : path) {
        cout << node << " ";
    }
    cout << endl;
}

使用方式 #

1. 调用dijkstra(graph, 源点编号)计算距离和前驱关系；
2. 调用printShortestPath(目标节点编号)输出完整路径。

比如以你的示例数据，源点为0、目标为3时，输出会类似：最短路径节点序列: 0 1 5 6 3。

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