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

图论——最短路算法

 引入:

如上图,已知图G。

问节点1到节点3的最短距离。

可心算而出为d[1,2]+d[2,3]=1+1=2,比d[1,3]要小。

求最短路径算法:

1.Floyd(弗洛伊德)

是一种基于三角形不等式的多源最短路径算法。边权可以为负数

表现为a[i,j]+a[j,k]<a[i,k]。

算法思想:

枚举“中转站”(k),“起点”(i),“终点”(j)

设d[i,j]为由i点到j点的最短路径

则 d[i,j]=min(d[i,j],d[i,k]+d[k,j])

初始化d[i,j]为无穷大 (1\leq i\leq n,1\leq j\leq n

算法模板如下:
 

inline int Floyd(int n,int st,int ed)// n个点,起点st,终点ed,返回st到ed的最短距离
{int d[n][n];memset(d,0x3f,sizeof(d));for(int i=1;i<=n;i++) d[i][i]=0;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}return d[st][ed];
}

 补充:Floyd输出最短路径。

题目:有向图中任意两点最短路径(floyd)

题目描述

  一个含n个结点的有向图(注意:是有向图!!),以矩阵存储方式给出,请求出指定的多组两个点之间的最短距离及其最短路径。

输入输出格式
输入格式:

  第1行,一个整数n(0 < n < 300 ),表示有向图中结点的个数。
  第2行到第(n+1)行,是一个n*n的矩阵,表示无向图中各结点之间的联结情况,矩阵中的数据为小于1000的正整数,其中 -1 表示无穷大!!
  第(n+2)行,一个整数m,表示接下来有m组顶点 < i , j >对 ,其中,i是起点,j是终点,且i不等于j。
  接下来有m行,每行两个整数,中间一个空格间隔,分别表示i和j,表示求解i点到j点的最短距离及最短路径。

  注:输入数据已经确保答案每一组顶点间的最短路径是唯一的,无多解数据存在,顶点编号用数字表示,从1开始编号,至n结束!

输出格式:

  共 2m 行。
  第(m-1)*2+1行,一个整数,表示第m组顶点的最短距离,若两点间距离为无穷大,则输出 -1。
  第(m-1)*2+2行,用顶点编号表示的路径序列,各顶点编号间用一个空格间隔,表示第m组顶点的最短路径,若两点间距离为无穷大,则输出的路径序列为 -1。

输入输出样例
输入样例#1:

3
0 4 11
6 0 2
3 -1 0
2
2 1
3 2 

输出样例#1:

5
2 3 1
7
3 1 2

代码如下:
 

#include<bits/stdc++.h>
using namespace std;
int n,q;
int d[10001][10001],pre[10001][10001];
void dg(int i,int j)
{if(i==j||pre[i][j]==0) return;int k=pre[i][j];dg(i,k);dg(k,j);
}
int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>d[i][j];if(d[i][j]==-1){d[i][j]=0x7fffff;}}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(d[i][k]+d[k][j]<d[i][j]){d[i][j]=d[i][k]+d[k][j];pre[i][j]=k;}}}}cin>>q;for(int i=1;i<=q;i++){int x,y;cin>>x>>y;cout<<d[x][y]<<endl;cout<<x<<" ";dg(x,y);cout<<y;cout<<endl;}return 0;
}

传递闭包(连通性)

d[i,j]=d[i,j]|(d[i,k]&d[k,j])
d[i,j]表示i与j是否连通。

题目:刻录光盘

题目描述

  在FJOI2010夏令营快要结束的时候,很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家,以便大家回去后继续学习。组委会觉得这个主意不错!可是组委会一时没有足够的空光盘,没法保证每个人都能拿到刻录上资料的光盘,怎么办呢?!

  DYJ分析了一下所有营员的地域关系,发现有些营员是一个城市的,其实他们只需要一张就可以了,因为一个人拿到光盘后,其他人可以带着U盘之类的东西去拷贝啊!

  他们愿意某一些人到他那儿拷贝资料,当然也可能不愿意让另外一些人到他那儿拷贝资料,这与我们FJOI宣扬的团队合作精神格格不入!!!

  现在假设总共有N个营员(2<=N<=200),每个营员的编号为1~N。DYJ给每个人发了一张调查表,让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然,如果A愿意把资料拷贝给B,而B又愿意把资料拷贝给C,则一旦A获得了资料,则B,C都会获得资料。

  现在,请你编写一个程序,根据回收上来的调查表,帮助DYJ计算出组委会至少要刻录多少张光盘,才能保证所有营员回去后都能得到夏令营资料?

