图论算法基础之计算两点间最短路径（三种算法的介绍）含Excel内的动画演示！

lee1892 · 发表于 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算法

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

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

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

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

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

lee1892 · 发表于 2012-12-28 15:43

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

正确的Dijkstra算法

正确的描述

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

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

如果用伪代码来描述的话，则形如：

Sub Dijkstra（节点集合，起始点，Optional 终点）
For Each 节点 In 节点集合
节点.距离 = 无穷大
节点.前驱节点 = 未知
Next
起始点.距离 = 0
临时集合 = 节点集合
Do While 临时集合.数量 > 0
当前节点 = 提取距离最短（临时集合） ' 提取是指获得并从集合中删除
If 定义了终点 And 当前节点 = 终点 Then Exit Do ' 已经找到到达终点的最短路径，可以退出
For Each 所连接节点 In 当前节点.连接节点集合
If 所连接节点.距离 > 当前节点.距离 + 获得距离（当前节点，所连接节点） Then
所连接节点.距离 = 当前节点.距离 + 获得距离（当前节点，所连接节点）
所连接节点.前驱节点 = 当前节点
End If
Next
Loop
End Sub

复制代码

lee1892 · 发表于 2012-12-28 15:50

本帖最后由 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楼

三坛老窖 · 发表于 2012-12-28 20:09

本帖最后由三坛老窖于 2013-1-13 11:57 编辑

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

lee1892 · 发表于 2012-12-28 20:29

哦，二叉堆吗。等着学习^_^

三坛老窖 · 发表于 2012-12-28 21:48

加了部分注释，现在发上来，供有兴趣的坛友探讨这个算法。

最短距离（半成品）.rar (81.04 KB, 下载次数: 420)

lee1892 · 发表于 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的设置，我个人认为这种方式是不正确的，其违背了一个数据结构的原则。在原始数据中保留指向寄存器的链接，这种做法是不对的或是不被提倡的。正确的做法应该是所有参与计算的变量都指向原始数据的地址，而不是反之。

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

Private Sub Heapify_up(Q() As Long, ByVal i As Long)
Dim j&, swap&
If i > 1 Then
j = Int(i / 2)
If uaVertex(Q(i)).MinDistance < uaVertex(Q(j)).MinDistance Then
swap = Q(i): Q(i) = Q(j): Q(j) = swap
uaVertex(Q(i)).QueuePoint = i
uaVertex(Q(j)).QueuePoint = j
Heapify_up Q, j
End If
End If
End Sub
Private Sub Heapify_down(Q() As Long, ByVal i As Long, ByVal qLength As Long)
Dim j&, swap&
If 2 * i > qLength Then
Exit Sub
ElseIf 2 * i = qLength Then
j = 2 * i
Else
If uaVertex(Q(2 * i)).MinDistance < uaVertex(Q(2 * i + 1)).MinDistance Then
j = 2 * i
Else
j = 2 * i + 1
End If
End If
If uaVertex(Q(j)).MinDistance < uaVertex(Q(i)).MinDistance Then
swap = Q(i): Q(i) = Q(j): Q(j) = swap
uaVertex(Q(i)).QueuePoint = i
uaVertex(Q(j)).QueuePoint = j
Heapify_down Q, j, qLength
End If
End Sub

复制代码

1、建议充分利用VBA提供的数据类型，比如这里用集合肯定会比数组方便很多，可以直接删除、插入，而不是交换。
2、建议学习二叉堆的最小堆的概念，真实的构建二叉堆数据结构，而不是在一个线性的数组或表中通过折半查找对比来调整前后次序。个人看法，即便仅仅使用一个二叉查找树可能也比程序中的方法会好一些，至少让人思路很清晰。
3、实际上在3楼的代码中，加几个变量就可以避免在临时节点集合中提取最近距离节点时的那个循环。比如，一个变量 Min1st 是临时集合中的最近距离节点的地址，一个 Min2nd 是次近距离节点的地址，一个 Min3rd 是第3近的。值得注意的是，临时集合使用的字典对象构建的，实际上是个散列表（哈希表）的使用，正是由于这个的关系，从而使得其不再需要另外构造二叉堆之类的数据结构供查找最近距离节点。
注：仔细琢磨了一下，第3点有问题，可能还是需要建立一个有序的队列或二叉堆之类的，以加快获得最近距离节点的地址。

以上，供参考、讨论。

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

lee1892 · 发表于 2012-12-29 15:20

本帖最后由 lee1892 于 2012-12-29 16:48 编辑

作了个动画，呵呵~

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

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

lee1892 · 发表于 2012-12-30 12:33

本帖最后由 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]

Moneky · 发表于 2012-12-30 12:45

多谢楼主辛苦分享，收藏学习。

		自动登录	找回密码
密码			免费注册

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

评分

正确的Dijkstra算法

正确的Dijkstra算法

评分

Floyd-Warshall算法

最新热点 /1

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

评分

正确的Dijkstra算法

正确的Dijkstra算法

评分

Floyd-Warshall算法

最新热点 /1

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