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

多源最短路径的原理及C++实现

时间复杂度

O(n3),n是端点数。


核心代码

template<class T, T INF = 1000 * 1000 * 1000>
class CNeiBoMat
{
public:
  CNeiBoMat(int n, const vector<vector<int>>& edges,bool bDirect=false,bool b1Base= false)
  {
    m_vMat.assign(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++)
    {
      m_vMat[i][i] = 0;
    }
    for (const auto& v : edges)
    {
      m_vMat[v[0]- b1Base][v[1]- b1Base] = v[2];
      if (!bDirect)
      {
        m_vMat[v[1]- b1Base][v[0]- b1Base] = v[2];
      }
    }
  }
  vector<vector<int>> m_vMat;
};

//多源码路径
template<class T,T INF = 1000*1000*1000>
class CFloyd
{
public:
  CFloyd(const  vector<vector<T>>& mat)
  {
    m_vMat = mat;
    const int n = mat.size();
    for (int i = 0; i < n; i++)
    {//通过i中转
      for (int i1 = 0; i1 < n; i1++)
      {
        for (int i2 = 0; i2 < n; i2++)
        {
          //此时:m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
          m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
          //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
        }
      }
    }   
  };
  vector<vector<T>> m_vMat;
};


原理

当一层循环执行完后,m_vMat[i1][i2]表示经过[0,i)中的任意个点的最短距离。
初始状态下, m_vMat[i1][i2]表示直达的最小距离,也就是经过0个点。
通过[0,i)中任意个点,i1到i2的最短路径记为PrePathi1i2,通过[0,i+1)中任意个点,i1到i2的距离的路径为Pathi1i2,如果Path不经过Pathi1i2,则和PrePathi1i2相同。如果经过则可以拆分成{i1…i}+{i…i2},显然{i1…i}是PrePathi1i,{i…i2}是PrePathii2,否则替换成PrePathi1i和PrePathii2。
m_vMat同时表示PreMath和Math,如果m_vMat[i1][i]或m_vMat[i][i2]已经更新,会带来错误的结果么?结果是不会,会更新但值不变。
当i1等于i时:
m_vMat[i][i2] = min(…, m_vMat[i][i] + m_vMat[i][i2]);
由于m_vMat[i][i]为0,所以右式就是左式。
当i2等于i时,类似。


样例
 


假定有5个点,前4个点连通。整个处理流程如下:

初始状态

处理完i等于0(不变)

0

1

4

INF

INF

1

0

2

4

INF

4

2

0

3

INF

INF

4

3

0

INF

INF

INF

INF

INF

0

处理完i等于1

处理完i等于2(不变)

3

5

3

5

处理完i等于3,结果不变

最终结果

0

1

3

5

INF

1

0

2

4

INF

3

2

0

3

INF

5

4

3

0

INF

INF

INF

INF

INF

0

测试样例

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

struct CDebugParam
{
    int n;
    vector<vector<int>> edges;
    vector<vector<int>> result;
};

int main()
{
    const int INF = 1000 * 1000 * 1000;
    vector<CDebugParam> params = { {5,{{0,1,1},{0,2,4},{1,2,2},{1,3,4},{2,3,3}},
        {
            {0,1,3,5,INF},
            {1,0,2,4,INF},
            {3,2,0,3,INF},
            {5,4,3,0,INF},
            {INF,INF,INF,INF,0}
        }
        } };
    for (const auto& param : params)
    {
        CNeiBoMat<int> mo(param.n, param.edges);
        CFloyd<int> floyd(mo.m_vMat);
        for (int r = 0; r < param.n; r++)
        {
            for (int c = 0; c < param.n; c++)
            {
                assert(param.result[r][c] == floyd.m_vMat[r][c]);
            }
        }
    }
}

其它

测试环境

win7 VS2019 C++17

源码及测试样例下载

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

doc文档下载

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

相关文章:

多源最短路径的原理及C++实现