输入输出格式

输入格式:

先是一个数N,接下来的N行,分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号,以一个0结束。如果一个营员不愿意拷贝资料给任何人,则相应的行只有1个0,一行中的若干数之间用一个空格隔开。

输出格式:

一个正整数,表示最少要刻录的光盘数。

输入输出样例

输入样例#1:

5
2 4 3 0
4 5 0
0
0
1 0

输出样例#1:

1

代码:

#include<bits/stdc++.h>
using namespace std;
int f[100001],d[300][300],g[100001],ans;
int main()
{int n;cin>>n;memset(d,0x3f,sizeof(d));for(int i=1;i<=n;i++){f[i]=i;}for(int i=1;i<=n;i++){int x;while(1){cin>>x;if(x==0) break;d[i][x]=1;}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j&&j!=k&&k!=i){if(d[i][k]==1&&d[k][j]==1){d[i][j]=1;}}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(d[i][j]==1){f[j]=f[i];}}}for(int i=1;i<=n;i++) {if(f[i]==i) {ans++;}}cout<<ans;return 0;
} 

2.dijkstra(狄克斯特拉,迪杰斯特拉)

基于贪心的单源最短路径算法。边权必须为正数

基本思想:

设d[i]为起点s到终点i的最短路径,a[i,j]为点i到点j边权。

1.找  min\begin{Bmatrix} d[i] \end{Bmatrix}\left ( 1\leqslant i\leqslant n ,vis[i]=true \right ),并将其用k记录

2.vis[k]=true

3.d[i]=min\begin{Bmatrix} d[i],d[k]+a[k][i] \end{Bmatrix}\left ( 1\leqslant i\leqslant n \right ) 松弛操作,用k来更新图中所有点。

int dijkstra(int n,int st,int ed)
{int dis[n+1],vis[n+1];memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[st]=0;for(int i=1;i<=n;i++){int k,minn=0x7fffff;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]<minn) minn=dis[j],k=j;vis[k]=true;for(int j=1;j<=n;j++) d[j]=min(d[j],d[k]+a[k][j]);}return d[ed];
}

堆优化dijkstra:
 

typedef pair<int,int> P;
struct node{int to;int next;int w;
}edge[10000010];
int head[10000010],d[10000010];
int cnt;
int n,m,x,y,z,s;
void add_edge(int u,int v,int w)
{edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
void dijkstra(int s)
{priority_queue< P,vector<P>,greater<P> >q;memset(d,0x3f,sizeof(d));d[s]=0;q.push(P(0,s));while(!q.empty()){P p=q.top();q.pop();int u=p.second;if(d[u]<p.first) continue;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(d[v]>d[u]+edge[i].w){d[v]=d[u]+edge[i].w;q.push(P(d[v],v));}}}
}

3.Bellman-Ford

O(n*m) 但有更优的,由其转换而来的Spfa算法,不再赘述。边权可以为负数

4.Spfa

基于bellman-Ford,用队列优化的单源最短路径算法,边权可以为负数,可用于判断负环。

代码如下:

    int head=0,tail=1;team[1]=s,vis[s]=1,dis[s]=0;while(head<tail){head=(head+1)%10000;int u=team[head];vis[u]=0;for(int i=1;i<=len[u];i++){int v=le[u][i];if(dis[v]>dis[u]+a[u][v]){dis[v]=dis[u]+a[u][v];if(vis[v]==0){tail=(tail+1)%10000;team[tail]=v;vis[v]=1;}}}}

相关文章:

图论——最短路算法

