没有合适的资源?快使用搜索试试~ 我知道了~
数据结构重要算法整理.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 101 浏览量
2023-02-20
17:33:07
上传
评论
收藏 342KB DOCX 举报
温馨提示
试读
9页
。。。
资源推荐
资源详情
资源评论
最短路径
交通网络可以画成带权的图,图中顶点表示城市,边代表城市
路径上该点的前趋顶点,若从源点到该顶点无路径,则用 0 作为
其前一个顶点序号。
间的公路,边上的权表示公路的长度。对于这样的交通网络常常提
出这样的问题:两地之间是否有公路可通?在有几条路可通的情况
下,哪一条路最短?以上提出的问题就是在带权图中求最短路径问
题,此时路径的长度不是路径上边的数目,而是路径上的边所带权
值的总和。
(3)迪杰斯特拉算法
voi DijGraph::ShorttestPath_Dijkstra(int v)
{
//G 是一个具有 n 个顶点的带权有向图,求从源点 v 到其余各
顶点的最短路径长度
设 A 城到 B 城有一条公路, A 城的海拔高于 B 城,若考
虑到上坡和下坡的车速不同,则边 <A,B> 和边 <B,A> 上表示行
驶时间的权值也不同,即<A,B> 和 <B,A> 应该是两条不同的边,
考虑到交通网络的这种有向性,本节只讨论有向网络的最短路径问
题,并假定所有的权为非负实数。习惯上称路径开始顶点为源点,
路径的最后一个顶点为终点。
for(int i=0;i<n;i++)
//dist,path,S 的初始化
{ dist[i]=Edge[v][i];S[i]=0;
if(i!=v&&dist[i]<MAXNUM)path[i]=v;
else path[i]=-1;
//顶点 i 无前顶点
}
S[v]=1;
//顶点 v 加入已求出的最短路径的顶点集合
//求其余 n-1 个顶点的最短路径
1、最短路径定义
dist[v]=0;
for(i=0;i<n;i++
所谓最短路径问题是指:如果从图中某一顶点(源点)到达另
一顶点(终点)的路径可能不止一条,如何找到一条路径似的沿此
路径上各边的权值总和(称为路径长度)达到最小。
2、单源最短路径
{float min=MAXNUM;
int u=v;
for(int j=0;j<n;j++)
//选择当前不在集合 S 中具有最短路径的
单源最短路径问题:已知有向带权图(简称有向网)G=(V,E),找
出从某个源点 s∈V 到 V 中其余各顶点的最短路径。
迪杰斯特拉(Dijkstra)算法求单源最短路径
顶点 u
if(!S[j]&&dist[j]<min){u=j;min=dist[j];}
S[u]=1;
//顶点 u 加入到已求出最短路径的顶点集合
由 Dijkstra提出的一种按路径长度递增序产生各顶点最短路径
的算法。
for(int w=0;w<n;w++)
//修改期于顶点的当前最短路径
if(!S[w]&&Edge[u][w]<MAXNUM&&dist[u]+Edge[u][w]<dist[w])
(1)按路径长度递增序产生各顶点最短路径
{ dist[w]=dist[u]+Edge[u][w];
若按长度递增的次序生成从源点 s 到其它顶点的最短路径,则
当前正在生成的最短路径上除终点以外,其余顶点的最短路径均已
生成(将源点的最短路径看作是已生成的源点到其自身的长度为 0
的路径)。
path[w]=u;}
}
}
其他最短路径问题
最短路径问题的提法很多,其它的最短路径问题均可用单源
【例】在有向网 G8 中,假定以顶点 0 为源点,则它则其余各顶点
的最短路径按路径递增序排列如右表所示
最短路径算法予以解决:
(2)具体做法
① 单 目 标 最 短 路 径 问 题 (Single-Destination Shortest-Paths
Problem):找出图中每一顶点 v 到某指定顶点 u 的最短路径。只需
将图中每条边反向,就可将这一问题变为单源最短路径问题,单目
标 u 变为单源点 u。
一开始第一组只包括顶点 v 1 ,第二组包括其他所有顶点, v
1 对应的距离值为 0 ,第二组的顶点对应的距离值是这样确定的:
若图中有边 <v 1 , v j >, 则 v j 的距离为此边所带的权值,否则 v j
的距离值为一个很大的数 ( 大于所有顶点间的路径长度 ) ,然后
每次从第二组的顶点中选一个其距离值为最小的 v m 加入到第一
组中。每往第一组加入一个顶点 v m ,就要对第二组的各个顶点
的距离值进行一次修正。若加进 v m 做中间顶点,使从 v 1 到 v
j 的最短路径比不加 v m 的路径为短,则要修改 v j 的距离值。
修改后再选距离最小的顶点加入到第一组中。如此进行下去,直到
图中所有顶点都包括在第一组中,或再也没有可加入到第一组中的
顶点存在为止。
② 单 顶 点 对 间 最 短 路 径 问 题 (Single-Pair Shortest-Path
Problem):对于某对顶点 u 和 v,找出从 u 到 v 的一条最短路径。
显然,若解决了以 u 为源点的单源最短路径问题,则上述问题亦迎
刃而解。而且从数量级来说,两问题的时间复杂度相同。
③ 所 有 顶 点 对 间 最 短 路 径 问 题 (All-Pairs Shortest-Paths
Problem):对图中每对顶点 u 和 v,找出 u 到 v 的最短路径问题。
这一问题可用每个顶点作为源点调用一次单源最短路径问题算法
予以解决。
假设有向图 G 的 n 个顶点为 1 到 n, 并用邻接矩阵 cost
表示 , 若 < v i , v j > 是图 G 中的边,则 cost[i][j] 的值等于边所
带的权 ; 若 <v i , v j > 不是图 G 中的边,则 cost[i][j] 等于一个
很大的数;若 i=j, 则 cost[i][j]=0 。另外 , 设置三个数组 S[n] 、
dist[n] 、 pre[n] 。 S 用以标记那些已经找到最短路径的顶点,若
S[i-1]=1, 则表示已经找到源点到顶点 i 的最短路径 , 若 S[i-1]=0,
则表示从源点到顶点 i 的最短路径尚未求得。 dist[i-1] 用来记录
源点到顶点 i 的最短路径。 pre[i-1] 表示从源点到顶点 i 的最短
单链表的插入
(1)思想方法
插入操作大致分为如下三种:
①在已知 P 指针所指向的结点后插入一个元素 x。
②在 p 指针所指向的结点前插入一个元素 x。
③在线性表中值为 y 的元素插入一个值为 x 的数据元素。
大致算法思想:插入运算是将值为 x 的新结点插入到表的第
资源评论
xxpr_ybgg
- 粉丝: 6468
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于虚拟仿真环境下的自动驾驶交通标志识别python源码+文档说明+截图演示+数据集+使用教学(98分高分毕业设计)
- python实现的基于CNN深度学习网络的交通标志识别+源代码+文档说明+安装教程+使用教程(高分毕业设计)
- 基于Spring Bootd实现的图像去雾系统端,完成主要的前后端交互+源代码+文档说明
- 企业网站建设-PPT.ppt
- 办公自动化Microsoft-Office学习教程.doc
- 办公软件ECEL技巧培训课件-PPT.pptx
- 办公软件Word快捷键大全.doc
- Springboot集成SpringbootAdmin实现服务监控管理-源码
- 办公软件应用-计算机一级考试试题.doc
- 毕业设计-图像去雾,基于matlab实现的暗通道先验算法和Retinex图像增强算法制作的图形化界面程序仿真源码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功