Dijkstra算法详解及C++实现

算法

Dijkstra算法是由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1956年提出的一种解决单源最短路径问题的贪心算法。它用于计算图中一个节点到其他所有节点的最短路径，主要适用于有向图和无向图（边权重必须为非负值）。

算法原理

初始化：设置起始点到自身的距离为0，到其他所有点的距离为无穷大。
选择当前距离最小的节点：从未处理的节点中选择距离起始点最近的节点。
松弛操作：对于当前节点的所有邻居，检查是否可以通过当前节点获得更短的路径。
标记为已处理：当前节点处理完毕后，标记为已处理，不再参与后续计算。
重复：重复步骤2-4，直到所有节点都被处理。

C++实现

以下是Dijkstra算法的C++实现，包含优先队列优化：

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

using namespace std;

// 定义图的邻接表表示
typedef pair<int, int> iPair; // <顶点, 权重>

class Graph {
    int V; // 顶点数
    vector<vector<iPair>> adj; // 邻接表

public:
    Graph(int V) : V(V), adj(V) {}
    
    // 添加边
    void addEdge(int u, int v, int w) {
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w); // 无向图需要添加双向边
    }
    
    // Dijkstra算法实现
    void dijkstra(int src) {
        // 优先队列，存储<距离, 顶点>
        priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
        
        // 初始化所有距离为无穷大
        vector<int> dist(V, INT_MAX);
        
        // 插入源点，距离为0
        pq.push(make_pair(0, src));
        dist[src] = 0;
        
        while (!pq.empty()) {
            // 取出距离最小的顶点
            int u = pq.top().second;
            pq.pop();
            
            // 遍历所有邻接顶点
            for (auto &[v, weight] : adj[u]) {
                // 松弛操作
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
        
        // 打印结果
        cout << "顶点\t距离源点的距离\n";
        for (int i = 0; i < V; ++i) {
            cout << i << "\t" << dist[i] << endl;
        }
    }
};

int main() {
    int V = 9;
    Graph g(V);
    
    // 添加图的边
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);
    
    g.dijkstra(0);
    
    return 0;
}