最短路径算法之燃线法

释永思

7 Q, p- _- X/ r9 g, ?* h" b3 w
  L6 V/ f4 @& n9 c

最短路径算法之燃线法

( n" I: A8 `8 E% l! q4 m

最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。

设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。

以这样简单的思想为基础，作者开发成了小软件，截图如下：

===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思
2 s0 R0 t; g9 x
" R: b6 q4 ]6 P% J# Y
! a/ t# X3 |1 j0 h, O/ r 最短路算法小软件EXE1.0.rar (1.1 MB, 下载次数: 8)

2016-3-28 08:22 上传

点击文件名下载附件
下载积分: 体力 -2 点

7 M9 q3 X: H+ T; q) S

. n2 o/ K1 ]  m

释永思

8 c% N* M& C& Y5 g4 }6 F, H
1 o; j* o% m! }( z. _/ ?关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。
可以把N个中途点排序，在所有排序中，求出最短路径。
! ~2 |: v' F& V5 F: n5 K至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。
这是我偶然想到的算法。
$ F3 C7 S# m1 U1 O" g; n
3 {! X8 O0 _& Z( x. s与哈密顿回路可能不同处在于可以重复顶点乎
* v5 C1 n4 W3 b8 ?9 X1 C
2 ?: H; [0 f' ?% C/ O其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。
4 ^3 U1 I6 \3 \1 E  K

＆中义

看看是什么东东，学意义
! {3 y+ G) c. e  x' h! z

洪洞大槐树

不错，可以
0 O6 K) p( R9 F/ |2 f+ p

永久的平常心

楼主，挺有想法，能把算法分享一下？？

释永思

永久的平常心 发表于 2016-4-13 10:35
0 }( i1 R9 {) [8 X! F楼主，挺有想法，能把算法分享一下？？

算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。