最短路径算法小软件V5.0

释永思

. |0 {. h9 M9 n# T, ~7 h% ~* n9 z百度百科：最短路径

用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
中文名 最短路径
2 K- O2 P( d* r6 m特点 以起始点为中心向外层层扩展
+ L5 s6 p8 @% S4 G6 L" `7 `性质 一个经典算法问题
; N3 t, B2 Q. r, V4 J* v4 V9 ~% z% b解决方法 Dijkstra算法A*算法
. G- t! K  m5 K) g
4 z7 M  \6 }# i4 R) d: D概述
5 Y9 n& n  a- J- H1 _
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：
确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。
确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
8 r% m0 v( n. K) H$ ?& v: I/ l全局最短路径问题 - 求图中所有的最短路径。
8 k8 ~1 b4 d* P; D
////////////////////////////////////////////////////////////
) I- j' t7 r& @
最短路径算法小软件V5.0
& {, H; ^: C) V" m0 G" \0 H2018年6月
作者：李庚子李丙寅（李均宇）
3 `# E: ]2 ~, v1 F* kQQ：165442523
4 h  a) p& T0 R/ FEMail：165442523@qq.com  
http://www.okmyok.com/lisoft.htm
' K2 V( r- z5 e  R% m2 b
! t6 b3 L4 g* E$ x3 d5 }下载地址：
https://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg



" A) X; U7 h( T0 m
/ ~1 _; J0 a& c9 Y; A" Q

最短路径算法小软件5.0EXE.zip (3.38 MB, 下载次数: 1)

2018-6-28 12:38 上传

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

. R( _- O4 m0 [' y! O+ U8 l




  Q9 @  Y7 H, o9 s& D1 }; l. R+ f; ^: d# I
4 y& ?1 H9 }% Z& d" _

* [& v5 L7 U2 C
8 O- K4 u/ K1 v! J" \+ s: F$ W7 j






- I, E( a/ ^* c5 I: R; i1.本软件为小软件，不想为项目管理花过多时间，例如要新增一个项目，又删除或修改一个项目等。
4 R- @, v0 O. @为此，本小软件只有两个默认的项目，一个为演示项目，一个用户当前正在使用的项目，不能增也不能减。
用户可以清空当前的用户项目，从而使用自已自定义的项目。先输入质点数等等。
! x7 C% G* A7 n" U* w7 A如果你要多个项目，可以COPY多个本软件所在文件夹使用。
2.初始化粗略质点坐标时，边长不作校验，例如，三角形两边长之和本应大于第三边，但是输入时三角形两边长之和小于第三边，将不作检验，所以请手工确保原始数据的正确性。
3.质点坐标是屏幕像素坐标，left,top,纵坐标向下不是向上，与数学上的纵坐标方向相反。
4.坐标为屏幕像素坐标，所以只能整数，边长为两位小数，如果四舍五入导致的出错不作处理。
7 o/ ~- c( X  ?! P! H5.注意，用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。


  l1 o7 ]3 j7 f+ A本次升级到5.0主要修改如下：
4 @: R* x4 A, g2 f1。边线条改成灰色，当鼠标移到边线条时，高亮显示边与边长数字，这对于边长数字重叠时有用。
2。点坐标可以超出屏幕范围自动产生滚动行，但点坐标不可以为负数。
3 M  s. a9 X. \3 C6 K* V3。增加了SPFA算法，来处理边长为 0 或者负数的情况，但SPFA当有负环时无解。
/ B* j. o7 R: o1 O+ ^5 i4 p& V4。增加了处理负环的两个新算法，这两个算法皆为作者自创的新算法，一个点与边都不可以重复，另一个点可以重复，边不可以重复。
5。边长为负数时最好有方向单向，一般不允许双向或无向。或者每条双向无向的负数边，可以每次取单向，如此组合出所有情况，来求最短路径，再在所有最短路径中再取其最小值。这个组合的算法暂不处理，由用户手工处理。
8 C# k' O: F3 j2 e$ @$ U- a
. m2 c5 R4 U! I( D升级到4.0时主要修改如下：
: n. N& _) m6 Y- U. f9 A) h( o1。更正了算法上的一个BUG。
; D( m; J- ]* n* c  J" ]. k2。边长由只可以为整数升级为可以为两位小数。
3。增加了可以保存运算结果，下次不用再运算的功能。
5 Z5 |4 F) B' z3 P: ~/ E3 @4。增加了可以列举所有最短路径的功能，不止一条最短路径时有用。
" Q; t0 Y4 Q! E6 V+ @5。增加了边向量功能，边向量方向可以双向或无向，或序号从小指向大，或序号从大指向小，三种选择。
6。改正了设置起点和终点的小BUG，增加了进度条显示。
/ f+ u  i5 y' ?7。增加了可以鼠标拖动质点，所相关联的边相应变动的功能。
9 W8 j; n0 D2 C5 a
作者的个人网站：http://www.okmyok.com/lisoft.htm
) t/ H' i& ~& C6 j+ q; J2 j- X上面有作者个人开发的所有软件，全免费下载。免费但不开源，源代码要收费。
上面有作者个人开发的中医五运六气和子午流注软件，有PC电脑版，安卓版，ASP网页版等。
还有作者开发的“行星财务”安卓软件，是一款在安卓设备上运行的真正意义上的财务软件，不是记录个人收支的个人记账，在安卓手机上可以运行，掌上财务软件。
还有作者开发的TSP算法小软件，或叫旅行商问题，不了解者可以百度。
3 i& f- p' F# E; E7 ~还有作者开发的表达式求值的计算器，可以层层括号等等。。。
6 v1 N! ]. `: @6 A% f: s
% e  f& P0 I! R% d0 e- ?9 H% m我的软件全免费，无广告，无须权限，无须上网，无时间和任何功能限制，纯绿色不污染系统，不体积庞大。。。

! G/ U& I& w4 D! d1 }) d

. Z# D7 V3 A! ^$ ~

8 A! l  c* e! T1 [, A6 H# ~3 h# B$ G
0 ^; S- A8 o9 i& u& A. G

0 h  u/ I7 h8 ?* V2 Z0 D& P
* V0 T/ w3 i0 g4 H$ C. T" f# U
1 U7 f$ v% F3 p1 B3 ]$ w

7 Z6 r$ d! d9 ]) T0 ^. ^


) @0 ]! c& m  R4 f  P) r

4 g1 y# Y, w$ N  m% ]; N4 N

$ M  r1 D  v0 m. R/ k3 s
# U5 g" J, h" q* n5 v

* o2 M. o+ V" m9 g# O) {


2 {4 u& y9 O  n; g& n