c++实现迪杰斯彻算法

以下是C++实现Dijkstra迪杰斯特拉算法的代码和解释：

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

using namespace std;

// 定义边的结构体
struct Edge {
    int to; // 边的终点
    int weight; // 边的权重
    Edge(int t, int w) : to(t), weight(w) {}
};

// 定义图的结构体
struct Graph {
    int V; // 图的顶点数
    vector<vector<Edge>> adj; // 邻接表表示的图
    Graph(int v) : V(v), adj(v) {}
    void addEdge(int u, int v, int w) { // 添加边的函数
        adj[u].push_back(Edge(v, w));
        adj[v].push_back(Edge(u, w));
    }
};

// 定义Dijkstra算法的函数
vector<int> dijkstra(const Graph& G, int s) {
    vector<int> dist(G.V, INT_MAX); // 初始化距离数组
    dist[s] = 0; // 初始节点到自身的距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 定义小根堆
    pq.push(make_pair(0, s)); // 将初始节点加入小根堆
    while (!pq.empty()) {
        int u = pq.top().second; // 取出小根堆中距离最小的节点
        pq.pop();
        for (auto e : G.adj[u]) { // 遍历该节点的所有邻居
            int v = e.to;
            int w = e.weight;
            if (dist[v] > dist[u] + w) { // 如果通过u可以更新v的距离
                dist[v] = dist[u] + w; // 更新v的距离
                pq.push(make_pair(dist[v], v)); // 将v加入小根堆
            }
        }
    }
    return dist; // 返回距离数组
}

int main() {
    Graph G(6); // 创建一个6个节点的图
    G.addEdge(0, 1, 2); // 添加边
    G.addEdge(0, 2, 4);
    G.addEdge(1, 2, 1);
    G.addEdge(1, 3, 7);
    G.addEdge(2, 4, 3);
    G.addEdge(3, 4, 1);
    G.addEdge(3, 5, 5);
    G.addEdge(4, 5, 2);
    vector<int> dist = dijkstra(G, 0); // 计算从节点0到其他节点的最短距离
    for (int i = 0; i < G.V; i++) {
        cout << "Distance from node 0 to node " << i << " is " << dist[i] << endl; // 输出结果
    }
    return 0;
}

解释：

1. 首先定义了一个边的结构体Edge，包含了边的终点和权重。

2. 定义了一个图的结构体Graph，包含了图的顶点数和邻接表表示的图。其中addEdge函数用于添加边。

3. 定义了Dijkstra算法的函数dijkstra，输入参数为图G和初始节点s，输出为一个距离数组dist。算法使用了小根堆来维护距离最小的节点，具体实现见代码注释。

4. 在主函数中创建了一个6个节点的图，并添加了8条边。然后调用dijkstra函数计算从节点0到其他节点的最短距离，并输出结果。