论多段图的最短路径问题(我认为本质上还是暴力枚举法)

简介: 本文讨论了多段图最短路径问题的解决方法,认为本质上是使用暴力枚举法,通过逐步计算每个阶段点的最短距离来确定从起点到终点的最短路径。

比如说这道题:我向前推进 从0到11的最短路径

按照图可以分5段,v1 是第一阶段 0,v2是第二段 有1,2,3,4

从0开始,路径为0,所以m(1,0)=0;

第二阶段的1点:m(2,1)=9, m(2,2)=7,m(2,3)=3,m(2,4)=2

第三段:第5点有两条路径,选最短的m(3,5)=min(4+m(2,1), 2+m(2,2))=9,然后依次:m(3,6)=min(2+m(2,1),7+m(2,2),11+m(2,4))=11,m(3,7)=min(1+m(2,1),11+m(2,3),8+m(2,4))=10

第四段:m(4,8)=min(6+m(3,5),4+m(3,6))=15 m(4,9)=min(5+m(3,5),3+m(3,6),5+m(3,7))=14

m(4,10)=6+m(3,7)=16

第五段:m(5,11)=min(4+m(4,8),2+m(4,9),5+m(4,10))=16

这样依次算出0到每个阶段各个点的最短距离,要是用程序实现就是简单的暴力枚举

目录
相关文章
|
12月前
|
机器学习/深度学习 人工智能 算法
时间复杂度O(40n*n)的C++算法:修改图中的边权
时间复杂度O(40n*n)的C++算法:修改图中的边权
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
5月前
【错题集-编程题】不相邻取数(动态规划 - 线性 dp)
【错题集-编程题】不相邻取数(动态规划 - 线性 dp)
|
5月前
|
机器学习/深度学习 算法 测试技术
【单源最短路 图论】882. 细分图中的可到达节点
【单源最短路 图论】882. 细分图中的可到达节点
|
5月前
|
算法 测试技术 C#
【树 图论 阶乘 组合 深度优先搜索】1916. 统计为蚁群构筑房间的不同顺序
【树 图论 阶乘 组合 深度优先搜索】1916. 统计为蚁群构筑房间的不同顺序
|
5月前
|
算法 测试技术 C#
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
|
5月前
|
机器学习/深度学习 存储 算法
C# | 凸包算法之Graham,快速找到一组点最外侧的凸多边形
这篇关于凸包算法的文章,本文使用C#和Graham算法来实现凸包算法。 首先消除两个最基本的问题: 什么是凸包呢? 凸包是一个包围一组点的凸多边形。凸多边形是指多边形中的每个内角都小于180度的多边形。 凸包算法有什么用呢? 凸包算法的作用是找到这个凸多边形,并且使用最少的点来绘制出它的轮廓。凸包算法在计算机图形学、计算几何和机器学习等领域中有着广泛的应用。
123 0
【数据结构】多段图最短路径
【数据结构】多段图最短路径
136 0
|
存储 算法
|
算法 定位技术 Perl