c++dijsktra

### C++ 实现 Dijkstra 算法

Dijkstra 算法用于解决加权图中的单源最短路径问题，适用于有向和无向图，但要求边权重非负。该算法通过逐步扩展已知最短路径来计算从起始节点到其他所有节点的最短路径。

#### 初始化与数据结构设置
为了高效实现 Dijkstra 算法，通常采用优先队列（最小堆）来管理待处理节点及其当前估计的距离值。这样可以在每次迭代时快速获取具有最小临时距离的节点[^4]。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Node {
    int id;
    int distance;
    
    bool operator>(const Node& n) const {
        return this->distance > n.distance;
    }
};

void dijkstra(vector<vector<pair<int, int>>>& adjList, vector<int>& distances, int startVertex) {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    distances[startVertex] = 0;
    pq.push({startVertex, 0});

    while (!pq.empty()) {
        auto current = pq.top();
        pq.pop();

        if (current.distance != distances[current.id]) continue;

        for (auto neighbor : adjList[current.id]) {
            int newDist = distances[current.id] + neighbor.second;
            
            if (newDist < distances[neighbor.first]) {
                distances[neighbor.first] = newDist;
                pq.push({neighbor.first, newDist});
            }
        }
    }
}

这段代码展示了如何利用邻接表表示图形并执行 Dijkstra 的核心逻辑。`adjList` 是一个二维数组，其中每个元素都是一个包含相邻结点 ID 和对应边权重的元组列表；`distances` 数组存储从起点出发到达各顶点的最佳已知距离；函数接收这些参数以及指定的起始顶点索引作为输入[^1]。

对于给定的例子：

int main() {
    // 假设 G 表示图对象，InitD 函数初始化距离数组 D
    int D[4] = {INT_MAX};
    InitD(D, 2, 4);
    dijkstra(G.adjList, D, 2);

    for (int i = 0; i < 4; ++i) {
        cout << "顶点2与" << i << "之间的最短距离为" << D[i]<< endl;
    }

    return 0;
}

此部分实现了完整的程序流程，包括调用 `dijkstra()` 来更新距离矩阵，并打印出结果。注意这里假设存在名为 `G` 的全局变量代表整个图实例化后的状态，实际应用中应根据具体情况进行调整[^3]。