当前位置: 首页 > news >正文

堆优化迪氏最短单源路径原理及C++实现

时间复杂度

O(ElogE),E是边数。适用与稀疏图。

使用前提

边的权为正。可以非连通,非连通的距离为-1。


原理

优选队列(小根堆)记录两个数据:当前点到源点距离,当前点。先处理距离小的点;如果距离相等,先处理谁都可以。可以用pair记录,不用重写小于。优先队列只记录如下情况的距离:
一,{0,源点}。
二,任意点的最短距离和可以直达的边。
如果是有向图,则入队数量等于边数,计算出起点最短路径的那一轮。无向图,则翻倍。显然出队数量等于入队数量。优先队列入队和出队时间复杂度都是O(logn),故总时间复杂度为O(nlogn)。

样例

 
下表分析源点为0的处理过程。
        

初始

入队{0,0}

出队{0,0}

入队{1,1}

0到源点的最短距离为0

入队{4,2}

出队{1,1}

入队{2,0}

入队{3,2}

1到源点的最短距离为1

入队{5,3}

出队{2,0}

0已经处理

出队{3,2}

入队{7,0}

2到源点最短距离为3

入队{5,1}

入队{6,3}

出队{4,2}

2已经处理

出队{5,1}

1已经处理

出队{5,3}

… 3到源点的最短距离是5。


核心代码


非常的简洁。
typedef pair<long long, int> PAIRLLI;
class  CHeapDis
{
public:
    CHeapDis(int n)
    {
        m_vDis.assign(n, -1);
    }
    void Cal( int start, const vector<vector<pair<int, int>>>& vNeiB)
    {
        std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;
        minHeap.emplace(0, start);
        while (minHeap.size())
        {
            const long long llDist = minHeap.top().first;
            const int iCur = minHeap.top().second;
            minHeap.pop();
            if (-1 != m_vDis[iCur])
            {
                continue;
            }
            m_vDis[iCur] = llDist;
            for (const auto& it : vNeiB[iCur])
            {
                minHeap.emplace(llDist + it.second, it.first);
            }
        }
    }
    vector<long long> m_vDis;
};

测试用例

#include <iostream>
#include <vector>
#include <queue>
#include <assert.h>
using namespace std;

class CDebugDis : public CHeapDis
{
public:
    using CHeapDis::CHeapDis;
    void Assert(const vector<int>& vDis)
    {
        for (int i = 0; i < vDis.size(); i++)
        {
            assert(vDis[i] == m_vDis[i]);
        }
    }
};

struct CDebugParam
{
    int n;
    vector<vector<std::pair<int, int>>> edges;
    int s;
    vector<int> dis;//答案
};

int main()
{
    vector<CDebugParam> params = { {1,{{}},0,{0}},
        {2,{{}},0,{0,-1}},{2,{{{1,2}},{{0,2}}},0,{0,2} }
        ,{3,{{{1,4},{2,5}},{{0,4}},{{0,5}}},0,{0,4,5} }
        ,{3,{{{1,4},{2,8}},{{0,4},{2,3}},{{0,8},{1,3}}},0,{0,4,7} }
        ,{3,{{{1,4},{2,8}},{{0,4},{2,5}},{{0,8},{1,5}}},0,{0,4,8} }
        ,{4,{{{1,1},{2,4}},{{0,1},{2,2},{3,4}},{{0,4},{1,2},{3,3}},{{1,4},{2,3}}},0,{0,1,3,5}}
    };
    for (const auto& par : params)
    {
        CDebugDis n2Dis(par.n);
        n2Dis.Cal(par.s, par.edges);
        n2Dis.Assert(par.dis);
    }
}


测试环境

win7 VS2019 C++17

相关下载

源码及测试用例:

https://download.csdn.net/download/he_zhidan/88390995


doc版文档,排版好
https://download.csdn.net/download/he_zhidan/88348653

相关文章:

