- 在线时间
- 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
- 自我介绍
- 软件开发工程师
 |
% p6 y$ D2 t/ s3 w: F
百度百科:最短路径
1 C' V! B- P7 x6 n, D d6 V% Q. q3 r) ?' h
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
: I% R' A K4 B" G, R/ O1 U中文名 最短路径7 U# A+ F; U* |8 q5 Y
特点 以起始点为中心向外层层扩展
' s; p9 B: f+ e. q9 S/ ?" f h性质 一个经典算法问题
. V5 F/ J7 k$ K H# @. p; d7 ]+ n解决方法 Dijkstra算法A*算法
3 Y( u! a7 f; r& t; K* s
7 X5 D3 ^+ c" F概述
9 I, } {+ U! s6 F5 b, }3 o1 a0 W9 p6 e8 @, [
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:; w7 o" i( K) U2 `
确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。% v8 K: n: d6 N3 P4 O
确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。' X4 d/ i+ L5 l& |7 N0 u
确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。
) k" W* A( ]( {9 U' I/ `2 x全局最短路径问题 - 求图中所有的最短路径。( A9 K# T- n! O! z# s, c
, ?* `8 k4 I6 z: h/ @
////////////////////////////////////////////////////////////
) B1 j& m- |% A/ S; s2 U. T& Q7 l7 w2 P, Z- V* c
最短路径算法小软件V5.0/ s# x1 c; Q1 Q# _' x0 k5 J; |
2018年6月 ) d# d: p& q, S. w
作者:李庚子李丙寅(李均宇)- j1 r3 U% s( o' Z4 u: l# s& g' `
QQ:165442523 2 @- Z2 B& M! b3 V9 n
EMail:165442523@qq.com . s; U/ `- ]7 C1 D/ K3 ]7 ?4 \
http://www.okmyok.com/lisoft.htm5 Q' p! V0 v, {( ] X, D; I2 n' Z/ h
0 }& v2 ]' U, }( P, Z& G下载地址:
& m1 K; g7 H# @3 f* P( Q- phttps://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg& U7 ~/ O) i) Y u7 X" T; q; n
& u" v$ y" |/ A9 O
$ l& ?0 a) `0 M5 q6 A3 h+ D4 T2 y$ i- L$ T$ G
1 s6 k. G3 l7 Q( S( I
' G! L% l C$ o) ~6 a8 A
$ T9 {& ]7 c, J+ j j- _
最短路径算法小软件5.0EXE.zip
(3.38 MB, 下载次数: 1)
8 g# j( R% ~5 x# S9 c
0 r0 _& h+ z; u' V7 N
" q" q/ ~4 g3 q
v2 p4 h' j9 J' s# {7 M/ I( e
" e+ b0 A& I% P7 I0 D
0 j3 r% J3 |, @' |* E( X) V* H: U4 l8 Q5 ^/ {$ z3 X8 t
3 @1 W0 [7 T0 {: |4 u5 x
* a. e% N! C3 w! K/ P% \5 g0 u4 C: @7 {5 m$ n' e
2 R! x! z& K. h4 w* \, D ^
9 [1 q' O9 U( I/ }' O, _
: {* H# z7 x0 k( m, _+ M% f7 b; n$ B* r- H4 V
. P. |9 q$ Y d' Y. O. t2 p. t5 t: L- Y
, z" m' f$ A, B8 t5 N/ d+ T' a
" i; G H: X$ B' J2 c' T$ r/ V1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。
; }2 l4 F+ K% X5 x为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。
8 q: l; A. h7 V1 j4 K% k用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。
- f2 L. a1 g/ d如果你要多个项目,可以COPY多个本软件所在文件夹使用。% A+ Q) [$ z5 @' e% B9 d$ t6 o
2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。+ J# [4 M3 ~5 C: }6 l3 `, S
3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。
- x9 [! H/ r% x5 G; G! V4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。
2 m+ d2 g9 `" t R' c* g: b t) L5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。
4 R. J; u2 f: s9 C) E4 J3 F3 A& o3 H; [0 c* ^9 \1 C
4 v5 O* M* R; c: V* p: q
本次升级到5.0主要修改如下:3 d# z) k: a$ x) S
1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。8 X+ Q# e( v3 \3 Z' W
2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。 I1 i* E* m# ~; f
3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。
9 v+ p3 H9 Y& z6 U4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。
& i3 Y3 b9 o% }. B2 R5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。& a4 s& S$ A0 G. h% \& i
5 n/ u- Y, p- D0 [5 Q! D升级到4.0时主要修改如下:
: b5 O. S0 Y9 @; F1 w1。更正了算法上的一个BUG。
2 U' \. {: F' {) d: x h2。边长由只可以为整数升级为可以为两位小数。" F& b9 d3 Z# k! g
3。增加了可以保存运算结果,下次不用再运算的功能。
) h9 K5 E; b' U4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。& V4 I/ E; t* m5 K6 X: \0 M
5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。
8 X3 y' P, \6 l% f. R& w6。改正了设置起点和终点的小BUG,增加了进度条显示。
1 l T; c+ a& @7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。( C* `" X5 w: _" o6 ~' ~! A
# u) w* |# H% w; r2 q1 c, d* M作者的个人网站:http://www.okmyok.com/lisoft.htm1 x7 q v9 ^, n: ~
上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。
5 F0 u$ w1 x5 |# Z7 W2 i上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。3 ], }2 v) l }0 {8 g. x% L0 [
还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。/ J$ g- Y! k* d y/ s, g' A+ ^
还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。( @5 N) d$ `2 j8 S" ]' \5 B
还有作者开发的表达式求值的计算器,可以层层括号等等。。。3 O2 G' [3 l* t6 Y `
, n+ O4 ^4 g$ |9 o9 X- N
我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。
- S0 ^, \) L) a4 H6 e K5 O
. e A0 R0 Y2 ]2 p& {4 q6 P, ?( g0 r; T
8 q' ^8 o9 `' r
) z% X) |) n& V- o3 n: y
8 R' E: V% w( B0 a4 f# A9 u5 L- _* {3 K3 ~$ _% o) e
: O& L# O A! F" _' \
7 v! @1 ^2 ?8 Y( b ^9 s: K4 M, `' {+ ?' ^; ?* S
/ _) s, f$ |3 L \0 r
0 ?$ b& ?$ A; p6 P
% z6 \2 B9 U/ }1 E# ~. J8 V
) B8 \) W; v/ f3 c1 i, y' L; E" i0 N8 V/ I9 k2 @' }( n. u
% i6 t8 \* I2 S& P
, S( f$ `3 V. J; f/ }
1 g# O+ [# ]7 O( O6 D
/ l% ]+ t. u& Q
3 _! H; z' H: V1 w# h
" l+ c9 A; u" K2 d3 E5 A/ |) @- Z" E' X
- E7 r# w* @1 o* F& I1 ^2 q7 l+ h! m8 _: b0 L
, c1 w- Y) |- L# a4 I y4 h- ^
; q8 P0 F4 ?2 q6 ?& ^2 U |
zan
|