最短路径（迪杰斯特拉算法）c++

迪杰斯特拉(Dijkstra's Algorithm)是一种用于寻找有向图或无向图中最短路径的经典算法，通常用于单源最短路径问题。在C++中实现迪杰斯特拉，我们可以按照以下几个步骤：

1. **定义数据结构**：
- 使用`std::priority_queue`来管理未处理的顶点及其距离估计。
- 定义一个辅助数组`dist`来记录每个顶点到已知源点的距离，初始时除了源点外全部设置为无穷大（通常用INT_MAX）。
- 可能还需要一个布尔数组`visited`来标记哪些顶点已被访问过。

2. **函数原型**：

   void dijkstra(std::vector<std::pair<int, int>>& graph, int src, std::vector<int>& dist, std::vector<bool>& visited);

其中`graph`是一个二维数组或邻接表，表示图的连接；`src`是源点的索引；`dist`和`visited`分别是距离数组和访问标志数组。

3. **核心算法流程**：
- 将源点加入优先队列，初始距离设为0。
- 循环直到优先队列为空：
a. 弹出优先队列中距离最小的未访问顶点u。
b. 更新其相邻顶点v的距离，如果通过u到v的距离小于当前已知距离，则更新`dist[v]`。
c. 标记顶点u为已访问。
- 结果会在`dist`数组中，`dist[i]`就是源点到顶点i的最短距离。

4. **示例代码片段**：

   while(!pq.empty()) {
       int u = pq.top().second; // 获取下标
       pq.pop();
       visited[u] = true;
       // 更新相邻顶点v的距离
       for (auto &edge : graph[u]) {
           int v = edge.first;
           int weight = edge.second;
           if (!visited[v] && dist[u] + weight < dist[v]) {
               dist[v] = dist[u] + weight;
               pq.push({dist[v], v});
           }
       }
   }

5. **输出结果**：
仅当`dist`数组完整计算完成后，可以遍历数组，获取从源点到所有其他顶点的最短距离。