堆优化迪氏最短单源路径原理及C++实现

时间复杂度 O(ElogE)&#xff0c;E是边数。适用与稀疏图。 使用前提 边的权为正。可以非连通&#xff0c;非连通的距离为-1。 原理 优选队列&#xff08;小根堆&#xff09;记录两个数据&#xff1a;当前点到源点距离&#xff0c;当前点。先处理距离小的点&#xff1b;如果…...

Leetcode202. 快乐数

力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1&#xff0…...

【MySQL】MySql常见面试题总结

目录 一、什么是sql注入 二、sql语句的执行流程 三、内连接和外连接的区别 四、Union和Union All 有什么区别 五、MySql如何取差集 六、DELETE和TRUNCATE有什么区别 七、count&#xff08;*&#xff09;和count&#xff08;1&#xff09;的区别 八、MyISAM和InnoDB的区…...

【Java 进阶篇】JDBC PreparedStatement 详解

在Java中&#xff0c;与关系型数据库进行交互是非常常见的任务之一。JDBC&#xff08;Java Database Connectivity&#xff09;是Java平台的一个标准API&#xff0c;用于连接和操作各种关系型数据库。其中&#xff0c;PreparedStatement 是 JDBC 中一个重要的接口&#xff0c;用…...

嵌入式Linux应用开发-驱动大全-第一章同步与互斥①

嵌入式Linux应用开发-驱动大全-第一章同步与互斥① 第一章 同步与互斥①1.1 内联汇编1.1.1 C语言实现加法1.1.2 使用汇编函数实现加法1.1.3 内联汇编语法1.1.4 编写内联汇编实现加法1.1.5 earlyclobber的例子 1.2 同步与互斥的失败例子1.2.1 失败例子11.2.2 失败例子21.2.3 失败…...

【计算机网络】 基于UDP的简单通讯(客户端)

文章目录 客户端流程代码实现添加头文件以及库依赖加载库创建套接字发送接收数据关闭套接字、卸载库 测试 客户端 流程 客户端跟服务端差不多&#xff0c;也要先加载库&#xff0c;在加载库之后也要创建套接字&#xff0c;但是客户端一定是没有绑定ip地址的&#xff0c;之后是…...

【云备份项目】:环境搭建(g++、json库、bundle库、httplib库)

文章目录 1. g 升级到 7.3 版本2. 安装 jsoncpp 库3. 下载 bundle 数据压缩库4. 下载 httplib 库从 Win 传输文件到 Linux解压缩 1. g 升级到 7.3 版本 &#x1f517;链接跳转 2. 安装 jsoncpp 库 &#x1f517;链接跳转 3. 下载 bundle 数据压缩库 安装 git 工具 sudo yum…...

电脑右键新建记事本不见了--设置恢复篇(无需操作注册表)

电脑右键新建记事本不见了–设置恢复篇&#xff08;无需修改注册表&#xff09; 电脑不知怎么想右键新建记事本结果竟然不见了&#xff0c;搜寻网上的都是什么修改注册表&#xff0c;粘贴代码修复&#xff08;感觉太复杂了&#xff09;&#xff0c;这里介绍通过设置内重新对记…...

JavaScript内置对象 - Array数组(四)- 序列生成器

序列生成器是生成一个指定起始值和结束值的序列&#xff0c;并且根据指定间隔长度&#xff0c;生成序列数组。 完成此功能需要使用到Array内置对象的from()对象&#xff0c;以及类数组相关知识&#xff0c;前面几篇有相关案例进行演示。 地址一&#xff1a;JavaScript内置对象…...

GD32F103x IIC通信

1. IIC通信 1.IIC的介绍 IIC总线有两条串行线&#xff0c;其一是时钟线SCK&#xff08;同步&#xff09;&#xff0c;其二是数据线SDA。只有一条数据线属于半双工。应用中&#xff0c;单片机常常作为主机&#xff0c;外围器件可以挂载多个。&#xff08;当然主机也可以有多个。…...

