- 在线时间
- 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
- 自我介绍
- 软件开发工程师
 |
1 F) W. ~ h& y0 y9 m
百度百科:最短路径
7 T9 o8 @" k3 L$ t! T% X
& n+ T; A& N* j( x5 Z% F用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
& a; l- ?2 Q' h& u) T, Q中文名 最短路径
! n" l# [" R2 o+ T* x6 J特点 以起始点为中心向外层层扩展6 f1 f* m+ u% _ _- i. Q
性质 一个经典算法问题
4 D+ ]$ {3 m& N# g( r% w/ L5 ~解决方法 Dijkstra算法A*算法
: A/ K) w, m C8 R$ z
2 a# P8 o+ N n# c概述9 v v n& H: W8 ~( k, }' B
& Z+ b& I+ z3 w% E最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:
. A* b8 N! ?8 ^3 Q# u确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。
* {4 ]+ Z8 ?* {% T Z4 ^- Z( h- z! g. ?& C确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。: C+ N0 C( l5 ]$ R
确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。
/ F- b8 a) t2 n& h. g# |. p% h7 c全局最短路径问题 - 求图中所有的最短路径。$ `! m6 c8 o2 ~2 C% w/ w
! N2 Z S3 x* V4 i" o r; y////////////////////////////////////////////////////////////
2 _$ @& n1 q' Q. r9 B+ Q3 G# n z% g! ] W% i
最短路径算法小软件V5.0
8 j, }/ q6 I7 ^' m2 L6 Q3 t2018年6月
+ g2 c, X/ b4 u作者:李庚子李丙寅(李均宇)2 }8 @" C! {! L6 ^. y% `, H
QQ:165442523
* n% k' _, o( B. o& X& xEMail:165442523@qq.com ) J# H) [" S) q/ z5 p
http://www.okmyok.com/lisoft.htm
5 Y3 u- \+ I$ _; K$ V6 O' r
7 |( ]* |/ |. y/ z' f" j% L2 F4 N w下载地址:; f9 s2 c! a2 c: K% x
https://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg; s9 r$ q; f' f% \1 K9 e
/ X$ E2 x$ ?% q4 i5 T
' s- @6 D+ ?/ V) r2 b2 X
' x6 U7 J8 B# E3 _3 a3 q, M
, C2 A. w$ B; n; x+ W& r% j3 u
6 ^, B; s# N0 _$ j: n# z
0 K7 I- M2 P. G; K
最短路径算法小软件5.0EXE.zip
(3.38 MB, 下载次数: 1)
" B+ X5 L! Y' P l( q5 p
( Y* T' \1 \: X# ^
( p0 ?. ?" c0 J6 U' Y1 }& [, ~
& @. E* d3 V' N9 g$ b' P
" U t( l( ]8 u9 ~3 k" a' ^1 R& X, ?0 A& `7 Z! u" a+ D
$ f9 I9 Y# N+ L0 @8 N2 R
8 n: ~% I/ u/ P" ?( ]
2 V4 C( ?6 @6 L5 \& B- I' K* \& v8 F, [) V* @8 h8 X
- j5 P" [, j1 y5 W; ?
# t0 m) R5 F9 z. I$ V! t P. m, l# |# }
$ E2 y. z- P; r5 p% x. ]$ s
/ M. n& \: Q1 z& e- b* G
% ?7 x. M" s0 s$ q6 S! \6 L J
& A, V& T0 a) H1 c* ~
K+ a* I9 Z/ y. [
1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。
" E4 i/ `, b% @+ w+ F4 [为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。
s9 p9 ?$ Q. h- j Y用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。( i" t) H7 Y4 `
如果你要多个项目,可以COPY多个本软件所在文件夹使用。 p* p0 a" \9 f! D) k# o
2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。% {9 `& b: }" r
3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。
0 J* J. `( u/ d( P4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。
+ e4 l. r, M! r5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。
4 U6 w9 r4 U7 M, h8 W" l4 S' E5 x: g- L7 O
, E* ~$ K- V, K' U
本次升级到5.0主要修改如下:
# }! J; j0 G5 f) H1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。
1 l# _" |) H9 |1 c3 C* v, f. v2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。
* _0 N; e( F7 }! a' k3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。
1 M# u" ^! D8 T4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。' d* x/ {( }2 ^6 n( v4 C
5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。8 u7 B# \3 W" o. Z2 n
" W+ W( E# I. x! s9 E; g1 e
升级到4.0时主要修改如下:
1 V8 B) d% P9 f6 R7 g8 E2 I$ \$ J1。更正了算法上的一个BUG。" Z4 H. V0 _ D4 K( c
2。边长由只可以为整数升级为可以为两位小数。/ V2 Z9 `- Y4 \: K4 b
3。增加了可以保存运算结果,下次不用再运算的功能。) |) m) O( ^5 O# q2 o1 {% \
4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。
0 |4 a. \. |* S5 q5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。
; X1 ^- G& ^" Q6 R1 ]6。改正了设置起点和终点的小BUG,增加了进度条显示。8 L1 Z3 ^' Z, I
7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。3 {+ Y% w! k0 F* z: o' c
x6 m* o4 k+ z& _' b作者的个人网站:http://www.okmyok.com/lisoft.htm
8 f+ [( R3 m! r |- {上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。
" E; J) F& s- }* I. r2 q上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。
7 r- \# M- q3 `, h8 c还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。
, ~3 c) q% w( E% c' ^8 O- T1 K, ?还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。
) T8 z; D/ n: Z还有作者开发的表达式求值的计算器,可以层层括号等等。。。
& j" `( y. F$ Q1 k' U2 M8 T) P, `+ M4 U& J) ~
我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。
% u$ h/ D6 [$ A& G3 \, O. l7 d, x0 c" X+ D' h3 }' l
7 o$ H6 i0 }0 F! B9 d7 i8 T6 Z g, E7 t# C/ k0 { s
$ F& P: R- z! ^; z) }( p
$ D Y; B, _4 Y: r& u2 Y: v/ r2 S {" j1 k5 h
: e3 [2 M* ?! I8 ^# U
/ Q3 T& O ^! {5 }# x* C1 T: _' ~; b0 o! V9 c' ^4 T& D8 [3 F
* K3 o3 [1 q) U2 C, P: ~4 x; C: v# F- n0 s: C4 u! \
# y+ S2 N! T) U! s" r
w4 M! a+ w2 J6 m' u
2 i4 A/ p: x8 D6 a: N/ K) B H% t+ X! z& ?# E# X0 ?; x9 @( O* j
- `$ w; m4 j( u
8 S/ ~$ I" T. l& e. y8 L% @( Z4 ^. W% D' i3 y' l
. r6 h- a* E7 v/ N5 P3 ?1 o5 P
; y% u; U9 l, z5 V W# F
6 \ z: ~0 n/ E& ^2 F0 z3 H, k: ^$ E# @$ N s: [
1 l# ] W; ~2 I3 X- |
5 ]3 I5 w& l. S$ Q8 s. f+ M3 J; L5 ^- |: C- c
|
zan
|