QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3309|回复: 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
    * r, Y; o9 U  d1 t5 W# A
    百度百科:最短路径
    3 H( p0 q& G$ u! [$ G! @; Q2 L9 P+ I4 \( W( u9 `* K# s
    用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
    ; c$ Z1 k8 Z* _1 `$ D/ Q  n+ M中文名 最短路径
    " w, C5 u) Q( M2 T3 d5 q特点 以起始点为中心向外层层扩展
    ) d) o) [/ K6 W性质 一个经典算法问题! w3 P9 g; m3 f% U/ @( }
    解决方法 Dijkstra算法A*算法5 `/ n( N' X7 v- n7 G/ L# ~

    8 ?- W. W$ u! w8 m" m! g/ C: F概述
    8 O4 o  e# k: \; T7 q! |6 g; B' _  C
    3 y: A6 H8 H5 Y最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:& }* m# ~% i' t: _5 q: s/ b
    确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。! V; G9 j6 S6 J( P( B
    确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。  w) I: ~; J2 c3 `& ~, d. j
    确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。, r- y! v* u  \1 Z$ S
    全局最短路径问题 - 求图中所有的最短路径。5 A) N8 i2 P1 |9 K1 s3 |
    3 @* j0 W% h7 m- H
    ////////////////////////////////////////////////////////////
    % `6 ~& @2 p: M! T$ ?7 f  l8 O: s0 e/ x! J5 o( X' q
    最短路径算法小软件V5.0( p! \. f/ X' v9 C+ x
    2018年6月
    2 B, s& v/ {9 B$ m作者:李庚子李丙寅(李均宇)
    3 f8 P: B- h. z* T# _4 UQQ:165442523 # V( y" A  O4 h9 {5 ~6 ^1 Z
    EMail:165442523@qq.com  
    2 X' j  y5 M0 m; ]* shttp://www.okmyok.com/lisoft.htm
    3 d3 D$ e* l6 k- C- A  I0 |& E- V" _- q2 S% k* Q6 Q+ ?
    下载地址:9 x5 I! }. r9 r' [+ h" s
    https://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg
    " k- I" _$ _4 n" F; c 最短路算法小软件3.jpg
    ; ~* V% r' d* M0 o/ d$ g  u$ U8 K% z% S% T- e' u7 G
    ) ~  y0 ^. n2 S3 Y' n
    最短路算法小软件2.jpg
    ! S) R* _6 n9 C) U5 y/ X, K
    ' B+ j7 L/ f8 K9 i0 t; W4 H: W5 @( d( H
    最短路径算法小软件5.0EXE.zip (3.38 MB, 下载次数: 1)
    # r/ `7 G, \0 u! F% M
    / g9 k6 z- k6 M( Q* ?* R) n
    0 e1 }) V: ~5 Q8 D& H0 z 最短路算法小软件1.jpg " H% |5 H2 V" y7 b) u6 ~1 ^
    + l% x2 F% S. ]

    / `7 d9 {/ d, D* Q% k- y0 [/ o& ?7 v0 U) T8 X- S. d# @* F
    / v; }$ w$ a% M! B" G' B
    1 j: U( |* I8 n

    $ X- |! `5 J9 y8 H/ j" K$ h, w; Z+ n; [' n; G# v2 ~

    7 r' I* E0 N6 G; j9 x1 E! B- J
    % I  p, Y5 W+ w) h, C
    ; P$ h2 J8 h$ l$ Z: r
    3 s0 N( T( _6 Q) q' B1 Z, ]% M# s- W1 M) L6 z6 K
    ! c( J7 _9 L% y/ A4 p
    : H+ n# M# {" C, u
    1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。
    * ]) ~8 F3 R, z, y为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。! I$ G! E! ~# G5 m2 N
    用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。0 {- J% x& L4 u
    如果你要多个项目,可以COPY多个本软件所在文件夹使用。( s/ D7 K) z' a5 q1 B  J
    2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。9 x' H5 I, {9 H1 f
    3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。# U: ]5 _7 D: K5 {/ U
    4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。
    7 U5 Y5 m+ K3 q+ e3 x5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。) m+ \3 {$ h2 _
    , j* b! c& b9 n
    2 a( k. s( s% U1 X4 @1 ]
    本次升级到5.0主要修改如下:5 v. V7 b  u( K+ C) {/ t( Z' i
    1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。: c) }" X  s, f9 I# r7 J
    2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。
    $ f) m% q  ]: [  I/ x+ f3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。
    ) Z5 R% T9 j4 M' Z4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。- P- u2 p% c0 @5 w. }( B
    5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。  D- z2 W: Z$ N
    & o5 }' b+ @* b2 m
    升级到4.0时主要修改如下:
    6 r; r0 z$ x0 {1。更正了算法上的一个BUG。% h& `. y0 X+ k
    2。边长由只可以为整数升级为可以为两位小数。
    + h, H: t1 Q! ?3。增加了可以保存运算结果,下次不用再运算的功能。; M$ ?5 x' A) V
    4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。4 D/ ^: S/ u  F* F6 t
    5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。$ i: ~/ D: C- C# x, }: c6 D
    6。改正了设置起点和终点的小BUG,增加了进度条显示。
    ) V! ]8 q1 \, S6 d7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。
    : u9 e8 [! b6 @* Z
    : j* \' v. y* s7 o( C作者的个人网站:http://www.okmyok.com/lisoft.htm
    2 L% Z7 S% V- K上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。1 m! F" |0 a7 f8 z4 e6 |6 D
    上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。
    : {4 m$ o2 e& W6 f' V0 K还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。- h# m% p8 h$ W0 F% u3 Z5 {
    还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。6 O5 J6 O+ e- }( V5 j
    还有作者开发的表达式求值的计算器,可以层层括号等等。。。
    # V, q7 ]4 S( p+ p  s7 y, k$ k: B* L7 J0 H% l
    我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。$ E+ S5 K, q* x. T# o3 _8 R9 }
    : q3 @5 Q& _- }& v# p4 V
    - z9 r% ^( z- p) q* }

    / ~) ^( M0 b* t  R
    6 R  c# t9 A8 R: y# b4 Z+ _4 w4 ^9 I2 s5 t* n6 [

    ' m& h5 w" x* r& |% T
    # D' H6 }% u' z
    3 n* s. G; |; H8 N+ P2 {5 i; j. x' D; W: Q8 G" `/ ]( f
    1 z* H) R- }5 @& }
    ' ]" g1 d6 C" Q, s& c+ W9 G" a+ j4 \

    4 \  p" ^- ]; `! \+ M! n! m: e1 s" ^$ H# T

    , j) n% N* z/ J2 S  d' U& v( F% j; b  N! |, x: M
    8 |% V  b' @5 v. D) G. w

      j8 y) r6 |: g4 y& [3 ~8 V9 i+ p8 ~" Q  Q: A
    5 A+ O, z' j4 x
    1 F8 m+ z3 p; }- z7 u- b7 W* p

      D2 F* U" R' a& o# J1 n* m
    5 \! _6 t/ g+ V
      p; f( _( I7 B- J
    8 Y& H1 S3 _0 ~2 [% t9 Z0 d  q. w. g( a( o
    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-11 01:00 , Processed in 0.464484 second(s), 54 queries .

    回顶部