引入&#xff1a; 如上图&#xff0c;已知图G。 问节点1到节点3的最短距离。 可心算而出为d[1,2]d[2,3]112,比d[1,3]要小。 求最短路径算法&#xff1a; 1.Floyd(弗洛伊德) 是一种基于三角形不等式的多源最短路径算法。边权可以为负数 表现为a[i,j]a[j,k]<a[i,k]。 …...

在项目中增加网络加载需要考虑什么?

1、下载器 网络加载的第一步肯定是下载&#xff0c;那么选择一个合适的下载器是十分重要的&#xff0c;这个下载器最好支持什么功能&#xff1f; 多线程下载&#xff08;同时需要服务端支持&#xff0c;下载时可指定range&#xff09; 断点续传 通用性&#xff08;其他位置也…...

阿里云服务器部署RabbitMQ流程

阿里云百科分享使用阿里云服务器部署RabbitMQ流程&#xff0c;RabbitMQ是实现了高级消息队列协议&#xff08;AMQP&#xff09;的开源消息代理软件&#xff0c;用于在分布式系统中存储转发消息&#xff0c;有良好的易用性、扩展性和高可用性。本文介绍如何通过ECS实例部署Rabbi…...

青大数据结构【2014】

一、单选 二、简答 为了解决顺序队列的假溢出问题&#xff0c;提出了循环队列&#xff0c;即把存储队列的表从逻辑上看成一个环 判别队列空和满有三种方法&#xff1a; 1&#xff09;采用计数器判别&#xff0c;空时&#xff0c;计数器为0&#xff1b;满时&#xff0c;计数器…...

Ansible Playbook快速部署一主多从MySQL集群

部署目标&#xff1a; 1、快速部署一套一主两从的mysql集群 2、部署过程中支持交互式定义安装目录及监听端口号 部署清单目录结构&#xff1a; rootmaster:/opt/mysql# tree . . ├── group_vars │ └── all.yml ├── hosts ├── mysql.yml └── roles└── mys…...

27.Netty源码之FastThreadLocal

highlight: arduino-light FastThreadLocal FastThreadLocal 的实现与 ThreadLocal 非常类似&#xff0c;Netty 为 FastThreadLocal 量身打造了 FastThreadLocalThread 和 InternalThreadLocalMap 两个重要的类。下面我们看下这两个类是如何实现的。 FastThreadLocalThread 是对…...

linux下离线安装docker

linux下离线安装docker 一、安装docker Docker 官网离线安装文档 https://docs.docker.com/engine/install/binaries/ 整理步骤如下&#xff1a; 官网下载 docker 安装包&#xff0c;地址为 https://download.docker.com/linux/static/stable/&#xff0c;如果是x86就选择x…...

SQL server 异地备份数据库

异地备份数据库 1.备份服务器中设置共享文件夹 2.源服务器数据库中添加异地备份代理作业 EXEC sp_configure show advanced options, 1;RECONFIGURE; EXEC sp_configure xp_cmdshell, 1;RECONFIGURE; declare machine nvarchar(50) 192.168.11.10 --服务器IP declare pa…...

高并发系统设计要点

在系统设计时&#xff0c;如果能预先看到一些问题&#xff0c;并在设计层面提前解决&#xff0c;就会给后期的开发带来很大的便捷。相反&#xff0c;有缺陷的架构设计可能会导致后期的开发工作十分艰难&#xff0c;甚至会造成“推倒重来”的情形。因此&#xff0c;在系统设计阶…...

Redis 拒绝服务漏洞(CVE-2023-28856)修复处理

一、漏洞描述 Redis Labs Redis是美国Redis Labs公司的一套开源的使用ANSI C编写、支持网络、可基于内存亦可持久化的日志型、键值&#xff08;Key-Value&#xff09;存储数据库&#xff0c;并提供多种语言的API。 Redis 7.0.0 到 7.0.10版本、6.2.0 到 6.2.11版本、6.0.0 到 …...

Android保存网页的方法

首先要使用js交互就需要懂原理&#xff1a; 感谢大佬&#xff1a;js中document节点获取页面元素的六种方式 1.querySelector()方法 描述&#xff1a;本方法用于根据给定的选择器选中页面元素 如果有多个元素满足条件&#xff0c;则返回第一个满足条件的元素节点 语法&#xff…...

