ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 EH云课堂直播课程免费学 打造核心竞争力的职场宝典
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 21648|回复: 33

[原创] 图论算法基础 之 计算两点间最短路径(三种算法的介绍) 含Excel内的动画演示!

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2012-12-28 15:18 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:
本帖最后由 lee1892 于 2012-12-31 21:20 编辑

On 121231:
    图论的数据结构基础知识,见15楼
    正确的FloydWarshall算法的实现,见17楼
    Bellman-Ford算法的实现,见18楼

On 121230:
    突然意识到HHAAMM描述的算法根本不是Dijkstra算法!! 而是弗洛伊德算法(Floyd-Warshall算法)!!!
    详细见9楼

On 121229
    老窖给出了一个优化方案,使用了二叉堆以加快寻找临时节点集合中距离起始点距离最小的节点,在 6 楼
    我个人对其代码的意见在 7 楼

==================================================================

正确的Dijkstra算法

动画演示Dijkstra算法

动画演示Dijkstra算法

相关链接:
HHAAMM 的 用dijkstra算法求最短路径
HHAAMM 的 最短路径—dijkstra算法详解
云牧帆 的求助贴 以及 三坛老窖 给出按上述帖子方法的解答 高手相救,双向递归求长

本想放在我的数据结构帖子里的(VBA编程技巧 之 浅谈数据结构),但想想这是一个单独的算法的事情,所以另外开贴了。

HHAAMM 在其贴中用表格的方法描述了Dijkstra算法(实际上是弗洛伊德算法)使用表格的直观表现,但在实际使用中如果也这样操作,无疑是非常非常不可取的。来看其实现代码:
[code=vb]
这段代码引用了毫无意义,删了。
[/code]
HHAAMM 真实的构建了一个节点间的距离表,并真实的使用这个表来计算,其循环量是 节点 数量的 3 次方!如果有100个节点,岂不是要循环100万次,而不论节点间是否存在连接?!

这种方式无疑是对算法本身的曲解,需要明确的是Dijkstra算法是基于路径寻找的,而不是节点!




补充内容 (2013-10-14 18:26):
相关链接:[原创] 图论算法基础 之 浅谈骑士巡逻问题(神经网络算法)与哈密顿路径

最短路径-Dijkstra算法的正确实现 By Lee1892.rar

22.49 KB, 下载次数: 723

最短路径-Dijkstra算法的正确实现 Excel内的动画演示 By Lee1892.rar

27.88 KB, 下载次数: 624

最短路径-FloydWarshall算法的正确实现 By Lee1892.rar

16.25 KB, 下载次数: 432

最短路径-BellmanFord算法的实现 By Lee1892.rar

18.86 KB, 下载次数: 367

评分

参与人数 4鲜花 +10 收起 理由
micch + 2 感谢帮助
liucqa + 3 值得肯定
三坛老窖 + 2 很好!思路很清晰。
灰袍法师 + 3 百尺竿头更进一步,楼主值得我们学习。

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-12-28 15:43 | 显示全部楼层

正确的Dijkstra算法

本帖最后由 lee1892 于 2013-1-4 15:00 编辑

正确的Dijkstra算法

正确的描述

Dijkstra算法是通过给每个节点保留计算循环中所找到的最短路径来工作的。

初始时,起始点的路径长度值被赋为 0 (即起始点到起始点的距离),同时将其它所有 节点 的路径长度设为 无穷大,代表不知道其到达起始点的路径,然后起始点开始搜索。
前面说过Dijkstra算法是基于路径的搜索,其对 当前节点 所连接的 其它节点 进行遍历访问,如果 其它节点 中保留的路径长度 大于 当前节点 + 两者的距离,那么说明 后者 是更短的距离于是保留该值,同时保留 当前节点 为其 前驱节点 供结束后获取路径使用。
遍历所有可路径后(算法经过组织可以保证路径只被搜索一次),所有节点中的路径长度值都是到达 起始点 的最短长度,而其保留的前驱节点则是最短路径中的上一个节点。

如果用伪代码来描述的话,则形如:

  1. Sub Dijkstra(节点集合,起始点,Optional 终点)
  2.     For Each 节点 In 节点集合
  3.         节点.距离 = 无穷大
  4.         节点.前驱节点 = 未知
  5.     Next
  6.     起始点.距离 = 0
  7.     临时集合 = 节点集合
  8.     Do While 临时集合.数量 > 0
  9.         当前节点 = 提取距离最短(临时集合) ' 提取是指获得并从集合中删除
  10.         If 定义了 终点 And 当前节点 = 终点 Then Exit Do ' 已经找到到达终点的最短路径,可以退出
  11.         For Each 所连接节点 In 当前节点.连接节点集合
  12.             If 所连接节点.距离 > 当前节点.距离 + 获得距离(当前节点,所连接节点) Then
  13.                 所连接节点.距离 = 当前节点.距离 + 获得距离(当前节点,所连接节点)
  14.                 所连接节点.前驱节点 = 当前节点
  15.             End If
  16.         Next
  17.     Loop
  18. End Sub
