QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3304|回复: 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
      J4 F/ e2 L2 s$ Z8 \$ i: t: ?
    百度百科:最短路径
    $ k) X8 l* c& `7 b8 R3 d, {4 |, y! a$ T! B: A; V* p; g: u4 T
    用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。6 z& I( M2 @* h! M( `+ R1 e$ O
    中文名 最短路径
    ' W' ~4 k* v* ^& q* h特点 以起始点为中心向外层层扩展: V5 h9 \+ T; E' }6 ~/ U2 n3 b8 _
    性质 一个经典算法问题5 @% [4 b7 k$ N9 y" a
    解决方法 Dijkstra算法A*算法  Q5 ~' p% s7 D& o' N7 X7 i

    : m( ^" g, B) p# t. f概述# Y, W' s' o8 j1 M- ]; J% B5 F

    ! c# C& ?- H4 \, p最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:% I4 C( h) J; M! K" ^& b
    确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。
    " O0 J1 B% F1 W' v9 C确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
    - S1 \( d  }/ S5 j- _& }" D确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。7 }" A. C2 y  z6 r2 p& T4 H
    全局最短路径问题 - 求图中所有的最短路径。
    ) i" e' n, {; L( g) R  ^) c  Z2 |
    ////////////////////////////////////////////////////////////
    1 i2 _5 A; \7 {; j; j* i$ z* @& K& b9 n8 ^  O+ u
    最短路径算法小软件V5.0' a7 Z3 X, D# [
    2018年6月 * a& r- x# M. @" X
    作者:李庚子李丙寅(李均宇)
    , ^7 W% Y1 v- j, {/ s, [4 QQQ:165442523
    1 n2 }9 t  N% F* e, y" K( TEMail:165442523@qq.com  + z0 p+ g1 ]. N2 A
    http://www.okmyok.com/lisoft.htm
    * t) M* ^* `8 J( F% c) R4 Z5 w; |/ z  }1 \) e
    下载地址:
    1 d. [- c8 U5 \; s( V, {- vhttps://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg
    7 L: v7 u9 Y/ Y( ?4 c$ u# P 最短路算法小软件3.jpg
    0 x6 Y2 V' a  d9 {- \
    " z5 p, L6 l6 R; Z# ]/ E. d8 k# A
    , ^0 U& n* m" D% B/ N 最短路算法小软件2.jpg ' j# T: X* ?6 t( w7 U

    ! ?) {9 w" G9 G6 A* I  H1 ?2 W7 N5 [  s1 n3 h
    最短路径算法小软件5.0EXE.zip (3.38 MB, 下载次数: 1)
    # @, ~0 V& i3 l' g9 z9 `/ C+ ?: i
    + [% z+ O2 c  r  m# E
    最短路算法小软件1.jpg . b  l9 U% C/ t# x4 B
    / D, e2 E2 M  m+ Z
    & V) |1 L9 K# E3 M8 C* `/ ]

    8 f6 c, m" m- ?  G6 {0 }( |
    , ]4 I5 v% E- ^+ s7 S' G( e, G1 s# g1 s3 ?- h/ E1 g/ \9 |

    8 E) u' a0 q% M- z/ n' v6 N, }4 Z9 H
    0 w9 i9 h# Q, [9 b" X- k" G

    # T' N9 L* L1 [$ O) ~( [- K
    5 R. L7 {! M0 x; p; f  U0 H% K  v# x' c
    % W1 j' u$ G% E' F
    3 N0 Y& k' _( ?# R; I

    9 o4 z" k  g# g1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。5 o! x" _0 j9 U$ a/ \# H2 f: ?$ L
    为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。
    6 O; L0 }/ H! I; [& T, O' B用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。7 p  L- X7 B( x6 Y
    如果你要多个项目,可以COPY多个本软件所在文件夹使用。6 H3 F9 B0 N$ l; C6 I
    2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。! D8 @$ M3 `5 ?3 l: E) A, A3 G$ }
    3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。
    7 r2 r1 {5 k* V& n. _4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。
    + d+ e- l/ }  s( T5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。
    0 }6 q" \4 u! B$ M/ X) j' U( T$ ?3 ^% y. h, ^7 |6 n( R: [3 n
    % y* K. u/ B7 S/ N
    本次升级到5.0主要修改如下:" u- z- U% ^7 i, k2 ]
    1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。
    4 ?5 u2 O/ d& ~; I' _) \2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。
      l4 d3 f5 }' u8 Y4 |8 w3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。% ]: b3 Z9 h+ L
    4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。1 {1 R. H( K, C$ F
    5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。
    ; y3 Q+ N1 d6 Z; _: @
    ! u& h+ T- e6 m( V8 k) r  E升级到4.0时主要修改如下:1 L( j9 ^. |* e1 [. k, ?
    1。更正了算法上的一个BUG。
    ! n. P( z0 M2 |4 M9 X2。边长由只可以为整数升级为可以为两位小数。; I$ O2 r7 N& J7 k2 ~4 K' s' V
    3。增加了可以保存运算结果,下次不用再运算的功能。
    / f. l6 {/ M; I& E4 ?4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。
    ( _7 w! K' q, j; ?6 D5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。
    8 |' A1 Q$ L! B6。改正了设置起点和终点的小BUG,增加了进度条显示。
    3 Z% F* R9 L$ F: A3 W7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。7 T4 n- C5 ]$ Q+ u# v0 ~

    ; @2 F: ^9 O5 C5 m2 E: T1 O作者的个人网站:http://www.okmyok.com/lisoft.htm
    8 x# h' t) C/ N. ~上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。
    & [: t4 |8 W5 f上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。
    " ~2 w" V. V- r2 U还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。
    2 t- E. w! x# K( \还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。
    : }5 I% u8 G1 m& C5 V# a5 S3 O还有作者开发的表达式求值的计算器,可以层层括号等等。。。
    5 `" V) e  q0 s7 Y8 n. [
    9 V( c. P& D$ u/ u. p3 H" S我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。% @* A( ]. p: L) ?5 c0 W6 ~

    . f& |# Z( \  ]; J2 i
    * s' f1 n3 S3 w! y2 R  D( ~1 K8 d% x. U/ k( V

    ; z& {' f0 G; ]  d# T( k; q) S' e  n2 m$ N3 a# p3 ?# Q
    ' I2 \2 S9 {* ^$ K

    # P7 h8 L6 U4 q: P. L) y* j, _9 w7 ~
    6 x1 X9 p, Z+ s& j) O: @! w( @
    - C) Q9 `0 I. D# d! q/ U
    0 U  F: d, V+ }; b
    4 a. |% g% s( I+ }

    8 {5 q/ X. P2 I6 N: W9 Z4 x
    $ }5 `3 b  H, U8 z( R+ y  V; x) c6 F6 r9 y0 a7 Y8 }0 Y

    - c( a: i" `" C5 G2 h$ F; t4 V% T: k- g3 ?# D  t

      C; z% V$ o) G. _& f4 G& y) H6 N) f9 c+ a$ Y4 O1 n! |' H
    9 \0 |0 O' ]+ n. }+ h; n6 D+ @
    : A3 E) F' A* P1 c: H
    , K- ]( E; |+ C

    2 ~/ S8 h+ q( c/ ^5 h: q/ L/ H3 l6 h/ Y1 K3 r
    . o# F7 S  `3 H' R$ h8 |8 p% x
    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 05:13 , Processed in 0.673614 second(s), 54 queries .

    回顶部