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

VIP免费

2025-01-13 3 0 4.78MB 108 页 5.9玖币

侵权投诉

算法设计与分析

最短路径问题的几种确定性解法

2024年春季

给出一个线路网络，从A点要铺设一条管

道到G点，其两点之间连线上的数字表示两点

间的距离；A和G之间存在多条线路（路径），

每条线路的长度是线路上各段（边）距离之和。

要求选择一条由A到G的铺管线路，使总距

离为最短。

单源最短路径问题描述

单源最短路径问题

约定：连通，有向无环图，非负权

AE2

D1E1

3 6

单源最短路径问题的不同求解方法

1. 蛮力/暴力/穷举

2. 回溯

3. 分支定界

4. 动态规划

5. 贪心

注：本节不涉及分治法

1. 蛮力/暴力/穷举/枚举

◼列出所有可行的路径，计算其长度，选出长

度最短的路径

AE2

D1E1

3 6

全排列

AE2

D1E1

3 6

◼对n个顶点（或者除起始点之外的n-1个顶点）

生成全排列，每种排列对应一条可能的路径。

◼问题：从A到G，存在多少条路径？

◼源码(全排列)

◼时间复杂度

◼空间复杂度

AE2

D1E1

3 6

B1B2

C1C2C3C2C3C4

D1D2D1D2D2D3D1D2D2D3D2D3

……

E1E2E2E3

F1F2

……

针对该图：实际上共有2 * 3 * 2 * 2 * 2 * 1=48

条路线，对应一棵有48个叶子节点的状态空间树。

状态空间树

可以在状态空间树上进行搜索

（深度优先或广度优先搜索）。

图的广度优先搜索

◼用广度优先法搜索有向图（使用队列），逻辑

上动态构造“状态空间树”+ 在状态空间树中搜索

AE2

D1E1

3 6

允许顶点被多次访问，从而可以穷尽所有路径；过程中

计算每条路径的长度

与图的遍历的不同点：图的遍历中，每个顶点只被访问一次，而此处则

允许顶点被多次访问。

可能存在多条

路径经过顶点V

◼记录最短路径长度dist = ∞

◼源点加入队列

◼依次从队列中取出一个顶点u

⚫处理该顶点的每个邻居顶点v，计算v的路径长度(经过

u的当前这条路径)。

⚫将v (以及相应的路径信息)加入队列

⚫若v为目的节点，且路径长度小于dist，则更新dist

◼重复以上过程，直到队列为空

注：广度优先较晚获得可行解

可以改成一维数组dist[N]:

dist[v]表示源点至v的已知最短路径长度

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

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

展开>> 收起<<

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

共108页,预览22页

还剩页未读，继续阅读

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

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: