Dijsktra 算法的 C/C++ 代码实现

迪杰斯特拉（Dijkstra）算法是一种用于解决单源最短路径问题的图算法，由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。它能够找到从一个特定源节点到图中所有其他节点的最短路径。在C/C++中实现Dijkstra算法通常涉及到数据结构如邻接矩阵或邻接表，以及优先队列（如二叉堆）来存储待处理的节点。 一、Dijkstra算法的核心思想： 1. 初始化：设置源节点的距离为0，其他所有节点的距离为无穷大（通常用一个较大的整数表示）。 2. 创建优先队列，并将所有节点按距离排序，初始时源节点距离最小。 3. 在每次迭代中，取出当前距离最小的节点，将其作为当前处理节点。 4. 遍历当前节点的所有邻居，如果通过当前节点到达邻居的路径比已知的最短路径更短，则更新该邻居的最短路径。 5. 将更新后的邻居节点放入优先队列中，重复步骤3至所有节点都被处理。 二、C/C++实现的关键部分： 1. 数据结构的选择：可以使用邻接矩阵或者邻接表来表示图。邻接矩阵适合稠密图（边较多），邻接表适合稀疏图（边较少）。 - 邻接矩阵：用二维数组表示，`int graph[V][V]`，其中V是顶点数量，`graph[u][v]`表示顶点u到顶点v的边的权重。 - 邻接表：用链表表示每个顶点的邻居，节省空间。 2. 优先队列：C++标准库提供`<queue>`和`<priority_queue>`，其中`priority_queue`适用于Dijkstra算法，因为它总是返回最小元素。 3. 主体代码： - 使用`priority_queue`，元素为节点及其距离，比较器按照距离从小到大排序。 - 初始化距离数组，源节点设为0，其余设为无穷大。 - 循环直到优先队列为空，每次从队列中取出最小节点，遍历其邻居并更新距离。 - 更新节点距离后，若更短，需要重新入队列。 三、C/C++实现示例伪代码： ```cpp #include <queue> #include <vector> using namespace std; // 假设图是以邻接列表形式存储 vector<pair<int, int>> adj[V]; // 存储邻居及其权重 void dijkstra(int src) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; vector<int> dist(V, INT_MAX); // 初始化距离数组 dist[src] = 0; // 源节点距离设为0 pq.push({0, src}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (auto neighbor : adj[u]) { int v = neighbor.first; int weight = neighbor.second; int alt = dist[u] + weight; if (alt < dist[v]) { // 如果发现更短路径 dist[v] = alt; pq.push({alt, v}); } } } // 输出最短距离数组dist } ``` 这个代码实现了Dijkstra算法的基本逻辑，实际应用中可能需要根据具体问题进行调整，例如处理负权重边的情况（Dijkstra算法不适用负权重边）。同时，为了提高效率，可以考虑使用 Fibonacci heap 或其他高效优先队列数据结构。在C++中，可以使用第三方库如 Boost 或自行实现。