复制代码

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-12-28 15:50 | 显示全部楼层

正确的Dijkstra算法

本帖最后由 lee1892 于 2013-1-4 15:01 编辑

正确的Dijkstra算法

实际的例子

以HHAAMM在其贴中给的例子为例,设置自定义数据类型和节点集合如下:[code=vb]
Private Type NODE_INFO
    Name As String ' 节点名称
    Connects() As Long ' 可连接的节点地址,节点数组的下标
    Distances() As Double ' 与所连接节点的距离
    Previous As Long ' 查找时的前驱节点
    TotalDist As Double ' 查找时距离起始点的总距离
End Type

Private aNodes() As NODE_INFO ' 节点数组
Private cNodeHash As Collection ' 集合模拟散列表,用名称索引节点数组下标
[/code]而实现Dijkstra算法的代码则是:[code=vb]
Private Sub Dijkstra(sBegin$, sEnd$)
    Dim dTempNodes As Object, aItems
    Dim i&, j&, nIndex&, nNodeIndex&
    ' 使用字典对象建立临时节点集合
    Set dTempNodes = CreateObject("scripting.dictionary")
    For i = 1 To UBound(aNodes)
        aNodes(i).Previous = -1 ' 标记为未定义
        aNodes(i).TotalDist = -1 ' 负值代表无穷大
        dTempNodes(aNodes(i).Name) = i
    Next
    aNodes(cNodeHash(sBegin)).TotalDist = 0 ' 起始点的初始总距离为 0,即起始点到起始点的距离
    Do While dTempNodes.Count > 0 ' 临时节点集合为空则退出
        ' 总是从临时节点集合中获得总距离最小的那个节点作为当前节点,并从临时集合中删除
        aItems = dTempNodes.Items: nIndex = LBound(aItems)
        For i = LBound(aItems) To UBound(aItems)
            If aNodes(aItems(i)).TotalDist >= 0 Then
                If aNodes(aItems(nIndex)).TotalDist < 0 Then
                    nIndex = i
                ElseIf aNodes(aItems(i)).TotalDist < aNodes(aItems(nIndex)).TotalDist Then
                    nIndex = i
                End If
            End If
        Next
        nNodeIndex = aItems(nIndex)
        ' 此处可以添加判断,如果获得的当前节点是终点的话,即可退出循环
        ' 否则会遍历所有节点,并使得所有节点都保留了至起始点最短路径的前驱节点和总距离
        If aNodes(nNodeIndex).Name = sEnd Then Exit Do
        dTempNodes.Remove aNodes(nNodeIndex).Name
        ' 对于当前节点,遍历其可连接的节点(不在临时集合中)
        ' 如果其可连接的节点的总距离大于当前节点的总距离+两者之间的距离,
        ' 则将其更新为后者,并将该节点的前驱节点设为当前节点
        With aNodes(nNodeIndex)
            For j = 1 To UBound(.Connects)
                If Not dTempNodes.exists(aNodes(.Connects(j)).Name) Then GoTo NEXT_CONNECTION
                If aNodes(.Connects(j)).TotalDist < 0 Then
                    aNodes(.Connects(j)).TotalDist = .TotalDist + .Distances(j)
                    aNodes(.Connects(j)).Previous = nNodeIndex
                ElseIf aNodes(.Connects(j)).TotalDist > .TotalDist + .Distances(j) Then
                    aNodes(.Connects(j)).TotalDist = .TotalDist + .Distances(j)
                    aNodes(.Connects(j)).Previous = nNodeIndex
                End If
NEXT_CONNECTION:
            Next
        End With
    Loop
    dTempNodes.RemoveAll
    Set dTempNodes = Nothing
End Sub
[/code]那么对于查找结束后的路径的获得,则是由终点通过保留的前驱节点向起始点搜索,代码如下,其中Initialize是数据初始化过程,Terminate则是清空全局变量用的:[code=vb]
Private Sub btnFind_Click()
    Dim nEnd&, sRoutine$, dDistance#
    If cNodeHash Is Nothing Then Call Initialize
    Call Dijkstra([G10], [G11])
    ' 从终点按前驱节点链接到达起始点即所查找的最短路径
    nEnd = cNodeHash([G11])
    sRoutine = aNodes(nEnd).Name
    dDistance = aNodes(nEnd).TotalDist
    Do
        nEnd = aNodes(nEnd).Previous
        sRoutine = aNodes(nEnd).Name & "->" & sRoutine
        If aNodes(nEnd).Previous < 0 Then Exit Do
    Loop
    [G13] = sRoutine & " " & Round(dDistance, 2)
    Call Terminate
