QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3210|回复: 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
    $ {2 e; J- m8 w6 W0 }) A
    百度百科:最短路径6 v9 j5 x8 P' f/ U( L2 L
    ' H+ v7 [5 W5 p
    用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
    $ b6 m) j  g" q中文名 最短路径
    4 M" y; `( e0 L+ H3 L, \  v特点 以起始点为中心向外层层扩展
    1 ]+ P8 x: T3 \8 S8 o% M! N+ [+ M" k性质 一个经典算法问题+ y, W6 a5 R( }. K; w" k( C7 ]
    解决方法 Dijkstra算法A*算法3 q1 K0 R+ F$ u  ?

    + ], c* D1 t8 ?1 f) m( ^概述
    1 w4 h+ T% d- u
    . d* w$ ?/ \- I! y& e% a- h8 X* W. }最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:
    " e! r+ H: ]3 C7 P确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。
    6 M; c& a( a% w/ l' J0 f9 A: @; |确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。4 ]* L& h' v" V6 h6 X
    确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。  \7 L/ o7 \7 X  J5 f/ S& `) A9 b
    全局最短路径问题 - 求图中所有的最短路径。
    % C! K8 q/ `1 j1 j% C' N5 `. A* e  D8 t9 m
    ////////////////////////////////////////////////////////////- {2 {2 h8 B3 k0 G' h. C6 P

    : o4 G: L# ?# P- s9 u3 g3 h5 J最短路径算法小软件V5.05 k" E3 r% r- ]7 t
    2018年6月
    5 v! g2 D5 {6 B4 k) t作者:李庚子李丙寅(李均宇)9 n, }% y; v! `. Q$ k
    QQ:165442523
    & z$ h2 {. t$ C0 u1 H* K2 |  _' `EMail:165442523@qq.com  - a* u9 L0 k) k! j! h
    http://www.okmyok.com/lisoft.htm
    3 v4 _- o. f7 ]6 L9 l0 Z% {2 L5 s9 n7 q) |( v2 `* l4 s
    下载地址:5 o4 ]9 Y' A) O8 w' J  z
    https://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg% T4 h- m, Q' _9 \  X+ l
    最短路算法小软件3.jpg   B: c$ {+ S- o$ O; Y0 K
    5 q& s' B2 h7 c7 \2 B% ^
    . G, U4 z% }4 K  P
    最短路算法小软件2.jpg
    % O+ U2 l: T/ _( S8 x9 Q3 F6 h; Z# K# Q0 i5 ^+ B. \8 p7 v

    ; P% g# }6 y/ g3 i  w 最短路径算法小软件5.0EXE.zip (3.38 MB, 下载次数: 1) 4 q/ [) Z, w% c2 t

    / s' h& o* Z& p% [7 b3 M; ]$ G+ i" l' e; G7 ?
    最短路算法小软件1.jpg 6 T1 B9 L& [' q% \3 ]% K
    . j, J* R# G  T" M
    ( c  u9 @+ V" u+ L5 C* `7 @
    8 t7 H% z- k5 `, g: \  R: r

    1 m) I+ B' w& ?$ o6 L. G& L$ N' ?: f/ D

    7 F. J: p! k* t0 t7 g- J+ h. r/ L
    0 e/ _1 o- _# d7 Q4 z7 Q' V, \# p2 [: `6 X' o' b. ?- |/ M! D

    & U/ b' Y' X2 M: f3 {# t5 a8 O0 X7 @( G9 K, V1 ^" J: b- l7 N

    ) l8 `# w$ m8 [! L' o1 o6 t$ F& N& A8 x! b) |

    1 m7 Y& ^6 S7 u! l8 V
    9 s* \/ }9 m: r/ _# ~  V3 I( P1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。! ]" H# @2 w. u+ r$ y* J
    为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。
    8 `1 [; [9 f0 H/ {+ c) [用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。; y4 @% Y& C# O, ]5 y8 G  f9 e5 F- n
    如果你要多个项目,可以COPY多个本软件所在文件夹使用。) k6 |) x7 v9 J% z/ S
    2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。) X* k+ y3 J0 f1 T+ v9 o
    3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。$ y* [& l& v5 C: b! t1 d3 h7 s
    4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。& S$ h# r( O3 T- n4 j* _, O5 @. A
    5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。
    & e! z+ B7 C" a& i/ V2 |$ v8 B1 i& i

    0 L6 j6 L" F( S本次升级到5.0主要修改如下:& J( r  f; f. r4 V4 q1 \# o& @" A/ u
    1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。
    + a3 [% W0 v( [5 @( t  _' I2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。
    1 T8 q4 R5 r# v0 z( D3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。
    5 |6 L3 ~8 C# J$ ?$ P! k9 _0 U4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。
    + y$ D# Y- l; m" |7 O$ `* c; C5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。2 ~" G/ ]/ }! e, k) B$ _
    4 b: M/ A1 R+ `; \  U
    升级到4.0时主要修改如下:
      G8 w/ N# B6 p4 m( C1 ^! K1。更正了算法上的一个BUG。
    9 t. a9 G, N* e: W) _1 D( f2。边长由只可以为整数升级为可以为两位小数。
    4 e: W; q! ^' T2 K3。增加了可以保存运算结果,下次不用再运算的功能。
    & o8 ~/ y$ u7 J$ A6 D) ^* _/ |4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。: K6 `/ {9 i/ A" b9 j
    5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。7 t3 C2 h0 \" G$ U0 |. I
    6。改正了设置起点和终点的小BUG,增加了进度条显示。
      l, N5 i: ]# |$ S) n1 A+ n6 q7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。& j1 E2 t5 A& b" h/ Z
    8 P9 b. f; }' H3 j2 u
    作者的个人网站:http://www.okmyok.com/lisoft.htm/ w3 ~) {% l9 z7 I" i
    上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。/ T; t) Z) W1 `- y7 y' d2 {# Q# ^
    上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。- s3 w3 w% [) c% n& a
    还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。% y. ~: p( _/ m
    还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。
    7 u6 B6 F/ W1 i2 i还有作者开发的表达式求值的计算器,可以层层括号等等。。。% t8 z/ H. i0 L6 @7 p

    - |8 y7 g6 ]& s# _/ G4 f3 l' j: C$ N8 C我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。
    6 S: R: [. i& p7 y7 m7 z! ~9 X  I0 |  A6 w0 x9 I  k

    " l2 I0 A% Z/ e- D5 u5 U2 r% Z  b" I; I/ p9 U9 ~" F

    6 z! |" a- t! Q
    ' R- r4 i; H  d# {- r/ k+ |
    ( e& X( O  ], l* A% J  d/ _7 k4 P) s9 G0 S; b% y0 G

    8 O9 T) W) W# f# v$ d$ ?3 L  x( R4 Q) a3 T
    : g8 g4 c' d; T4 Q4 d& o/ G

    ) r5 |' _3 ]; O
    5 L  O8 g4 m& n9 A3 \
    4 C; l# t- z$ {! C* S. M6 v7 I0 q; m# S: |. u4 a5 r

    , k# h  B& c! {. u& b
    , C- u, r, u7 e% ]: a) X; y+ T, t& c
    / Q# A: c; q. t1 g! Q, }7 r8 |9 u9 i

    6 G/ o" |( T5 M2 D
    % p5 Q/ E2 u; l; G
    3 U$ K! H! m& ^( c) c# o8 ~, _1 ~6 |* R/ `( u& l# Y

    ' b4 l! T% f2 [1 c6 _3 E  O4 C/ V
    % c1 |, g+ c# `& s! W! X
    * k  L( M( G' _
    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-22 14:17 , Processed in 0.394612 second(s), 54 queries .

    回顶部