数学建模社区-数学中国
标题:
最短路径算法小软件V5.0
[打印本页]
作者:
释永思
时间:
2018-6-28 12:39
标题:
最短路径算法小软件V5.0
8 b/ W) O* y- }# {4 B7 Y% P! x8 \
百度百科：最短路径
4 e* I; a' L( p" g3 z- W
i/ K; B0 w9 S( [% `3 J3 W
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
% g3 h8 Q1 m6 p, y. w
中文名 最短路径
' o' I; Z$ r+ f- S l
特点 以起始点为中心向外层层扩展
. C/ w6 z% H. J- v
性质 一个经典算法问题
0 f+ y* {4 w' ^, j7 E: I8 z
解决方法 Dijkstra算法A*算法
+ A5 M- c* L# n' ^# U
; k; T! ]# e1 R; }% _( u
概述
3 c* y x2 |+ Q4 w8 T
- r0 o1 O( j( E. d- e3 [# V
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：
0 R' }# F% R8 x" S2 B8 |' R2 B
确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。
0 Q8 C# F0 t. c" S
确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
) Q+ M' ?7 f& V7 ~# i, b& l0 w0 _& m
确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
% D: N- x; X5 `" A2 l
全局最短路径问题 - 求图中所有的最短路径。
6 Q& ^6 U7 {5 L1 O
/ B! Z; R N+ J
////////////////////////////////////////////////////////////
; T a. `4 K! W/ u3 p
$ j$ W5 \9 y% L' q6 f
最短路径算法小软件V5.0
+ D3 d) B$ X! X2 `. C8 k q* p
2018年6月
6 I' p( u6 G0 Z4 B
作者：李庚子李丙寅（李均宇）
; a) a" \* N0 ?$ B' d3 X
QQ：165442523
# G9 `0 W( J5 ~9 c6 A+ X
EMail：
165442523@qq.com
/ L* Z5 D5 _9 G! Z$ a$ Q
http://www.okmyok.com/lisoft.htm
3 ~% Z1 C+ O+ ?- @- X# W9 ?% R T
, b% o8 K2 Y5 y2 K: m! I
下载地址：
1 G$ a4 n0 U9 I' |1 g. q. G
https://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg
! c4 i8 c4 g+ U+ {( x9 R2 g
2018-6-28 12:39 上传
下载附件
(245.32 KB)
K5 A# |4 R# k
: f4 _: q5 c2 c1 W
7 H( O. h. b. E. Z
2018-6-28 12:38 上传
下载附件
(235.45 KB)
& ~( Q! Z9 H+ C. `7 k
; u% U8 p9 I3 _) {( u# R# V7 q
0 C, k8 K4 i7 `' h$ M2 M1 y( m
最短路径算法小软件5.0EXE.zip
(3.38 MB, 下载次数: 1)
2018-6-28 12:38 上传
点击文件名下载附件
下载积分: 体力 -2 点
( q. ^! e/ z( B$ B3 v
& e" I# b; X& R0 R b
) e1 H% `) w- {( l$ v8 [8 n2 Q' x
2018-6-28 12:37 上传
下载附件
(287.62 KB)
& t* C6 m3 }- D7 H
2 C1 `$ q @7 ^
9 S! e1 \" N% t1 n V; I( X
) t% O8 A" r0 s+ h
5 H, w) D# q4 Y1 A; x3 T
( w: E5 Z9 |* p# f7 _
: I5 j0 d* x6 j( O7 b/ N) ^8 J- ^* M1 A
5 K: I7 Z" m4 P4 Z( g& @6 T
/ f5 e# b/ c: I' a
2 X% J! c1 N3 p# h& i; L
- z& ?5 C1 m0 m4 R1 H
& x( F; ~2 [4 ~# c* B, i% z; s
" r" M/ k' d' v$ h& W$ ^# S% N; z
$ ~* ]. C4 ^, u' t' [1 q$ b
. i0 V+ I& i" B
1.本软件为小软件，不想为项目管理花过多时间，例如要新增一个项目，又删除或修改一个项目等。
. \7 l8 h6 a: P$ f R
为此，本小软件只有两个默认的项目，一个为演示项目，一个用户当前正在使用的项目，不能增也不能减。
. Q. m( l# R( L
用户可以清空当前的用户项目，从而使用自已自定义的项目。先输入质点数等等。
; H* a! ^" R* H6 F1 _3 _
如果你要多个项目，可以COPY多个本软件所在文件夹使用。
" I% h2 q+ m6 S! `9 ~
2.初始化粗略质点坐标时，边长不作校验，例如，三角形两边长之和本应大于第三边，但是输入时三角形两边长之和小于第三边，将不作检验，所以请手工确保原始数据的正确性。
& j/ w& K5 T( l5 Y3 N$ H* {3 i$ Z& H/ @
3.质点坐标是屏幕像素坐标，left,top,纵坐标向下不是向上，与数学上的纵坐标方向相反。
5 i7 e- ~, k3 G8 D" ]) h
4.坐标为屏幕像素坐标，所以只能整数，边长为两位小数，如果四舍五入导致的出错不作处理。
0 T# k& x7 B3 }6 w7 e" i. N
5.注意，用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。
8 j; X# T7 q( E, M3 C
# U3 u" m! M# P" v2 P& ^4 x
% n8 o7 q% w8 l1 `1 k7 r6 S. `
本次升级到5.0主要修改如下：
( r" ?( \# E$ Z8 `; g( `
1。边线条改成灰色，当鼠标移到边线条时，高亮显示边与边长数字，这对于边长数字重叠时有用。
" `1 ?, ?# F& \
2。点坐标可以超出屏幕范围自动产生滚动行，但点坐标不可以为负数。
6 |( a% a: I! |0 J6 V
3。增加了SPFA算法，来处理边长为 0 或者负数的情况，但SPFA当有负环时无解。
' u# _2 ` L6 F7 }" c9 f
4。增加了处理负环的两个新算法，这两个算法皆为作者自创的新算法，一个点与边都不可以重复，另一个点可以重复，边不可以重复。
7 ~. s& ]. p: b/ Y
5。边长为负数时最好有方向单向，一般不允许双向或无向。或者每条双向无向的负数边，可以每次取单向，如此组合出所有情况，来求最短路径，再在所有最短路径中再取其最小值。这个组合的算法暂不处理，由用户手工处理。
2 l( R# G( g! v
- P0 V! C6 D0 V: U) J4 N
升级到4.0时主要修改如下：
}* U' U3 z& w8 c1 ~
1。更正了算法上的一个BUG。
0 A/ l1 e9 K/ R
2。边长由只可以为整数升级为可以为两位小数。
) d* b1 U: ^5 A4 u: Z
3。增加了可以保存运算结果，下次不用再运算的功能。
5 n8 q) c E8 }! d
4。增加了可以列举所有最短路径的功能，不止一条最短路径时有用。
/ t# q' I6 Z, E4 @2 e) ^
5。增加了边向量功能，边向量方向可以双向或无向，或序号从小指向大，或序号从大指向小，三种选择。
' q7 d3 c4 S8 z" [% m3 e. |' {
6。改正了设置起点和终点的小BUG，增加了进度条显示。
: U% @$ H% q( }/ C1 N6 P! }3 m: A
7。增加了可以鼠标拖动质点，所相关联的边相应变动的功能。
9 Q' H0 C$ c3 \6 f+ r8 U# `
/ l+ e" y7 r- Q7 z) M) W7 h* x
作者的个人网站：
http://www.okmyok.com/lisoft.htm
6 i6 |$ @5 [ B2 t; }1 A
上面有作者个人开发的所有软件，全免费下载。免费但不开源，源代码要收费。
! d( C( ^2 l' i( D2 f9 A
上面有作者个人开发的中医五运六气和子午流注软件，有PC电脑版，安卓版，ASP网页版等。
3 C3 F3 `% }8 z" ?' J
还有作者开发的“行星财务”安卓软件，是一款在安卓设备上运行的真正意义上的财务软件，不是记录个人收支的个人记账，在安卓手机上可以运行，掌上财务软件。
2 A4 \% e2 U \. h
还有作者开发的TSP算法小软件，或叫旅行商问题，不了解者可以百度。
. ^8 n$ [: V( F/ u5 G
还有作者开发的表达式求值的计算器，可以层层括号等等。。。
1 Y; W e% q: ]
5 Y9 H8 a: \; C9 i1 `) F/ b
我的软件全免费，无广告，无须权限，无须上网，无时间和任何功能限制，纯绿色不污染系统，不体积庞大。。。
1 D/ h: g q7 ^9 E
* I, K1 A; z4 j. I. @7 m4 c
. Z. \5 Y+ S7 z' y' p- a! N/ k
" s" C* p* N2 [* ~7 F+ |( b& o
. q* |, C D- E& u8 {7 S, ]
0 ~( u+ r! J1 C8 g
6 _6 i3 b$ _% b m2 l
5 D" V; c: m# C! H& U( _. e
$ ~8 M4 T% e& z0 G0 u3 a& i" D) g
4 Z0 r6 \, _: `. n
# f5 q) X2 v! t; m. }; U
# I4 X7 G+ D) H$ A
$ O/ R% }" L; ?
# Y1 g1 K1 }- {8 n0 N2 R7 M
' C" Z1 M! U4 ]. B5 H- T* `. |
8 ]9 h3 H9 `$ @8 N! C
3 r. W" W1 Z3 O: Z/ ~; x1 H" }% o
6 k$ z- O' \- B; a. }2 b6 I7 ~/ k
# Y4 Y7 g9 H- j- U& a1 x
v* |0 u/ ]$ A- v
1 x1 Z1 H) H2 H- a. e4 Z# u" c9 H; Q
) T5 k' y0 K3 N0 J1 x
' B$ z! m& W$ {: l' |
+ b3 h/ O/ t# P$ d
/ v4 d5 Y9 y8 h/ J
# r/ X4 w5 r7 V# O0 V
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
最短路径算法小软件5.0EXE.zip
(3.38 MB, 下载次数: 1)