最短路径算法之燃线法

释永思

) q( G+ i, x9 \! Z$ \! c1 h
9 \- B8 O$ F. g# l

最短路径算法之燃线法

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

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

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

===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思
$ R3 B) k" g6 D6 @; h- M6 F! f

$ w. {0 P' z& q! W 最短路算法小软件EXE1.0.rar (1.1 MB, 下载次数: 8)

2016-3-28 08:22 上传

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

. x( }8 t$ j3 ^0 w8 K

0 a3 `; R: I. k5 O
! O2 e0 H) u* O& h1 \) a, k. {

释永思

  j3 s6 S4 k" g0 \2 g# q关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。
/ r5 `% c" _$ ~3 a4 Y可以把N个中途点排序，在所有排序中，求出最短路径。
至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。
, ?3 ^% o! w" T这是我偶然想到的算法。
  G8 M- O5 {- D; r- `. v
- p: i0 a9 d) `3 J5 l* h与哈密顿回路可能不同处在于可以重复顶点乎

其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。
/ R# ?. v+ Y2 ?$ P8 @5 u

＆中义

看看是什么东东，学意义
* A( Y, F$ k/ _

洪洞大槐树

不错，可以
9 K# v  H: q0 y

永久的平常心

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

释永思

永久的平常心 发表于 2016-4-13 10:35
8 {" u1 e; o- \5 q& W楼主，挺有想法，能把算法分享一下？？

- C1 L" l; k( C4 r, f0 M+ s算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：
+ @" u4 a7 x9 I5 c' {; I; u1 X设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
/ ~& V% z) X6 D: G. O# o