QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3308|回复: 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
    ' h' ~# e3 ^. {" b* @( ^2 g
    百度百科:最短路径
    , n; Z4 ?/ e( E+ J: q: U6 f
    . [( `8 k) Z& g2 E. g用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
    9 C$ d; t* V2 i, t8 S. Z中文名 最短路径
    9 U$ R- t5 I  l/ y1 ~1 W特点 以起始点为中心向外层层扩展( ~* q" B# x5 C1 w7 G: F
    性质 一个经典算法问题
    ) I- m3 u, [# j5 Q# [解决方法 Dijkstra算法A*算法
    & j# J0 B, M+ _+ L6 Q1 c+ q& x
    : F# V# N, U) ?7 s% ]概述9 U$ e* D. g) Q% P4 p2 E

    - o3 T/ ?! k2 Y* P最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:
    - [2 Z; o4 f5 Z; B9 @: P& K' L1 L2 x确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。
    & R2 S% L  Z- o5 s) y# O" Z/ b; g确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。* m) v0 G2 v7 U+ y) Z. u  F
    确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。6 s. z7 k8 j& \0 P/ J
    全局最短路径问题 - 求图中所有的最短路径。2 ^4 `) u" U3 \4 B* i1 p! B5 i3 m
    9 q2 m/ @& u: g9 j! @
    ////////////////////////////////////////////////////////////  B4 P' Z; ]! E- c# P

    ; W- _6 l! A( S最短路径算法小软件V5.0) }) C) U# k$ W9 v' [9 X7 _
    2018年6月 5 U; Y' w4 x4 R; T% L
    作者:李庚子李丙寅(李均宇)
    + M' ?& {) o1 I9 V0 aQQ:165442523
    ; M* P0 \' N! l; IEMail:165442523@qq.com  / F& ~8 d- E/ F9 y& u% t# ?
    http://www.okmyok.com/lisoft.htm
    8 r! S7 A' A8 e  B; w2 f9 B, l
    3 A$ n+ [  Q$ q8 f下载地址:
    2 q& ?6 U. F: i/ v3 Y( Y) [https://pan.baidu.com/s/1dY_9GQC3G435d2nke2WoQg2 ]7 g; K- o4 l. J
    最短路算法小软件3.jpg 0 d' h3 d% w1 a2 U
    ' q1 l  Y! i( K' C. C
    ( ^8 |% m: q# r- ]! \, }- h, M
    最短路算法小软件2.jpg - f7 V6 ^' I& N. {

    - }+ W" w* K& `) z8 w, b
    / H% Q) P* _% V, ]/ ?) C' l  @ 最短路径算法小软件5.0EXE.zip (3.38 MB, 下载次数: 1) $ m& C4 e- s5 p- H
    * e+ Z: }9 J8 l0 g
      }+ M% }5 P1 [, ?  u+ Z% \  u0 d
    最短路算法小软件1.jpg " ^1 u4 s  i9 x) K+ L
    # x" Q6 [) D5 m3 n# {
    0 Z& g7 b, c$ M' q5 ~5 u: A7 }# K

    # z. e! J* D+ `9 X0 ^! \" R& S& g3 W' {
    ' a+ n3 E8 B: o: R

    0 d+ \) Y5 v4 k8 X+ b) X0 E! ~1 ?2 k3 y+ x" h- |

    ) G. h& ^1 u$ |' \7 z8 g
    8 c3 d* v( j" H+ I% r5 y0 Z; e0 `) V9 V
    : t0 `9 p2 Z/ l7 n/ D% T
    / m1 T) \$ O5 t, l$ q9 l6 n, N# h
    . v6 w4 c8 b! v; B/ L6 O' r: p' C
      l# G" b: I: E& T
    1.本软件为小软件,不想为项目管理花过多时间,例如要新增一个项目,又删除或修改一个项目等。; j# q9 W. {( l" ~
    为此,本小软件只有两个默认的项目,一个为演示项目,一个用户当前正在使用的项目,不能增也不能减。3 l$ t7 k$ m7 N2 X8 _. q, u
    用户可以清空当前的用户项目,从而使用自已自定义的项目。先输入质点数等等。
    * C) N% r  d# o+ f: L1 L/ ?) ?如果你要多个项目,可以COPY多个本软件所在文件夹使用。1 X* j- u  @7 S5 b: R& \
    2.初始化粗略质点坐标时,边长不作校验,例如,三角形两边长之和本应大于第三边,但是输入时三角形两边长之和小于第三边,将不作检验,所以请手工确保原始数据的正确性。# V* `- Z3 Z) K; Z+ h
    3.质点坐标是屏幕像素坐标,left,top,纵坐标向下不是向上,与数学上的纵坐标方向相反。% }+ \- K8 N- |5 J9 h/ t% ^4 }
    4.坐标为屏幕像素坐标,所以只能整数,边长为两位小数,如果四舍五入导致的出错不作处理。! J3 h' H; m4 d: ~8 V
    5.注意,用户要先点击“注意:先清空用户项目!!!”才可以自定义自已要用到的顶点数的改变。/ Y/ [5 B8 s+ U) C2 i2 l
    - w, \' n/ A1 e  G" ~9 A$ ^

    6 ^9 u- }2 a: u3 a本次升级到5.0主要修改如下:
    ) a3 ^9 x( q# E; C, f8 v7 `) p8 |1。边线条改成灰色,当鼠标移到边线条时,高亮显示边与边长数字,这对于边长数字重叠时有用。/ i; f* A# s0 K6 U4 Y* u9 x6 J/ ?
    2。点坐标可以超出屏幕范围自动产生滚动行,但点坐标不可以为负数。5 B6 D* H& X* d$ k
    3。增加了SPFA算法,来处理边长为 0 或者负数的情况,但SPFA当有负环时无解。
    & Q' ]/ y% h( Q* L: A8 `' W6 ~4。增加了处理负环的两个新算法,这两个算法皆为作者自创的新算法,一个点与边都不可以重复,另一个点可以重复,边不可以重复。
    ! C* r1 Z$ ~% w9 U! X# }4 J4 g5。边长为负数时最好有方向单向,一般不允许双向或无向。或者每条双向无向的负数边,可以每次取单向,如此组合出所有情况,来求最短路径,再在所有最短路径中再取其最小值。这个组合的算法暂不处理,由用户手工处理。1 J8 W. W# n, W0 J8 S9 g' W

    8 i0 z7 `  [( @1 {; w$ A升级到4.0时主要修改如下:+ ^& J# s" s: `$ O
    1。更正了算法上的一个BUG。% O6 W/ x) o+ {* Y( W
    2。边长由只可以为整数升级为可以为两位小数。3 P# J7 B, r0 q( `
    3。增加了可以保存运算结果,下次不用再运算的功能。; E# j, V* _+ V% b: @8 M
    4。增加了可以列举所有最短路径的功能,不止一条最短路径时有用。) K. g( w1 \: v0 h; w9 W3 V
    5。增加了边向量功能,边向量方向可以双向或无向,或序号从小指向大,或序号从大指向小,三种选择。
    + Y* m" W2 f. |' {0 ]6。改正了设置起点和终点的小BUG,增加了进度条显示。: g. g) ?, @8 |- B
    7。增加了可以鼠标拖动质点,所相关联的边相应变动的功能。
    9 [* ~- H* ]/ }$ {$ W* S6 J
    2 v% ?/ t# J" K; q, r) x作者的个人网站:http://www.okmyok.com/lisoft.htm; E/ B/ C9 x, b) g0 I
    上面有作者个人开发的所有软件,全免费下载。免费但不开源,源代码要收费。
    - ^  S) L0 C, J0 O* `. s9 p& s上面有作者个人开发的中医五运六气和子午流注软件,有PC电脑版,安卓版,ASP网页版等。, ~* Q9 Y4 ~! H/ v
    还有作者开发的“行星财务”安卓软件,是一款在安卓设备上运行的真正意义上的财务软件,不是记录个人收支的个人记账,在安卓手机上可以运行,掌上财务软件。
    0 s' `  e0 n6 R0 g. z# p还有作者开发的TSP算法小软件,或叫旅行商问题,不了解者可以百度。" x7 I/ @& U+ _8 ^0 f) q
    还有作者开发的表达式求值的计算器,可以层层括号等等。。。
    8 B/ B; J: L4 E% z* x$ X7 p, I; P6 K  Z7 Y* m9 F
    我的软件全免费,无广告,无须权限,无须上网,无时间和任何功能限制,纯绿色不污染系统,不体积庞大。。。
    # y' r: A& `% R- H9 z( U9 S, i0 {5 q& o( n- q/ l2 h3 g. J
    5 g% S1 D* w0 V$ _

    # S5 e! g; E7 d" c, \" B! b0 R, U- a8 E. N8 \
    1 S6 f' W+ p, Y* s

    9 k" Q) W$ h/ X. w0 A
    ; u4 v. [: o" k0 W  I. ~! O  L& `7 Q5 p/ }; S! d$ p7 S
    0 r, T$ g8 ~8 E7 Y0 G/ ~: R6 \! t- a8 Y
    1 v" A+ ^8 I! x1 z- z; N( a# j0 M

    * R! `+ F% R" D; r4 o
    ) [4 x0 a* M6 w. K, ?# c& @8 C2 u  ~1 C! l& L/ j7 [
    : E+ P, t. f# t, X4 e0 w
    ; t) [, m' \  c1 w3 m: w9 ?8 K
    9 {% _8 F0 ^, E( h; @% `& ^0 @

    - h. s7 v" r8 ^) j( P( u( [" J. {" r5 x6 N" l+ o
    8 u( R: d$ @2 ~9 B& _0 S
    8 f% L; {* b0 X% W) g( q0 L8 p3 u

    ; j4 v* R, L4 I2 o( P2 S6 ?
    % B* o  H0 `4 U. j" _6 X2 N8 K& _! `" I, g% ?/ L/ r

    1 @* X/ Z9 E: Q$ t1 \: G4 q, A6 A: S# L; o5 ?5 S% }
    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 18:22 , Processed in 0.711775 second(s), 53 queries .

    回顶部