当前位置: 首页 > 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;大咖免费“圣经”…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...