C++如何实现Dijkstra算法_C++求解单源最短路径问题的Dijkstra算法

裘德小鎮的故事

发布时间：2025-11-25 04:41:18

340人浏览过

来源于php中文网

原创

Dijkstra算法用于求解非负权图的单源最短路径，通过优先队列优化实现。1. 使用邻接表存储图，小根堆按距离排序选取最近节点。2. 维护dist数组记录起点到各点最短距离，初始化为无穷大，源点为0。3. 每次取出堆顶节点进行松弛操作，若经当前节点到邻居更近，则更新距离并入堆。4. 忽略已处理的过时节点，避免重复计算。5. 最终输出从源点到其余各点的最短距离。代码以C++实现，时间复杂度O((V+E)logV)，适用于稀疏图。

c++如何实现dijkstra算法_c++求解单源最短路径问题的dijkstra算法

Dijkstra算法是解决单源最短路径问题的经典方法，适用于带权有向图或无向图，且所有边的权重必须为非负值。在C++中实现该算法，通常结合优先队列（堆）优化来提升效率。下面详细介绍如何用C++实现Dijkstra算法。

基本思路

Dijkstra算法通过贪心策略逐步确定从源点到其他各顶点的最短距离。核心思想是：

维护一个距离数组，记录起点到每个顶点的当前最短距离。
使用优先队列选择当前距离最小的未处理节点进行扩展。
对当前节点的所有邻接边进行松弛操作：如果通过当前节点到达邻居的距离更短，则更新距离。

数据结构设计

为了高效实现，常用以下结构：

Morph Studio

Morph Studio是一款领先的文字转视频AI平台，可以将用户输入的文字转化为精美视频。

下载

vectorair>>：邻接表存储图，pair中第一个元素是邻居节点，第二个是边权。
priority_queue, vector>, greater>>：小根堆，按距离排序，每次取出距离最小的节点。
vector：dist数组，初始化为无穷大，源点为0。

代码实现

#include 
#include 
#include 
#include 
using namespace std;

void dijkstra(vector>>& graph, int start) {
    int n = graph.size();
    vector dist(n, INT_MAX);
    priority_queue, vector>, greater>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue; // 跳过过时节点

        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << "Distance from " << start << " to " << i << " is " << dist[i] << endl;
    }
}

int main() {
    int n = 5; // 节点数
    vector>> graph(n);

    // 添加边：u -> v，权重w
    graph[0].push_back({1, 10});
    graph[0].push_back({3, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 2});
    graph[2].push_back({4, 4});
    graph[3].push_back({1, 3});
    graph[3].push_back({2, 9});
    graph[3].push_back({4, 2});
    graph[4].push_back({0, 7});
    graph[4].push_back({2, 6});

    dijkstra(graph, 0);
    return 0;
}

注意事项与优化

实际使用中需要注意几点：

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

确保图中没有负权边，否则应使用Bellman-Ford算法。
优先队列可能包含重复节点，需判断当前弹出的距离是否已过时。
若需要输出路径，可额外维护一个parent数组，在松弛时记录前驱节点。
稀疏图适合邻接表+堆优化，时间复杂度约为O((V+E)logV)。

基本上就这些。掌握这个模板后可以根据具体题目调整输入方式和输出格式。

c++中如何求矩阵的转置_c++二维数组矩阵转置代码

C++如何实现一个A*寻路算法？C++游戏AI与路径规划【算法实战】

c++在Unreal Engine中的应用_c++ UE4/5游戏开发基础

如何用C++实现一个有限状态机（FSM）？C++游戏AI与协议解析【设计模式】

c++如何实现一个简单的神经网络推理框架_c++ ONNX Runtime集成【AI】

相关标签:

edge ai c++ ios stream int 数据结构堆算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：C++怎么使用OpenMP进行并行编程_C++共享内存并行计算入门下一篇：C++23的deducing this是什么_C++中允许在成员函数中推导*this的类型

作者最新文章

电脑开机一直循环重启进入不了桌面怎么办_系统修复教程

2026-01-09 09:25

电脑文件误删怎么恢复_回收站清空了找回文件方法【教程】

2026-01-09 09:34

ZLibrary忘记密码怎么办 ZLibrary账号密码找回【步骤】

2026-01-09 09:35

C++中的堆内存和栈内存有什么区别？(手动管理与自动分配)

2026-01-09 09:43

学习通官方平台登录学习通网页版官方入口在线访问

2026-01-09 09:53

声音传播速度是多少空气中声速是多少【解答】

2026-01-09 09:59

c++中如何使用tuple元组_c++ tuple存储多个不同类型数据

2026-01-09 09:59

C++编译器优化级别-O2和-O3的区别？(代码体积与运行速度的权衡)

2026-01-09 10:01

像素火影免安装网页官方秒玩地址分享

2026-01-09 10:03

喜马拉雅官方听书网站喜马拉雅网页版官网入口

2026-01-09 10:11

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

string转int

在编程中，我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算，或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

315

2023.08.02

int占多少字节

int占4个字节，意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值，在某些情况下也可能是2个字节或8个字节，int是一种常用的数据类型，用于表示整数，需要根据具体情况选择合适的数据类型，以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

533

2024.08.29

c++怎么把double转成int

本专题整合了 c++ double相关教程，阅读专题下面的文章了解更多详细内容。

2025.08.29

C++中int的含义

本专题整合了C++中int相关内容，阅读专题下面的文章了解更多详细内容。

193

2025.08.29

treenode的用法

在计算机编程领域，TreeNode是一种常见的数据结构，通常用于构建树形结构。在不同的编程语言中，TreeNode可能有不同的实现方式和用法，通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

533

2023.12.01

C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化，涵盖排序算法（快速排序、归并排序）、查找算法、图算法、动态规划、贪心算法等，并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构（链表、树、堆、哈希表等），帮助开发者提升在复杂应用中的算法设计与性能优化能力。

2025.12.22

深入理解算法：高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念，适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用，如数组、链表、栈、队列、哈希表、树、图等；以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析，帮助开发者不仅能熟练运用这些基础知识，还能在实际编程中优化性能，提高代码的执行效率。本专题适合准备面试的开发者，也适合希望提高算法思维的编程爱好者。

2026.01.06