- 在线时间
- 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
- 自我介绍
- 软件开发工程师
 |
% a5 z9 ^7 [9 \
百度百科:最短路径! {1 ~5 M# g, S& N2 L
& @) @$ L' y6 q( \" k
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。4 K( T: p& V3 e6 y
中文名 最短路径. j6 H6 t6 c2 O+ V4 p0 x' X# P! I' |
特点 以起始点为中心向外层层扩展% R, p3 o) G. E* S/ m. G, D4 ]
性质 一个经典算法问题
9 \, `! I6 [+ R# L, U解决方法 Dijkstra算法A*算法) u' m6 l& @! ?1 T* r0 g
0 m7 G2 H j( y0 S3 V
概述% f( ^0 g+ o2 _+ X
4 F7 W2 s8 M2 t4 p5 r( H
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:
3 D+ {# V, U6 v7 O7 ^) T( p确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。' R. J9 h0 s# \
确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
0 m: s5 O- j/ n( b( P! \: g5 f确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。
2 s/ W& ` B- H全局最短路径问题 - 求图中所有的最短路径。
5 F/ z0 R- a( f- p
* r7 A$ L. r0 p8 ^5 `////////////////////////////////////////////////////////////- o5 p& S& f) ? s; m8 ], z- f7 T
7 z9 E7 a& B$ c1 i* g最短路径算法小软件V5.0
4 n" X* O+ i3 D# @2018年6月
' G* q6 T% ?. u6 ~作者:李庚子李丙寅(李均宇)
* X* E' K- V1 Q& |+ D. Z! oQQ:165442523
; b% _# h! T& {5 j$ b' Y. B# sEMail:165442523@qq.com
: @( W, j8 ~! }9 H( i6 P1 t( v7 bhttp://www.okmyok.com/lisoft.htm& Y: H! M: G& g8 [
1 i' v- Y/ E$ X. j5 X9 a下载地址:
2 }" C% ]' t) g: B8 t/ g' y5 X4 Ehttps://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg
+ v9 o% G) ?! h- ^# B
. B0 _0 Y5 V5 h$ K2 T; Y% ^6 d
; G# E e2 N# J( e8 k: g6 w/ G% S9 F, w5 Y3 \- e
; j, H& \! C( G+ O% H5 r& e
R9 K% W @- H. V6 _" D! O8 ?- I- F N n9 S7 U0 {+ V
最短路径算法小软件5.0EXE.zip
(3.38 MB, 下载次数: 1)
# L/ Y( F2 K m; x
% P1 |. Y* I% S& t8 u
7 J9 c. z5 r! K0 _5 S
- C- j" e2 A, ~
! T- P6 t3 I5 V* |* J& @+ D: {
" B) B7 f. L: }: l3 E$ B! ?' I
2 e4 o4 [7 ~! d% x" n9 P6 O2 W' e; ~$ K5 O1 C' O0 n1 X8 h- }8 b
. ~8 ~" ?% x3 l
; A! A& I9 i# H. m+ ~5 O
! @) H8 M7 u. B. d# J9 J6 Y
E: }) o8 C4 J9 f# w1 `/ A
2 {, d7 W; Q$ W* r* ~. w. ^; ]1 x1 p( D% D! {. G" x. m
% Z; H5 k% b1 ?& A
% F+ r& T. ^5 C; F$ U
+ D& u. K4 b) z, i+ ?3 q1 A1 `& k
4 M! T7 y; D$ r5 `7 S, Y6 @1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。
' z* x) v. W* a4 Q2 ~为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。
0 c9 Y- W" v u5 a7 R5 _6 R. ^用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。8 l0 t/ l/ X3 N1 p! Q& T
如果你要多个项目,可以COPY多个本软件所在文件夹使用。; d9 m2 ]& ~2 @4 Q
2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。
% x# E( ]/ ~( _$ u0 ^3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。
/ }! K5 d! o0 R Y+ i0 @4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。
' U& n/ Y8 s" {3 A. R2 d5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。
! ^ g. Z z7 k: m" T' v: O, b& O" E
: h D$ h- L6 {* i u( ~. K0 b* r9 l4 K
本次升级到5.0主要修改如下:
3 V3 {/ i0 `) ^3 s( c1 @: J1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。) `5 S; r O; o6 L
2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。$ x1 W( m* p9 ~# n
3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。# c$ x) w/ K, R! `' D c! P! W ~
4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。( a7 _+ \$ k3 K: E$ U/ [
5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。. Q- t9 t+ w- u
& S, m; E- ~' g# |; s升级到4.0时主要修改如下:
, m. \, \" {/ _0 q, F4 z1。更正了算法上的一个BUG。
" W7 S0 Z4 l8 z7 E/ O$ o2。边长由只可以为整数升级为可以为两位小数。, F' k: S4 f6 k" U
3。增加了可以保存运算结果,下次不用再运算的功能。: C6 g$ |$ g( A' Q6 b7 ` W. R# J
4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。- w- U- n3 E4 E! g# R7 u: ]
5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。
) g: V, O3 S( T$ _1 P6。改正了设置起点和终点的小BUG,增加了进度条显示。, ]5 _5 E1 g" H* V0 L. R; S) c
7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。, E! z# G B4 R0 w& }
5 ~7 o' A* K! n9 u; ]
作者的个人网站:http://www.okmyok.com/lisoft.htm- ^8 S3 Y* B* I0 F5 C
上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。6 z3 e) f4 g d# D( ?
上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。, u4 L2 @' o: ?8 x
还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。 {- W+ g3 Q. K( _: Z# B c
还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。$ S# G: n2 ^# A: j' E! h- T
还有作者开发的表达式求值的计算器,可以层层括号等等。。。7 F" O& F( W5 R- i9 f. Z% j) v
* W/ L" l, o( c: e V6 L2 H! y! s
我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。! u5 } C: J. R- T2 ^: p# t
& [) a' m4 ?( O1 ?, o/ G( p" K) P
; N! v p. l1 ~' w: L
" F; q; V% M) k$ }' h" @: j' m, H+ ?! A4 B! F# {4 c5 {
. i* F( w$ X4 S4 j8 [. n4 r
4 q* n. B/ s. Q4 O9 M2 j' o2 B. a1 b7 n S
' L/ d. d6 b9 h3 u
1 s! W+ d l/ ^) _" r4 d% B0 I j7 T' }5 b
) }# [/ g/ h! v( `
2 R, K# S, _) S7 b/ H% s4 M- T( n6 G+ ]- }9 ]& ]9 A7 @* y
4 B: R" R6 N3 `! l* T m
) t( f% R, T' _) K) B$ y
$ J" O# [" @7 G$ b1 t+ j$ W# z4 ~ u
6 `8 L0 U0 R! h+ G8 j) W, f& i
0 ]% W: G0 _" G: z# S
; W) i0 i0 s b5 Y+ D8 Q2 B) }4 d
& a) J7 A2 X7 \5 M2 {
3 x. \; I3 }3 ?' C# C) u
j+ U& ~4 @3 I6 K/ k
: J! [$ B. b, N+ h' z7 [% d$ y9 ~( }% Q
6 t; ~& x" {$ r6 N |
zan
|