QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3209|回复: 0
打印 上一主题 下一主题

[其他资源] 最短路径算法小软件V5.0

[复制链接]
字体大小: 正常 放大
释永思        

23

主题

13

听众

146

积分

升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    跳转到指定楼层
    1#
    发表于 2018-6-28 12:39 |只看该作者 |正序浏览
    |招呼Ta 关注Ta

    0 C7 B8 N; U: U  D# O7 v. b, [# C百度百科:最短路径
    . j  Q# P+ q' D8 p9 ?* Y, q. W/ s* V& I0 D0 r
    用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。* b% J0 t) C* Q) B" T0 S
    中文名 最短路径
    * W, Z8 P5 ]0 p7 I; R6 T7 U1 a8 g特点 以起始点为中心向外层层扩展/ J( v# ^* A0 p9 ^
    性质 一个经典算法问题
    7 W, g. L; ]: ^9 Y* l/ Q解决方法 Dijkstra算法A*算法) r6 k; f, K' u3 q3 e+ P- Q
    / A& L, j$ U8 E
    概述
    : a& r4 N# w4 B- x
    1 |% w' a% P6 s3 e, l, J; R" h最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:
    - z, g4 `9 l* i' |5 Z- ^* `1 E" S" ?确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。
    : }# S3 r3 D4 D9 @2 L1 ?确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
    7 z! O8 Q2 Y' `- h7 {4 l. X确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。
    : R" @9 Q9 ^8 U全局最短路径问题 - 求图中所有的最短路径。/ @3 v5 D$ D1 H- A0 W6 B

    $ [% u: l! s6 o6 a0 y4 v////////////////////////////////////////////////////////////0 r& z( i* q9 B. @, F1 e+ J$ q
    - n+ A5 _! J& G7 D& `! k/ B
    最短路径算法小软件V5.0! R/ @" ]9 g( c. B) i  w: v
    2018年6月 $ K5 |- ^) d! {- ~
    作者:李庚子李丙寅(李均宇)! R+ B+ f6 X" y' d' j
    QQ:165442523 , R$ l1 r+ ]: G: X' Y4 U! V- [  F# N7 X
    EMail:165442523@qq.com  
    : g4 j: A* ?/ c3 d: z; ^0 Nhttp://www.okmyok.com/lisoft.htm8 G5 k1 M) P6 F. T: b1 ]* U

      X! t* S7 `  @% U$ c下载地址:
    ( Q; a9 Z! T* h* o/ fhttps://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg
    % l2 b" \( d* G 最短路算法小软件3.jpg
    : V6 N- R( y7 r. X- J+ ]8 I& M; l5 Z: v: S+ z) c% x' t0 A

    ( y3 k# }$ L/ }% ~ 最短路算法小软件2.jpg
    0 Z9 r' h' S5 O5 O- k8 P$ T
    0 V9 q3 ^. c. _  j& i
    ; @9 B6 p5 i/ x: j& f0 \0 G, Y* h 最短路径算法小软件5.0EXE.zip (3.38 MB, 下载次数: 1) 9 B! }2 U! ^7 d$ G% M+ ?0 \! ^

    & T# a( {5 v+ _4 ^6 Y5 \. R3 C3 A! a& p) \1 V( @9 I
    最短路算法小软件1.jpg
    ! F- t$ n7 S: M' I, t3 H- ?  R0 {( A5 e

      R# S$ }6 ?3 n- x. i" m; R1 K/ p8 O- r

    8 E  X5 D& L+ |- b- ?: _! `% j  h! g4 E5 K  e& I

    1 ~+ T8 ^7 r  I6 o2 J0 m# A3 J6 Y& U9 }- B/ c5 Q0 R& w

    * ~, U7 [9 ?$ `. t) w# R/ Q- B. h+ q
    ! a( x0 T0 O7 B4 f
    4 c' e0 F* s' |* I4 x& ^2 s! }8 K& x
    * V; c1 t1 u" j% q. }' j

    9 O) a: ?& [7 ?! g" b/ z  R6 A* v+ [) Y( F" g! [1 N
    1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。
      O: k0 R" H( Y为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。6 @2 O. m( Z% i7 J% I
    用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。3 c0 J0 a. ~$ h
    如果你要多个项目,可以COPY多个本软件所在文件夹使用。5 ?# b( @+ B- j5 x! ]- U
    2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。
    9 X6 N7 C; {. l$ @3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。
    4 q% H: ^$ v4 _: r+ q4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。( G& o$ O$ t: L
    5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。# |0 q6 H& p6 D( v
    , L4 a1 w  t7 V8 A# D+ ^

    , y9 L% n0 e3 i  e/ F4 v本次升级到5.0主要修改如下:
    ! Y5 }6 ~! n9 E! Y! r2 N9 Q* _1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。
    # C' z& z! X2 W5 X2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。2 c% ~) s% P( [" g/ x
    3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。
    4 t9 u- Z' V8 L) @( q4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。
    5 I! D. a* I+ O. ]% ^3 n5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。
    5 t! Q/ p7 y3 n( }/ S' @
    7 H+ W& Q9 c5 ?: Y# w升级到4.0时主要修改如下:
    * ]0 V& e3 ~+ X) m# c" y1。更正了算法上的一个BUG。' e* z4 S* q3 Y; ]
    2。边长由只可以为整数升级为可以为两位小数。1 Z7 F  `2 x) U; B" s8 f( j
    3。增加了可以保存运算结果,下次不用再运算的功能。
    3 m0 @( r0 J9 _: T- P+ X4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。
    $ p5 u! K) i/ Y% _- s  m4 }5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。5 o; t2 `4 F. D3 C' e: Z6 m
    6。改正了设置起点和终点的小BUG,增加了进度条显示。
    7 r7 X* @$ n3 e2 z7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。
    * |1 g- x# l! x: l3 A
    * ]. F% t" X0 \* E: [: e% d/ |作者的个人网站:http://www.okmyok.com/lisoft.htm& q: J- R" e( J; Q$ l/ |" V
    上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。8 A) s, ~4 h- S3 F1 j# o9 g
    上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。
    7 P' K5 p% F' J( J* z! t还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。
    3 b/ [& V7 d. v1 G7 }. \8 N还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。
    " @( r/ K5 o9 G! h还有作者开发的表达式求值的计算器,可以层层括号等等。。。
    : N, W9 @2 @  a5 h
    # n( S0 ]4 P9 ^我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。
    . _0 J2 n) u! k, O: q
    * u+ `! a3 l& t( G4 h% _7 H5 ~. o3 v7 X0 S2 g5 x
    3 n) o$ B/ Z' a8 f2 E8 M8 ~- K
      V0 C4 m: {+ g+ R% w

    8 C1 B6 x! b3 P' Q% ~* e
    / M% O* q+ `0 X# U2 j- o& E' A* H  J. h( ~- H

      z' H5 {* U2 P* O" _6 R3 H( x. e% k+ O* X- f0 V' P

    : S# F( F  a' I- x
    , o/ W3 }, V- q6 s) y, L1 A0 \. s/ ]- [" ?3 a4 c8 E6 @
    . Q0 J- l0 }0 k  N' l3 u7 `6 `9 `, X
    ( W% B4 V1 R  B. Z- {( R

      E+ a0 |7 b7 T% t
    . L# }4 b4 X  L1 @
    6 [) Y( w4 v/ r$ a
    / i7 e( ~4 i9 r3 B7 E& |5 l& \5 ?; E9 b  h
    3 i/ A, [) ^2 x1 [: ]; m5 F
    . s) k  U; q. f# h
    0 p9 C0 n5 j6 C, m% J) B3 F+ ?5 H
      e. o8 N3 h& o1 d
    : n/ r  S5 L0 ]0 v
    ' D1 W8 v2 @+ ?  @6 ]
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏1 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-21 22:35 , Processed in 0.557474 second(s), 54 queries .

    回顶部