End Sub
[/code]附件在1楼

TA的精华主题

TA的得分主题

发表于 2012-12-28 20:09 | 显示全部楼层
本帖最后由 三坛老窖 于 2013-1-13 11:57 编辑

这个题目正是我目前求解的,本想以此为题,在2012结束之前,开个处女贴,不想被老兄抢先了……感到些许的遗憾!
不过从解此题的时间效率来看,楼主是将郝版的O(n^3)的提升到了O(n^2),而我目前的代码,总体思路与你的一样,不同的地方在选取下一个当前节点(我称之为:活动节点)的方法,我在代码中用到了邻接表、优先队列(堆)的技巧,代码虽比不上你的简洁,但时间复杂性却降到了O(nlogn+m)(n为节点数,m为边数)。既然你已就此题开贴了,我想就借你的宝地,将我的半成品拿出来,供坛中朋友探讨。
(附件待我略作整理后发上来)

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-12-28 20:29 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2012-12-28 21:48 | 显示全部楼层
加了部分注释,现在发上来,供有兴趣的坛友探讨这个算法。
最短距离(半成品).rar (81.04 KB, 下载次数: 216)

评分

参与人数 1鲜花 +2 收起 理由
lee1892 + 2 值得肯定,谢谢参与讨论!

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-12-29 10:48 | 显示全部楼层
本帖最后由 lee1892 于 2012-12-30 22:31 编辑
三坛老窖 发表于 2012-12-28 21:48
加了部分注释,现在发上来,供有兴趣的坛友探讨这个算法。

非常感谢参与讨论!文件作的很漂亮~
我只能看到你的代码,没法运行你的程序。

总体而言,我个人认为你把数据结构复杂化了,从而导致在使用时很容易把思路弄混乱。程序的申明部分如下:
[code=vb]
Public Type Vertex
    Code As String          '节点符号
    MinDistance As Long     '起点到该点的最短距离
    Previous As Long        '起点到该点的最短距离的途径中的上一个节点的指针,指向【节点表】
    FirstEdge As Long       '通过该节点的第一条边的指针,指向【边表】,通过【边表】的Next属性获取该节点其余边的边指针
    Discovered As Boolean   '该节点是否已被探查
    QueuePoint As Long      '该节点在优先队列(堆)中的位置指针
End Type
Public Type Edge
    Length As Long          '边的长度
    Vertex As Long          '邻接节点的指针,指向【节点表】
    Next As Long            '与该边拥有同一个节点的下一条边指针所在的位置,指向【边表】
End Type
Public Type EdgeData
    Vertex1 As String       '节点1
    Vertex2 As String       '节点2
    Length As Long          '边的长度
End Type
Public Const VERTEX_WIDTH As Long = 30
Public Const VERTEX_HEIGHT As Long = 30
Public uaEdge() As Edge         '邻接表之边表
Public uaVertex() As Vertex     '邻接表之节点表
[/code]

可以看到,程序用了两个数组来分别存放节点和节点间的连线(即边)的信息,整个数据结构是扁平化的。两个数组之间互相来回链接,我相信在编写调试程序时会很让人头疼的。当然,这种方式是一种邻接表最为直观的组织方式,但实际上在我3楼的代码中也同样使用了邻接表,不过是另一种方式而已,即在每个节点中保存了与其邻接的节点链接数组。这带来一个很大的好处,所有的链接都是指向节点的,而且数据的组织是使用链表的方式,套句当前的流行语:达到了和谐、统一^_^

再有就是,我个人的观点,能用For .. Next语句循环总好过用Do .. Loop的形式,由于3楼代码中的数据结构的设置,其中的外循环也可以改写为For ... Next的。

再来看节点的定义中这个QueuePoint的设置,我个人认为这种方式是不正确的,其违背了一个数据结构的原则。在原始数据中保留指向寄存器的链接,这种做法是不对的或是不被提倡的。正确的做法应该是所有参与计算的变量都指向原始数据的地址,而不是反之。

