最短路径算法之燃线法

释永思

% O# v0 \, ]4 Y( p# n: n/ f
. P1 @1 r, o9 Q0 z0 _& I

最短路径算法之燃线法

+ S* z8 t2 u7 |& y7 T0 ?2 ~9 W

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

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

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

===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思

) u! e6 E- `+ n$ a  u2 w
1 Y, Z$ D% \6 {( K  ?. } 最短路算法小软件EXE1.0.rar (1.1 MB, 下载次数: 8)

2016-3-28 08:22 上传

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

. U, P# W% x$ F: f1 C1 ]


- R) s$ h) E0 I0 A. |* M" e8 c

释永思

/ o* |( F8 `& l4 Z9 o6 k: u
) Y" d5 K4 F* N- L& ?: ]关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。
# c1 K- |" [$ {( q9 r. p+ L- Q9 b可以把N个中途点排序，在所有排序中，求出最短路径。
9 K: \  H) `! f7 d0 [至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。
6 ]+ S; r; c% J' q这是我偶然想到的算法。
3 Z- c9 t; g! b- B# r
与哈密顿回路可能不同处在于可以重复顶点乎

其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。

＆中义

看看是什么东东，学意义

洪洞大槐树

不错，可以
4 L. H1 s8 \% U; k) K

永久的平常心

1 y; O( ^6 w! v& ?/ g; a楼主，挺有想法，能把算法分享一下？？
" g9 @; K' R- {# _

释永思

永久的平常心 发表于 2016-4-13 10:35
/ B4 q/ [5 P) |8 L9 T楼主，挺有想法，能把算法分享一下？？

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