P2P 网络,PING程序。

没有废话,直接上版本号和代码,以及讲解。 crate版本号libp2p0.52.1tokio1.30.0依赖配置: [dependencies] tokio = { version="1.30.0", features=["full"] } libp2p = { version="0.52.1", features=["tokio","dns", &q…...

OPENCV C++(十二)模板匹配

正常模板匹配函数 matchTemplate(img, templatee, resultMat, 0);//模板匹配 这里0代表的是方法&#xff0c;一般默认为0就ok img是输入图像 templatee是模板 resultmat是输出 1、cv::TM_SQDIFF&#xff1a;该方法使用平方差进行匹配&#xff0c;因此最佳的匹配结果在结果为…...

【配置环境】Linux下安装MySQL

目录 一&#xff0c;环境 二&#xff0c;安装步骤 1.使用包管理器安装MySQL 2.配置MySQL的安全选项 3.设置root用户使用密码进行身份验证&#xff08;可选&#xff09; 三&#xff0c;拓展知识 1.如何修改MySQL的密码策略&#xff1f; 一&#xff0c;环境 VMware Workst…...

【100天精通python】Day30:使用python操作数据库_数据库基础入门

专栏导读 专栏订阅地址&#xff1a;https://blog.csdn.net/qq_35831906/category_12375510.html 1 数据库基础知识介绍 1.1 什么是数据库&#xff1f; 数据库是一个结构化存储和组织数据的集合&#xff0c;它可以被有效地访问、管理和更新。数据库的目的是为了提供一种可靠的…...

android 如何分析应用的内存(十八)终章——使用Perfetto查看内存与调用栈之间的泄露

android 如何分析应用的内存&#xff08;十八&#xff09; 在前面两篇文章中&#xff0c;先是介绍了如何用AS查看Android的堆内存&#xff0c;然后介绍了使用MAT查看 Android的堆内存。AS能够满足基本的内存分析需求&#xff0c;但是无法进行多个堆的综合比较&#xff0c;因此…...

arcpy实现kml批量转出为shp 包括shp合并

参考文章 arcpy实现 kml批量转出为shp_kml批量合并转shp_A873054267的博客-CSDN博客 参考帮助是arcgis里边自带的KMLToLayer_conversion函数 应用场景&#xff1a; 两步路产生的多个轨迹文件KML&#xff0c;批量转换成arcgis 的gdb数据库 最后合并成一个shp 第一步&#…...

高等数学:泰勒公式

注&#xff1a;第三条 e x e^x ex的展开式&#xff0c;在 1 1 1和 1 2 x 2 \frac{1}{2}x^2 21​x2之间添上一个 x x x。 1 1 − x ∑ n 0 ∞ x n 1 x x 2 x 3 ο ( x 3 ) , x ∈ ( − 1 , 1 ) . \begin{aligned}\frac{1}{1-x}\sum_{n0}^\infty x^n1xx^2x^3\omicron(x^…...

JZ32 从上往下打印二叉树(Java)

题目地址&#xff1a;从上往下打印二叉树_牛客题霸_牛客网 题目回顾&#xff1a; 不分行从上往下打印出二叉树的每个节点&#xff0c;同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}&#xff0c;如以下图中的示例二叉树&#xff0c;则依次打印8,6,10,2,1(空节点不打印&…...

hackNos靶机

靶机训练1 - hackNos: Os-hackNos 靶机平台 Vulnhub 是一个提供各种漏洞环境的靶场平台&#xff0c;供安全爱好者学习使用&#xff0c;大部分环境是做好的虚拟机镜像文件&#xff0c;镜像预先设计了多种漏洞&#xff0c;需要使用VMware或者VirtualBox运行。每个镜像会有破解的目…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

对象回调初步研究

_OBJECT_TYPE结构分析 在介绍什么是对象回调前&#xff0c;首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例&#xff0c;用_OBJECT_TYPE这个结构来解析它&#xff0c;0x80处就是今天要介绍的回调链表&#xff0c;但是先不着急&#xff0c;先把目光…...

python基础语法Ⅰ

python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器&#xff0c;来进行一些算术…...