时间复杂度 O(n3),n是端点数。 核心代码 template<class T, T INF 1000 * 1000 * 1000> class CNeiBoMat { public: CNeiBoMat(int n, const vector<vector<int>>& edges,bool bDirectfalse,bool b1Base false) { m_vMat.assign(n, vector<…...

JMeter性能测试

性能测试前言 老师开局一句话&#xff1a;性能测试和你会不会JMeter一点关系没有…… 作者坚持技多不压身的原则&#xff0c;还是多学一点JMeter吧&#xff0c;看老师到底要怎么讲下去&#xff0c;什么并发量、吞吐量啥的…… 性能测试的核心思想&#xff1a;在于创造大量并发去…...

Cocos Creator3.8 实战问题(四)巧用九宫格图像拉伸

一、为什么要使用九宫格图像拉伸 相信做过前端的同学都知道&#xff0c;ui &#xff08;图片&#xff09;资源对包体大小和内存都有非常直接的影响。 通常ui 资源都是图片&#xff0c;也是最占资源量的资源类型&#xff0c;游戏中的ui 资源还是人机交互的最重要的部分&#xff…...

Linux shell编程学习笔记7:只读变量

在编程过程中&#xff0c;我们经常会使用到一些常量&#xff0c;也就是值不需要改变的变量&#xff0c;在许多编程语言提供了常量的定义方式&#xff0c;比如c/c的define MAXNUM 99999 或 const int a 7&#xff0c;javasccipt的const a7&#xff0c; 等等。 跟以上这些方法…...

Scala第十七章节

Scala第十七章节 scala总目录 文档资料下载 章节目标 了解集合的相关概念掌握Traversable集合的用法掌握随机学生序列案例 1. 集合 1.1 概述 但凡了解过编程的人都知道程序 算法 数据结构这句话, 它是由著名的瑞士计算机科学家尼古拉斯沃斯提出来的, 而他也是1984年图灵…...

BGP高级特性——4字节AS号

目录 4字节AS号 相关概念 两种过渡属性 4字节AS号的格式 4字节AS号建立邻居 4字节AS号路由传递 配置命令 4字节AS号 相比于2字节AS号&#xff0c;范围更大。由1~65535扩展到1~4294967295 支持4字节AS号的BGP设备兼容仅支持2字节AS号的BGP设备 相关概念 Speaker&#…...

cesium源码无法更新的解决方案

一、环境&#xff1a; 中国移动的宽带 win10操作系统 二、问题复现步骤&#xff1a; 1、开了VPN&#xff0c;设置为全局代理 2、在vscode中执行git pull命令 3、结果显示无法更新 三、解决方案&#xff1a; 1、安装Github官方开发的软件Github Desktop 下载地址&#xf…...

大数据-玩转数据-双流JOIN

一、双流JOIN 在Flink中, 支持两种方式的流的Join: Window Join和Interval Join 二、Window Join 窗口join会join具有相同的key并且处于同一个窗口中的两个流的元素. 注意: 1.所有的窗口join都是 inner join, 意味着a流中的元素如果在b流中没有对应的, 则a流中这个元素就不会…...

from PIL import Image,文字成图,ImageFont import jieba分词,input优雅python绘制图片

开始的代码 import os from PIL import Image, ImageDraw, ImageFont import jiebadef generate_image_with_white_bg(text, font_path, output_path):# 设置图片大小和背景颜色image_width 800image_height 600bg_color (255, 255, 255) # 白色# 创建图片对象image Imag…...

渗透测试信息收集方法笔记

一、指纹识别 1、钟馗之眼https://www.zoomeye.org/ 2、天眼查https://www.tianyancha.com/ 3、工具&#xff1a;御剑WEB指纹识别系统正式版&#xff0c;可以查网站用了哪些框架&#xff0c;什么版本&#xff0c;有哪些漏洞 4、kali whatweb 二、信息泄露 1、csdn https://www.…...

协议栈——连接服务器

如对方的ip和port配置信息&#xff0c;这里的连接是指通信前的准备工作 上一篇介绍查看套接字的命令时&#xff0c;可以看到很多信息&#xff0c;但是刚刚创建出来的套接字是什么信息都没有的&#xff0c;协议栈也因此不知道和谁通信&#xff1b; 客户端填补信息 这一步中调…...

数据结构--队列与循环队列的实现

数据结构–队列的实现 1.队列的定义 比如有一个人叫做张三,这天他要去医院看病,看病时就需要先挂号,由于他来的比较晚,所以他的号码就比较大,来的比较早的号码就比较小,需要到就诊窗口从小号到大依次排队,前面的小号就诊结束之后,才会轮到大号来,小号每就诊完毕就销毁,每新来…...

数据结构—栈、队列、链表

一、栈 Stack&#xff08;存取O(1)&#xff09; 先进后出&#xff0c;进去123&#xff0c;出来321。 基于数组&#xff1a;最后一位为栈尾&#xff0c;用于取操作。 基于链表&#xff1a;第一位为栈尾&#xff0c;用于取操作。 1.1、数组栈 /*** 基于数组实现的顺序栈&#…...

2023年4月到7月工作经历

2023年4 有同事说程序崩溃一起分析得结果 unsigned uNum 2; std::string str "abc" uNum; std::cout << str; 结果是c 。如果uNum 很大的话&#xff0c;就可能崩溃。 unsigned uNum 2; //std::string str "abc" uN…...

嵌入式Linux应用开发-驱动大全-同步与互斥③

嵌入式Linux应用开发-驱动大全-同步与互斥③ 第一章 同步与互斥③1.4 Linux锁的介绍与使用1.4.1 锁的类型1.4.1.1 自旋锁1.4.1.2 睡眠锁 1.4.2 锁的内核函数1.4.2.1 自旋锁1.4.2.2 信号量1.4.2.3 互斥量1.4.2.4 semaphore和 mutex的区别 1.4.3 何时用何种锁1.4.4 内核抢占(pree…...

力扣-383.赎金信

Idea 使用一个hashmap 或者一个int数组存储第二次字符串中每一个字符及其出现的次数 遍历第一个字符串&#xff0c;讲出现的重复字符减1&#xff0c;若该字符次数已经为0&#xff0c;则返回false AC Code class Solution { public:bool canConstruct(string ransomNote, strin…...

计算机网络 第二章物理层

计算机网络第二章知识点速刷 其中重要的是信源和信宿&#xff0c;以及调制解调器在通信模型当中起到的作用。...

uniapp:动态修改页面标题

我们经常遇到这种情况&#xff0c;点击新增按钮&#xff0c;进入一个空白表单页面&#xff0c;点击修改按钮&#xff0c;其实也是进入这个表单页面&#xff0c;只是表单内容已经被数据库的记录反显了&#xff0c;为了区别页面&#xff0c;我们还需要动态设置页面的标题&#xf…...

java学生管理系统

一、项目概述 本学生管理系统旨在提供一个方便的界面&#xff0c;用于学校或机构管理学生信息&#xff0c;包括学生基本信息、课程成绩等。 二、系统架构 系统采用经典的三层架构&#xff0c;包括前端使用JavaSwing&#xff0c;后端采用Java Servlet&#xff0c;数据库使用M…...

Docker和容器化:简介和使用案例

Docker和容器化&#xff1a;简介和使用案例 引言 容器化技术在近年来变得越来越流行&#xff0c;为开发人员和运维团队提供了更加灵活、高效的软件部署和管理方式。其中&#xff0c;Docker是最为知名和广泛使用的容器化平台之一。本篇博客文章将介绍Docker和容器化的基本概念…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

SpringCloudGateway 自定义局部过滤器

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

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式

pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图&#xff0c;如果边框加在dom上面&#xff0c;pdf-lib导出svg的时候并不会导出边框&#xff0c;所以只能在echarts图上面加边框 grid的边框是在图里…...

简单介绍C++中 string与wstring

在C中&#xff0c;string和wstring是两种用于处理不同字符编码的字符串类型&#xff0c;分别基于char和wchar_t字符类型。以下是它们的详细说明和对比&#xff1a; 1. 基础定义 string 类型&#xff1a;std::string 字符类型&#xff1a;char&#xff08;通常为8位&#xff09…...