- 在线时间
- 138 小时
- 最后登录
- 2018-11-1
- 注册时间
- 2015-8-26
- 听众数
- 13
- 收听数
- 0
- 能力
- 0 分
- 体力
- 366 点
- 威望
- 0 点
- 阅读权限
- 30
- 积分
- 146
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 70
- 主题
- 23
- 精华
- 0
- 分享
- 0
- 好友
- 17
升级   23% TA的每日心情 | 难过 2016-5-14 14:04 |
|---|
签到天数: 18 天 [LV.4]偶尔看看III
- 自我介绍
- 软件开发工程师
 |
! G, t1 y2 z! Z2 E
百度百科:最短路径
" k; |! h2 p( s1 e p! C2 l& H- J. i4 X3 c
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 G; H! Q; P( Q
中文名 最短路径
. Y+ v* P- n5 N a6 T. [" G特点 以起始点为中心向外层层扩展
( C. y$ G3 G% g4 c2 B- @性质 一个经典算法问题
% N" V& g* B3 H解决方法 Dijkstra算法A*算法
" ]& y/ d" N! `+ V8 x+ C: k X* X0 o2 r+ J+ V }/ c' w. `1 }
概述" }' K+ U/ r$ y. u$ p5 [
" d; R+ B# D* H% D- X4 T0 r8 |7 N最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:
4 b$ E! C# `1 d确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。
6 [ m5 s, \. r确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
$ p$ R2 b+ r6 R; a5 w' N8 ~确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。# @: w7 u, s' P5 Z: T- E0 n4 [6 v
全局最短路径问题 - 求图中所有的最短路径。+ p$ N8 e; g6 }9 M/ d* W0 V$ b- ]
8 o8 `3 f8 ~' ~( N1 W3 t; j; V# Z
////////////////////////////////////////////////////////////) ?/ \& ~# V( B, a
: l6 A" \! C0 m" t0 b最短路径算法小软件V5.00 H- [& r6 c8 }3 i! s4 d
2018年6月
6 d: V6 U9 `) O6 Z0 j; p) g$ ?作者:李庚子李丙寅(李均宇). P9 s3 M/ y; H! G$ S, _, Y
QQ:165442523 * v# u, @: h. o; K# ~3 q
EMail:165442523@qq.com
* W, z+ ?% r' `) L c- g; S8 M4 Zhttp://www.okmyok.com/lisoft.htm1 }; y2 r p+ I7 ^% l
9 [, _$ r3 f5 y) K( ?9 w; }# }下载地址:
. {$ b. _5 e0 o- thttps://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg( S. ~' ?, Y0 Z
' v" ^( P1 O% G: x! k( L) j) l4 V' r' j; S( i7 U0 W
( E5 q% d& {! R0 B0 Q2 _5 G/ | F5 f
) W4 y/ J4 B& d: y9 m( Z3 Y: A
( n; r0 k% W" G/ [
7 y5 {5 `6 v- E* o
最短路径算法小软件5.0EXE.zip
(3.38 MB, 下载次数: 1)
1 o2 E3 c! n+ ^" n% b, g/ ^& ^* y+ {' h- T7 y
+ u9 }4 Q2 b4 t4 g$ A( a
0 w. ]5 w2 ~" s3 m
+ ~, G7 W, o+ d, a" S+ A
$ `( z$ o! j7 Z% R9 V* r: O( l7 h
1 b( e1 p4 W! `, h0 A8 _
0 s# ~1 J2 A7 I0 o" Z6 R0 F( J, h1 a
0 `; q' T( d1 O) c
J8 g, J+ r. o- n) X6 l- V! [
1 s3 b. |! p" J! K% V9 B0 d, e+ l; m# \
8 Q( S y$ g* ?1 p5 N9 L
4 O# W( p* H8 g$ N a3 o( E
- K3 z: |0 ]: e% F9 L [- F8 s/ g: Q# R% e* K, Y
1 }1 m/ F0 c4 Q: _0 {# z+ N
1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。
+ f* }" F; ~/ \ O为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。4 _7 F% ?% q: t
用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。
6 m7 e2 \2 B+ P如果你要多个项目,可以COPY多个本软件所在文件夹使用。- a# I- H- Y/ B2 u9 j
2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。& R; x* z3 G% `, X" ?. ?
3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。# w: j; x6 P* A* s' U
4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。' [% e5 U, Y! `9 A1 C
5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。- J; h4 e! R% O9 v
. ?# I) i: j2 T, e) Z- V) S% e' e
本次升级到5.0主要修改如下:. x1 { E+ X$ t1 v5 ^
1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。
$ [0 q4 L" n, q. X4 B& x6 o2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。
7 A6 j! R- K( ]" |3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。
* ?# n* Y n$ S- S% W9 \4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。; F. P7 H. P5 u) ~! f' ?( \! ?; J
5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。! \' F9 _# h. m+ q+ \2 L
* K9 w: o* G) C Q4 v2 X
升级到4.0时主要修改如下:3 v$ O2 C& y) l
1。更正了算法上的一个BUG。
( w0 r: d6 O$ P9 a2。边长由只可以为整数升级为可以为两位小数。2 T9 l4 r7 s2 c# I
3。增加了可以保存运算结果,下次不用再运算的功能。
; q5 _0 g) q6 k4 R) S) R4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。9 i; _; A' Y( b- p& S! m
5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。
( C. M1 q. \" v$ {+ i6。改正了设置起点和终点的小BUG,增加了进度条显示。
$ F9 a) [! ~( [7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。( \; J/ \6 V. ?# n- }
- o: N; {% `+ u) V/ f$ S0 j
作者的个人网站:http://www.okmyok.com/lisoft.htm( G" D6 L0 t6 [1 |3 R f/ f. V# v
上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。
3 f k$ Q5 ]" t5 N* q" |上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。5 @6 n) _& K) a9 t0 p2 n1 t
还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。* @) V* Q) P) o" w5 u& R
还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。
( j2 E+ `7 a5 v9 h还有作者开发的表达式求值的计算器,可以层层括号等等。。。
* F1 v1 S F. \% L& Q# t0 y4 N0 U, p( [5 B& P) {$ \, x& q& W
我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。4 I2 L: q3 s) K2 J* |9 `& n
% V! g3 H8 S" J% {; }) l
6 f, z! o# I- c: J+ N2 O1 Y! N
' J+ x" Q+ ~' x7 X% ?. J
+ z' a: e3 d" g2 v
( J9 S4 ^. F& G( ]
6 S6 h: M& T4 A. M( _: F% j2 u. ?& y9 X# u
9 u! o' @, O$ y/ \3 q' R1 P' A' ?& J) B* o$ n% u! Q
t1 J+ G9 z2 I4 s2 |
' v) u4 m5 d2 D8 m
B* m7 F" t* w4 ]9 n+ ?
, {7 N: j* ~* o. v5 o. o
* C1 V5 t, a; E, @/ Z' |
& L6 X, p6 W7 Q. `7 j2 Y' J: t- f+ ]- ~
/ N2 u6 U* ]- H9 N2 q2 [/ p, t
7 U u1 t* D1 D" o7 D" L# h5 E. |$ h3 N0 H+ E
& c. ?" ]) V: f
; R5 B5 l; [ V8 |. W/ M- P) @0 i% I8 D$ F9 z: E
6 u4 d, M$ p" g! y$ v
" i! p/ v% F" ]$ X* y( F( B
0 F' S3 V+ ]' ~+ N6 @+ [( n |
zan
|