算法设计与分析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，存在多少条路径？
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.蛮力/暴力/穷举/枚举◼列出所有可行...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
工程建设招标投标合同（附件）VIP免费
2024-11-15 16 -
工程建设招标投标合同（动员预付款银行保证书）VIP免费
2024-11-15 11 -
工程建设招标设标合同条件（第1部分）VIP免费
2024-11-15 11 -
工程建设招标设标合同合同条件（第3部分）VIP免费
2024-11-15 10 -
工程建设招标设标合同合同条件（第2部分）VIP免费
2024-11-15 13 -
工程建设监理委托合同VIP免费
2024-11-15 14 -
工程建设监理合同标准条件VIP免费
2024-11-15 11 -
工程技术资料目录VIP免费
2024-11-15 13 -
工程技术咨询服务合同VIP免费
2024-11-15 13 -
工程建设招标投标合同（投标邀请书）VIP免费
2024-11-15 35
分类：计算机
价格：5.9玖币
属性：108 页
大小：4.78MB
格式：PDF
时间：2025-01-13
渝公网安备50010702506394
