QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3303|回复: 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
    & ]6 [" R/ I/ j- e9 Y4 ~4 {
    百度百科:最短路径
    + `) B7 n# S1 V( Y, J1 _/ l* X4 f0 s% Z. B) X3 @+ c1 w
    用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
    7 v. z& G4 }# x3 ]8 m- {& v4 x1 {中文名 最短路径
    ! r6 E6 Q, g7 E! n: u9 s特点 以起始点为中心向外层层扩展+ ]3 ^2 S( z! R0 w% s
    性质 一个经典算法问题8 j5 q) D' M% M
    解决方法 Dijkstra算法A*算法0 ]8 p+ `. o! z0 E

    ; M* {5 e0 @! L  U/ s9 q概述
    , N: T5 ]( H" W) f4 L# z8 w, T4 z# I3 I
    最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:9 {# h1 s# G5 y
    确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。  g6 {! @: K$ S: Z( J9 G
    确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。  K' ]2 K% J# }1 L0 @' Y6 w
    确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。! a2 i# R! r, z2 W  |) S8 y
    全局最短路径问题 - 求图中所有的最短路径。
    & @/ M( X" O" O+ L% q" c/ T
    4 Y$ S3 P0 l  Q7 [////////////////////////////////////////////////////////////- C/ V  I% @. [$ T6 |; s

    7 V  K5 \9 Z6 p2 y; ]- O+ c最短路径算法小软件V5.0
    * n" J5 L" N! n2 \: y2018年6月
      q# ^: L9 O# T7 I6 f3 X作者:李庚子李丙寅(李均宇)
    3 j2 ]9 m& N. E) d) M) VQQ:165442523
    8 N9 {4 ^9 n9 n* n* z& GEMail:165442523@qq.com  
    4 N- P: ^. O# N# W; L3 z! ~http://www.okmyok.com/lisoft.htm* {! t8 L8 r' Q2 s/ `8 f
    / ~# @) K% K9 k$ ~! B  I+ f. a& X
    下载地址:9 T- {+ g9 W5 l- W  I$ S
    https://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg. H" y& y, n8 C7 [! H
    最短路算法小软件3.jpg $ o  `! D5 i) q4 G$ ^
    0 d+ ~& F# b1 R. Z

    - A; n  {/ t- s  i 最短路算法小软件2.jpg
    # ~% |! z% [/ o- ^* t3 w9 o. Q9 g5 \
    4 b# |3 E7 ]. B$ m( D" L
    最短路径算法小软件5.0EXE.zip (3.38 MB, 下载次数: 1) / R: G# A! D. c0 Y/ ^" ?4 J/ _& [

    * r5 k& e# m$ D. a, }% T" j8 a* `; \" W9 L" Y" H6 p  V/ c( m$ ?
    最短路算法小软件1.jpg 2 Q$ H/ H: t' c8 [$ [3 ]6 \3 e

    " E( p( c* O  j* s! g
      b+ B8 Z/ Y" Q' e/ j1 ~# C/ s6 G0 `6 `& ]

    9 U3 d2 n+ i+ t& J' [/ l$ w5 X  o5 u3 f% p2 I  ~; i
      T" F" z: g) |8 ^% J$ _1 o
    - z' Z1 i  m9 C$ M6 _- _  C+ c  c

    7 p/ \' I; o" v% H* G8 o1 O
    " i% p  G8 V: ?: V, B1 n- q7 y
    5 v9 a7 t! b0 u( C
    - A3 d5 \/ f% X6 X# V( l& W+ n0 m9 S
    ! \* `1 V. o% `6 Q* k! ]/ p
    & D8 L  h# u/ m( h; t% C+ Q
    1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。
    3 T/ ^  P2 K' M' w5 f为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。3 s" n) P- d% A. Q7 O3 S2 y. a' X
    用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。& I/ u0 K- y' ]4 A6 y$ Z, B3 }) Q
    如果你要多个项目,可以COPY多个本软件所在文件夹使用。+ o7 J9 t" U8 Z: T0 F& I
    2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。
      c9 d4 D. `$ j/ }) e5 l  i3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。
    - V! B  K' r, O1 x) {& t4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。
    6 [8 I0 L) q9 \  L& s- i& [5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。
      R' y6 w2 Q& S( R# @
    9 g, _- l7 L$ @+ R) j% V2 ?$ J; a
    本次升级到5.0主要修改如下:$ U9 I1 i0 G0 i9 O
    1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。6 K4 z, I; B3 @
    2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。+ U- O1 U. M. y. s1 ~) x% Y
    3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。$ g6 z/ V$ I$ w% W
    4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。
    : |) b* o- W2 U% A, X- Z7 E5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。$ f/ H8 _+ }" D# i3 U2 i( G, r
    9 D7 c+ s$ ~2 l( j
    升级到4.0时主要修改如下:5 @  x: v9 s' ~0 o# c! m! a" V
    1。更正了算法上的一个BUG。' y2 J- l! O6 P; n) n
    2。边长由只可以为整数升级为可以为两位小数。0 v, D* q* |" u( ^/ V0 d( I
    3。增加了可以保存运算结果,下次不用再运算的功能。: `- u+ W. m! }0 R' A
    4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。
    8 ~+ P" V7 E. o5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。! ?( `9 y; t3 g2 K* K2 H
    6。改正了设置起点和终点的小BUG,增加了进度条显示。  p, n$ ~: h! L3 _0 d& Z- ?
    7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。
    5 ^/ _" }; @2 O5 s2 {% o
    $ y7 G' ~9 B7 n作者的个人网站:http://www.okmyok.com/lisoft.htm6 H- a/ R2 x, v' U2 G
    上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。
    + `9 h* U+ S( c8 b, d" o( Z4 I上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。
    ; ]1 _8 ?& w7 x还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。
    ) d+ l- X3 b* v3 j# G7 @$ l0 j8 L还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。
    4 j8 W) o: ?  L$ f8 O还有作者开发的表达式求值的计算器,可以层层括号等等。。。% O* ~$ v& K3 I( L4 M( G5 F

    % Z$ f; |2 _+ b* C3 A" m9 A我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。; U' H- }! ^$ T( [, R* |# V

    8 M6 g7 Y: J+ Z4 W9 T  ^
    9 g. N- h- W$ g/ }$ {6 m; _; h0 v. B; J" O2 l
    9 w' n4 E* ^) s5 q

    ' \: h3 m  G/ M/ J. c" p5 F
    ' H! \- K) w  D: y, J8 c. m* q( [: F; R& R% G5 Y: u. a

    6 O1 Y8 q/ v! D1 R0 z
    / s5 j- N) z6 C- B7 j; i, F7 E, y* g' o' Q

    ' P+ M/ G+ d5 w2 h% w1 u* \( t( e4 s  c9 q+ I$ M

      p2 l7 T8 \8 w! `6 K
    , L0 v8 @) Z9 c2 i( c% e6 c- Y8 O1 t; G; N& b/ u

    : E8 F3 x+ r8 G7 S# |' x
    ) s& J' g7 J& A3 ~$ _. M" d$ A$ E0 c1 m9 q& u+ d
      c% G/ e5 u+ w
    & h7 `( N0 b. \: L2 Y: [+ I

    / O3 o- E$ @. x4 @) ?, H' ^% w8 j( D
    , r, n" `1 \5 u  ^1 y- H& R' q" q/ }/ c  s

    9 v4 n/ g0 f! K2 b% {0 o8 C) c6 W, I
    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-9-10 04:57 , Processed in 0.350762 second(s), 53 queries .

    回顶部