dijkstra算法用于求解带权图单源最短路径，适用非负权重边。1. 采用邻接表存储图结构，节省空间；2. 使用优先队列（最小堆）快速选取距离最小节点；3. 通过松弛操作更新邻居距离；4. 利用visited数组避免重复处理；5. 时间复杂度为o((v + e) log v)。示例输出从起点0到各节点的最短距离：节点0:0，节点1:7，节点2:3，节点3:9，节点4:5。
Dijkstra算法是解决带权图单源最短路径问题的经典方法，适用于边权重为非负的图。下面是一个基于邻接表和优先队列（最小堆）实现的C++版本Dijkstra算法，效率较高，时间复杂度为 O((V + E) log V)。
使用优先队列优化的Dijkstra算法实现
该实现使用 STL 中的 priority_queue 和 vector 来表示图和维护待处理节点。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定义边：目标节点和权重
struct Edge {
int to, weight;
Edge(int t, int w) : to(t), weight(w) {}
};
// 定义优先队列中的元素：距离和节点
struct Node {
int node, dist;
Node(int n, int d) : node(n), dist(d) {}
// 重载操作符，使优先队列按距离从小到大排序（最小堆）
bool operator<(const Node& other) const {
return dist > other.dist; // 注意：priority_queue默认是最大堆，所以用>实现最小堆
}
};
class Graph {
int V; // 节点数量
vector<vector<Edge>> adj; // 邻接表
public:
Graph(int v) : V(v) {
adj.resize(V);
}
// 添加边（无向图可调用两次或修改为双向）
void addEdge(int u, int v, int w) {
adj[u].push_back(Edge(v, w));
}
// Dijkstra算法求最短路径
void dijkstra(int start) {
vector<int> dist(V, INT_MAX); // 距离数组
vector<bool> visited(V, false); // 访问标记
priority_queue<Node> pq;
dist[start] = 0;
pq.push(Node(start, 0));
while (!pq.empty()) {
Node curr = pq.top();
pq.pop();
int u = curr.node;
if (visited[u]) continue;
visited[u] = true;
// 遍历所有邻接节点
for (const Edge& e : adj[u]) {
int v = e.to;
int weight = e.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push(Node(v, dist[v]));
}
}
}
// 输出结果
cout << "从起点 " << start << " 到各节点的最短距离：" << endl;
for (int i = 0; i < V; ++i) {
if (dist[i] == INT_MAX)
cout << "到节点 " << i << "：不可达" << endl;
else
cout << "到节点 " << i << "： " << dist[i] << endl;
}
}
};
主函数示例
创建一个简单图并运行Dijkstra算法：
MD5校验和计算小程序（C）
下载
C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。
int main() {
Graph g(5); // 创建5个节点的图
// 添加有向边（起点、终点、权重）
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 3);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 2);
g.addEdge(2, 1, 4);
g.addEdge(2, 3, 8);
g.addEdge(2, 4, 2);
g.addEdge(3, 4, 7);
g.addEdge(4, 3, 9);
g.dijkstra(0); // 从节点0开始计算最短路径
return 0;
}
关键点说明
该实现的核心在于：
立即学习“C++免费学习笔记（深入）”；
- 使用 邻接表 存储图，节省空间且适合稀疏图。
- 用 优先队列 快速取出当前距离最小的未处理节点。
- 通过 松弛操作 更新邻居的距离。
- 使用 visited 数组避免重复处理节点。
输出示例
对于上述图，从节点0出发的输出可能如下：
到节点 0： 0到节点 1： 7
到节点 2： 3
到节点 3： 9
到节点 4： 5 基本上就这些。这个版本简洁高效，适合学习和实际应用。
