C++实现单元最短路径

在C++中，实现单元最短路径通常涉及图论算法，比如Dijkstra算法或者Floyd-Warshall算法。这里我们以Dijkstra算法为例，它常用于寻找有向无环图(DAG)或加权非负边的最短路径。

**Dijkstra算法步骤：**
1. 初始化：将起点的距离设置为0，其他所有顶点的距离设置为无穷大，标记为未访问。
2. 选择距离最小的未访问顶点u作为当前顶点。
3. 更新邻接节点：对于u的所有邻居v，如果通过u到达v的距离(d(u, v))小于v当前已知的距离，则更新v的距离，并将其标记为已访问。
4. 重复步骤2和3，直到所有顶点都被访问过，或者找到目标节点。

**C++代码示例：**

#include <vector>
#include <queue>
#include <limits>

struct Edge {
    int to;
    int weight;
};

class Graph {
private:
    std::vector<std::vector<Edge>> adj; // 邻接表表示

public:
    void dijkstra(int start) {
        std::priority_queue<pair<int, int>, std::vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> dist(adj.size(), INT_MAX);
        dist[start] = 0;

        pq.push({0, start});

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

            if (dist[u] != INT_MAX && dist[u] < dist[vertex]) {
                for (const auto& edge : adj[u]) {
                    int new_dist = dist[u] + edge.weight;
                    if (new_dist < dist[edge.to]) {
                        dist[edge.to] = new_dist;
                        pq.push({new_dist, edge.to});
                    }
                }
            }
        }
    }
};

// 使用示例
Graph g;
g.dijkstra(0); // 从节点0开始搜索最短路径

在这个例子中，`Graph`类包含邻接列表表示图，并封装了Dijkstra算法。`dijkstra`函数接受起始节点作为参数，返回从起始节点到所有其他节点的最短路径。