c++ 实现 Dijkstra 求Point3d点集的最短路径

在C++中，Dijkstra算法通常用于寻找图中最短路径的问题，特别是无权有向图或有权无环图（例如，点到点的距离）。对于Point3d点集，我们可以先构建一个邻接矩阵或邻接表表示它们之间的连接，然后应用Dijkstra算法来找到两点间的最短距离。

以下是使用优先队列（如`std::priority_queue`）实现Dijkstra算法的基本步骤：

1. 定义数据结构：存储节点（Point3d）、当前已知最小距离、以及前驱节点的信息。可以创建一个`struct Node`或者`class`，包含节点值、距离、和一个指向邻居的引用。

#include <vector>
#include <queue>

struct Node {
    Point3d point;
    int distance;
    Node* prev;
};

2. 初始化：将起点的距离设为0，其他所有点的距离设为无穷大，并标记为未访问。

3. 创建优先队列：存放尚未处理的节点，按照距离排序。

4. 主循环：直到队列为空，取出当前距离最小的节点，更新其相邻节点的距离并标记为已访问。

5. 更新邻接节点：遍历节点的相邻点，如果通过这个节点到达比直接到达更近，就更新距离和前驱节点。

6. 返回结果：从终点开始跟随前驱节点链，重建路径。

下面是一个简化版的Dijkstra实现示例（假设`Graph`类代表点集及其边的关系，`add_edge`添加边）：

Node dijkstra(const Graph& graph, const Point3d& start) {
    std::priority_queue<Node> pq({start, {start, 0, nullptr}}); // 初始堆中只有一个节点
    std::vector<Point3d> visited(graph.size(), start);
    visited[start] = start.distance = 0;

    while (!pq.empty()) {
        auto [current, current_dist] = pq.top(); // 取出距离最小的节点
        pq.pop();

        if (visited[current] != current)
            continue; // 如果已经访问过，跳过

        for (const auto& neighbor : graph.get_neighbors(current)) {
            int new_dist = current_dist + graph.get_distance(current, neighbor);
            if (new_dist < visited[neighbor]) {
                visited[neighbor] = new_dist;
                pq.push({neighbor, new_dist, &current}); // 更新邻接节点
            }
        }
    }

    return *visited.rbegin(); // 返回终点的节点信息，包含了最短路径
}