什么是FOSS

FOSS 是指 自由和开放源码软件(Free and Open Source Software)。这并不意味着软件是免费的。它意味着软件的源代码是开放的&#xff0c;任何人都可以自由使用、研究和修改代码。这个原则允许人们像一个社区一样为软件的开发和改进做出贡献。...

C++语言GDAL批量裁剪多波段栅格图像:基于像元个数裁剪

本文介绍基于C 语言的GDAL模块&#xff0c;按照给定的像元行数与列数&#xff0c;批量裁剪大量多波段栅格遥感影像文件&#xff0c;并将所得到的裁剪后新的多波段遥感影像文件保存在指定路径中的方法。 在之前的文章中&#xff0c;我们多次介绍了在不同平台&#xff0c;或基于不…...

简单丝的tab切换栏(html/CSS)

#html <!DOCTYPE html> <html lang"en" > <head><meta charset"UTF-8"><title>CSS实现左右滑动选项卡效果</title><link rel"stylesheet" href"https://cdnjs.cloudflare.com/ajax/libs/meyer-res…...

LabVIEW开发带式谱感测技术

LabVIEW开发带式谱感测技术 如今&#xff0c;通过无线网络传输的数据量正在迅速增加&#xff0c;并导致频谱稀缺。超过数十亿的无线设备将被连接起来&#xff0c;并需要互联网接入。因此&#xff0c;无线电频谱管理方案的效率不足以授予对所有设备的访问权限。在频谱分配中&am…...

认识柔性数组

在C99中&#xff0c;结构中的最后一个元素允许是未知大小的数组&#xff0c;这就叫做柔性数组成员 限制条件是&#xff1a; 结构体中最后一个成员未知大小的数组 1.柔性数组的形式 那么我们怎样写一个柔性数组呢 typedef struct st_type {int i;int a[0];//柔性数组成员 }ty…...

熔断、限流、降级 —— SpringCloud Alibaba Sentinel

Sentinel 简介 Sentinel 是阿里中间件团队开源的&#xff0c;面向分布式服务架构的高可用流量防护组件&#xff0c;主要以流量为切入点&#xff0c;从限流、流量整形、熔断降级、系统负载保护、热点防护等多个维度来帮助开发者保障微服务的稳定性 Sentinel 提供了两个服务组件…...

python经典百题之反向输出数字

题目:输入一个整数&#xff0c;并将其反转后输出。 程序分析 我们需要对输入的整数进行反转&#xff0c;即将整数的数字反向排列。 方法1&#xff1a;使用字符串反转 解题思路 将整数转换为字符串&#xff0c;然后对字符串进行反转。 代码实现 def reverse_integer_usin…...

复习Day08:哈希表part01:242.有效的字母异位词、349. 两个数组的交集、1. 两数之和、160. 相交链表

之前的blog&#xff1a;https://blog.csdn.net/weixin_43303286/article/details/131765317 我用的方法是在leetcode再过一遍例题&#xff0c;明显会的就复制粘贴&#xff0c;之前没写出来就重写&#xff0c;然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用…...

用 Pytest+Allure 生成漂亮的 HTML 图形化测试报告

本篇文章将介绍如何使用开源的测试报告生成框架 Allure 生成规范、格式统一、美观的测试报告。 通过这篇文章的介绍&#xff0c;你将能够&#xff1a; 将 Allure 与 Pytest 测试框架相结合&#xff1b; 如何定制化测试报告内容 执行测试之后&#xff0c;生成 Allure 格式的测…...

Python字符串索引解码乱码谜题

输入数行“数字字母”字符组成的乱码字符串&#xff0c;根据谜题规则解码出乱码字符串中隐藏的单词信息。 (本笔记适合熟悉python字符串索引操作的 coder 翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#xff1a;大咖免费“圣经”…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...