C++怎么实现Dijkstra最短路径算法_C++图论算法与邻接表实现-C++-PHP中文网

C++怎么实现Dijkstra最短路径算法_C++图论算法与邻接表实现

冰火之心

发布： 2025-11-24 15:39:05

原创

336人浏览过

使用邻接表和优先队列实现Dijkstra算法，从源点出发，每次选取距离最短的未访问节点进行松弛，更新邻居距离，直至处理所有节点，得到单源最短路径。

c++怎么实现dijkstra最短路径算法_c++图论算法与邻接表实现

在C++中实现Dijkstra最短路径算法，通常结合图论中的邻接表结构和优先队列来高效处理。该算法适用于带权有向或无向图，且权重非负的情况，能求出从一个源点到其他所有顶点的最短距离。

邻接表存储图结构

使用vector嵌套pair的方式构建邻接表，每个顶点保存其相邻顶点及对应边的权重。

typedef pair pii; // {距离, 目标节点}
vector> graph; // graph[u] 包含所有从u出发的边

添加边的操作如下：

void addEdge(int u, int v, int weight) { graph[u].push_back({weight, v}); }

使用优先队列优化Dijkstra

Dijkstra的核心是贪心策略：每次取出当前距离最小的未访问节点进行松弛操作。使用priority_queue（最小堆）可以快速获取最小距离节点。

LanguagePro

LanguagePro是一款强大的AI写作助手，可以帮助你更好、更快、更有效地写作。

120

查看详情

立即学习“C++免费学习笔记（深入）”；

const int INF = 1e9; vector dist; priority_queue, greater> pq; // 小根堆 {距离, 节点} void dijkstra(int start) { dist.assign(graph.size(), INF); dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); // 如果已找到更短路径，跳过 if (d > dist[u]) continue; for (auto& edge : graph[u]) { int w = edge.first; int v = edge.second; if (dist[u] + w 完整示例与输出结果

以下是一个完整的可运行示例：

#include #include #include #include using namespace std; typedef pair pii; vector> graph; vector dist; void addEdge(int u, int v, int w) { graph[u].push_back({w, v}); } void dijkstra(int start) { dist.assign(graph.size(), INT_MAX); priority_queue, greater> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d != dist[u]) continue; for (auto& edge : graph[u]) { int w = edge.first; int v = edge.second; if (dist[u] + w 输出结果为：从0到0的最短距离: 0
从0到1的最短距离: 3
从0到2的最短距离: 1
从0到3的最短距离: 4
从0到4的最短距离: 7

基本上就这些。邻接表节省空间，优先队列提升效率，整体时间复杂度约为O((V+E)logV)，适合稀疏图使用。

以上就是C++怎么实现Dijkstra最短路径算法_C++图论算法与邻接表实现的详细内容，更多请关注php中文网其它相关文章！