最后关于程序设置的队列,我的理解是用来快速找到临时节点集合中的距离起始点最近的节点而设置的。看程序中的队列调整代码,下述代码实现了数组模拟二叉堆,值得学习。

  1. Private Sub Heapify_up(Q() As Long, ByVal i As Long)
  2.     Dim j&, swap&
  3.     If i > 1 Then
  4.         j = Int(i / 2)
  5.         If uaVertex(Q(i)).MinDistance < uaVertex(Q(j)).MinDistance Then
  6.             swap = Q(i): Q(i) = Q(j): Q(j) = swap
  7.             uaVertex(Q(i)).QueuePoint = i
  8.             uaVertex(Q(j)).QueuePoint = j
  9.             Heapify_up Q, j
  10.         End If
  11.     End If
  12. End Sub
  13. Private Sub Heapify_down(Q() As Long, ByVal i As Long, ByVal qLength As Long)
  14.     Dim j&, swap&   
  15.     If 2 * i > qLength Then
  16.         Exit Sub
  17.     ElseIf 2 * i = qLength Then
  18.         j = 2 * i
  19.     Else
  20.         If uaVertex(Q(2 * i)).MinDistance < uaVertex(Q(2 * i + 1)).MinDistance Then
  21.             j = 2 * i
  22.         Else
  23.             j = 2 * i + 1
  24.         End If
  25.     End If        
  26.     If uaVertex(Q(j)).MinDistance < uaVertex(Q(i)).MinDistance Then
  27.         swap = Q(i): Q(i) = Q(j): Q(j) = swap
  28.         uaVertex(Q(i)).QueuePoint = i
  29.         uaVertex(Q(j)).QueuePoint = j
  30.         Heapify_down Q, j, qLength
  31.     End If
  32. End Sub
复制代码
1、建议充分利用VBA提供的数据类型,比如这里用集合肯定会比数组方便很多,可以直接删除、插入,而不是交换。
2、建议学习二叉堆的最小堆的概念,真实的构建二叉堆数据结构,而不是在一个线性的数组或表中通过折半查找对比来调整前后次序。个人看法,即便仅仅使用一个二叉查找树可能也比程序中的方法会好一些,至少让人思路很清晰。
3、实际上在3楼的代码中,加几个变量就可以避免在临时节点集合中提取最近距离节点时的那个循环。比如,一个变量 Min1st 是临时集合中的最近距离节点的地址,一个 Min2nd 是次近距离节点的地址,一个 Min3rd 是第3近的。值得注意的是,临时集合使用的字典对象构建的,实际上是个散列表(哈希表)的使用,正是由于这个的关系,从而使得其不再需要另外构造二叉堆之类的数据结构供查找最近距离节点。

注:仔细琢磨了一下,第3点有问题,可能还是需要建立一个有序的队列或二叉堆之类的,以加快获得最近距离节点的地址。

以上,供参考、讨论。

===============
On 121230
又复习了一下基础知识,是我自己没看明白,老窖确实使用了二叉堆,很好!^_^


TA的精华主题

TA的得分主题

 楼主| 发表于 2012-12-29 15:20 | 显示全部楼层
本帖最后由 lee1892 于 2012-12-29 16:48 编辑

作了个动画,呵呵~

很直观啊~
===============================

有机会,再聊聊Bellman-Ford算法~~

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-12-30 12:33 | 显示全部楼层

Floyd-Warshall算法

本帖最后由 lee1892 于 2013-1-4 15:01 编辑

Floyd-Warshall算法

其算法的表现可以去看1楼提到的HHAAMM的两个贴子,虽然其实现的代码由于没有使用正确的图的数据结构,而显得很奇怪,但不妨碍我们理解这个算法。

弗洛伊德算法比较了图中任意两个节点间所有可能的路径,其时间复杂度是N(节点数量)的3次方。其好处是可以获得任意两点间的最短距离的长度,但找出路径则比较费劲,需要额外的空间。

实现的伪代码形如:
[code=vb]
构造矩阵 M(1 to N, 1 to N) 且初始值均为 ∞ ' N是节点数量
For i=1 to N
    M(i, i)=0
Next
For Each 路径 In 路径集合
    M(i, j) = 路径.长度 ' i 为该路径的起点序号,j 为终点序号
Next
For k=1 to N
    For i=1 to N
        For j=1 to N
             If M(i, k) + M(k, j)  < M(i, j) Then
                  M(i, j) = M(i, k) + M(k, j)
             End If
Next j, i, k
[/code]

TA的精华主题

TA的得分主题

发表于 2012-12-30 12:45 | 显示全部楼层
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关闭

最新热点上一条 /1 下一条

关注官方微信,高效办公专列,每天发车

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2020-2-26 09:46 , Processed in 0.477770 second(s), 23 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表