c++迪杰斯特拉算法

Dijkstra算法是一种用于解决单源最短路径问题的图论算法，在C++中实现Dijkstra算法通常涉及以下几个步骤：

1. **初始化**：将起始节点的距离设为0，其他所有节点的距离设为无穷大（常用INT_MAX）。创建一个优先队列存放节点及其距离，起始节点入队。

2. **查找最小距离**：从队列中取出当前距离最小的节点，这个节点就是当前已经找到最短路径的节点。

3. **更新邻接节点**：遍历该节点的所有未访问邻居，计算通过该节点到达邻居的总距离（当前节点距离 + 邻居之间的边的权重），如果这个新距离小于邻居当前的距离，则更新邻居的距离并将邻居加入队列。

4. **继续迭代**：重复第2步和第3步，直到队列为空或者找到目标节点为止。如果队列为空还未找到目标，说明源点到其他所有节点都没有路径。

5. **结果存储**：当算法结束时，已知的最短路径是从起点到每个节点的直接路径长度。

以下是C++实现的一个简单版本（假设图是一个邻接矩阵表示）：

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

std::vector<int> dijkstra(std::vector<std::vector<int>>& graph, int start) {
    int n = graph.size();
    std::vector<int> dist(n, std::numeric_limits<int>::max());
    dist[start] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0 && dist[v] > dist[u] + graph[u][v]) {
                dist[v] = dist[u] + graph[u][v];
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}