算法设计与分析W10-最短路径202404

VIP免费
2025-01-13 3 0 4.78MB 108 页 5.9玖币
侵权投诉
算法设计与分析
最短路径问题的几种确定性解法
2024年 春季
给出一个线路网络， 从A点要铺设一条管
道到G点，其两点之间连线上的数字表示两点
间的距离；A和G之间存在多条线路（路径），
每条线路的长度是线路上各段（边）距离之和。
要求选择一条由A到G的铺管线路，使总距
离为最短。
单源最短路径问题描述
单源最短路径问题
约定：连通，有向无环图，非负权
AE2
D2
B2
B1
C4
C3
C2
C1
D3
D1E1
E3
F2
F1
G
3
3 6
6
2
5
5
3
3
4
3
2
1
2
2
3
3
5
3
8
6
6
3
1
4
8
5
7
6
8
单源最短路径问题的不同求解方法
1. 蛮力/暴力/穷举
2. 回溯
3. 分支定界
4. 动态规划
5. 贪心
注：本节不涉及分治法
1. 蛮力/暴力/穷举/枚举
◼列出所有可行的路径，计算其长度，选出长
度最短的路径
AE2
D2
B2
B1
C4
C3
C2
C1
D3
D1E1
E3
F2
F1
G
3
3 6
6
2
5
5
3
3
4
3
2
1
2
2
3
3
5
3
8
6
6
3
1
4
8
5
7
6
8
全排列
AE2
D2
B2
B1
C4
C3
C2
C1
D3
D1E1
E3
F2
F1
G
3
3 6
6
2
5
5
3
3
4
3
2
1
2
2
3
3
5
3
8
6
6
3
1
4
8
5
7
6
8
◼对n个顶点（或者除起始点之外的n-1个顶点）
生成全排列，每种排列对应一条可能的路径。
◼问题：从A到G，存在多少条路径？
◼源码(全排列)
◼时间复杂度
◼空间复杂度
AE2
D2
B2
B1
C4
C3
C2
C1
D3
D1E1
E3
F2
F1
G
3
3 6
6
2
5
5
3
3
4
3
2
1
2
2
3
3
5
3
8
6
6
3
1
4
8
5
7
6
8
A
B1B2
C1C2C3C2C3C4
D1D2D1D2D2D3D1D2D2D3D2D3
……
E1E2E2E3
F1F2
GG
……
……
针对该图：实际上共有2 * 3 * 2 * 2 * 2 * 1=48
条路线，对应一棵有48个叶子节点的状态空间树。
状态空间树
可以在状态空间树上进行搜索
（深度优先或广度优先搜索）。
图的广度优先搜索
◼用广度优先法搜索有向图（使用队列）， 逻辑
上动态构造“状态空间树”+ 在状态空间树中搜索
AE2
D2
B2
B1
C4
C3
C2
C1
D3
D1E1
E3
F2
F1
G
3
3 6
6
2
5
5
3
3
4
3
2
1
2
2
3
3
5
3
8
6
6
3
1
4
8
5
7
6
8
允许顶点被多次访问，从而可以穷尽所有路径；过程中
计算每条路径的长度
与图的遍历的不同点：图的遍历中，每个顶点只被访问一次，而此处则
允许顶点被多次访问。
可能存在多条
路径经过顶点V
◼记录最短路径长度dist = ∞
◼源点加入队列
◼依次从队列中取出一个顶点u
⚫处理该顶点的每个邻居顶点v，计算v的路径长度(经过
u的当前这条路径)。
⚫将v (以及相应的路径信息)加入队列
⚫若v为目的节点，且路径长度小于dist，则更新dist
◼重复以上过程，直到队列为空
注：广度优先较晚获得可行解
可以改成一维数组dist[N]:
dist[v]表示源点至v的已知最短路径长度
摘要：

算法设计与分析最短路径问题的几种确定性解法2024年春季给出一个线路网络，从A点要铺设一条管道到G点，其两点之间连线上的数字表示两点间的距离；A和G之间存在多条线路（路径），每条线路的长度是线路上各段（边）距离之和。要求选择一条由A到G的铺管线路，使总距离为最短。单源最短路径问题描述单源最短路径问题约定：连通，有向无环图，非负权AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768单源最短路径问题的不同求解方法1.蛮力/暴力/穷举2.回溯3.分支定界4.动态规划5.贪心注：本节不涉及分治法1.蛮力/暴力/穷举/枚举◼列出所有可行...

展开>> 收起<<
算法设计与分析W10-最短路径202404.pdf

共108页,预览22页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：计算机 价格：5.9玖币 属性：108 页 大小：4.78MB 格式：PDF 时间：2025-01-13

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

高考理综 人际关系 力的合成 配电装置 动力学连接体 全宋诗作者索引 公务员考试
/ 108
评分 收藏
分享
立即下载 VIP免费下载
客服
关注