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

三坛老窖

lee1892 发表于 2012-12-29 15:20
作了个动画，呵呵~

很直观啊~

这个做得很漂亮，正是我本想要达到而没有厘清的目的。
其中有几个小小的瑕疵，提出来供你参考。
1.如果出发点与目的地之间不存在通路，即图是不连通的，运行时会出错。如能给出不通的提示则更好。
2.标记节点间距离和节点离出发地的最短距离的标签若能设成无填充色，则能使界面更清晰。
3.作为演示，节点数少了点。
-----------------------------------------------------------
另有一个问题请教：能否根据shape的连接点引用到其上的连接线？

三坛老窖

lee1892 发表于 2012-12-29 10:48
非常感谢参与讨论！文件作的很漂亮~
我只能看到你的代码，没法运行你的程序。

诚如你所言，我用了一大堆的指针，互相引用，在写代码时确实容易把思路弄乱。你所用的数据结构，可能更好一些（未能细细推敲）。
对你所提的1、2两点建议，我持保留意见。
最初在编程构想时，首先想到的也是用集合来处理，后来发现其有一个与所要达到的目的不相容的，即它不接受自定义数据类型的元素。所以，如果用它来保存节点，就没办法把整个节点的数据都放进去。再就是要从其中选取距离最小的节点，除了历遍，想不出有其他的办法。在这儿，我还是觉得用数组比用集合更合适。如果不考虑选取距离最小节点的时间效率，我同样还是会选择用数组来保存节点队列的信息。你看查看我附件中备份模块的那个过程，只要维护队首和队尾两个指针，即可达到对集合来说的插入、删除的动作。

lee1892

  2012-12-30 18:32
д· ...

全局变量的集合对象不能接受自定义数据类型是VBA的一个限制，确实比较烦人。

但换一个思路就可以了啊，完全可以只保留节点的地址(全局变量节点数组的下标)嘛，用节点的唯一名称来索引，或者干脆用地址的字符串索引。

你用到的这个Q寄存器实际上是想维护一个有序的节点临时集合，由于集合对象没有Exists方法判断是否存在某关键字，而字典对象则缺少插入的功能，所以我的建议是两个同时用。

你再想想?

==================
平板回帖又出乱码，哎...

三坛老窖

lee1892 发表于 2012-12-30 19:27
全局变量的集合对象不能接受自定义数据类型是VBA的一个限制，确实比较烦人。

但换一个思路就可以了啊， ...

如果是仅仅保留节点的地址，何必要用两个对象的组合，况且他们的组合也无法生成也个按关键字【最短距离】排序的队列，何不直接用一个数组来保存这个地址，岂不省事。

lee1892

非常感谢老窖的参与讨论！学到二叉堆的实现方式。
之前的一个问题，如果在从临时集合中获得的距离最近的点的距离值是无穷大，那么说明临时集合中剩余的点都与起始点不联通，不难吧^_^

图论的数据结构基础知识

图是一种复杂数据结构，表象的看是由一系列顶点（Vertex）和连接它们的边（Edge）构成。其抽象的数学定义则可分为如下两种：
1、二元组的定义
        图G = （V，E），V是顶点集而E是边集。
2、三元组的定义
        图G =（V，E，I），I 是关联函数，使得 I（e）=（v1，v2）。

可分为无向图和有向图。有向图中，边具有方向性，即边的所连接两个顶点不等价的分别为起点和终点。相反的，边没有方向的图则被称为无向图。

另可分为简单图和多重图。一个图如果：1、不存在重复的边，即没有两个边所连接的两个顶点相同；2、顶点不能连接自身，即每条边所连接的两个顶点不同，则被称为简单图。否则，则被称为多重图。

所有的简单图都可以用上述的二元组定义来描述。多重图则只能用上述的三元组定义描述。

对图的最为基础的操作：遍历，通常的图的遍历包括对顶点的遍历和对边的遍历。如同树的遍历一样（见我的另一个帖子：浅谈数据结构），图的遍历也可分为 深度遍历 和 广度遍历。

一个无向图的深度遍历（可使用递归或堆栈）的伪代码如下：
[code=vb]
Sub 深度遍历（顶点集合，边集合，Optional 起始点）
    If 未定义（起始点） Then
        起始点 = 获得未访问的第一个顶点（顶点集合）
        If 没找到（起始点）Then Exit Sub
    ElseIf 起始点.访问过 Then
        Exit Sub
    End If
    起始点.访问过 = True
    For Each 边 In 起始点.连接的边集合
        Call 深度遍历（顶点集合，边集合，边.另一个顶点）
    Next
End Sub
[/code]
对上面这段程序的反复调用即可完成对图的深度遍历，可思考一下图中点的连通性。

广度遍历则可使用迭代或队列，不再罗列了。

一个简单图的数据组织可通过顶点数组和边数组来建立，也可通过顶点数组和邻接表来实现如3楼。

前述的Bijkstra算法和Floyd-Warshall算法都可以用来计算无向图和有向图，但Bijkstra算法不能用来计算边的长度是负值的图（或称为边的权值），另外一个计算图中两点最短距离（或最小花费）的是Bellman-Ford算法，则也可以用来计算边的权值为负的情况。

飞翔的渔

好东西，借鉴

lee1892

FLoydWarshall的正确实现

由于1楼提到的帖子里虽然描述了弗洛伊德算法，但实际上却没有正确的用代码实现，所以另写了一个放在1楼的附件集里了。

这个算法的思维逻辑是：
最外层的 k 是扫描的顶点，内两层的 i 和 j 则是扫描的由 i 顶点到 j 顶点的路径（可能是数个边，也可能不通），如果 由 i 到 k 的路径 加上 由 k 到 j 的路径 的总长（或花费）小于由 i 到 j 的长度，则用后两者合并来取代原先的路径。

1楼附件的申明部分如下，注意保存路径部分的代码比较麻烦，实际上合并两个数组后取代，或则用字典对象或集合对象会比数组方便：
[code=vb]
Private Type VERTEX_INFO
    Name As String ' 顶点名称
End Type
Private Type EDGE_INFO
    FromVertex As Long ' 起点地址
    ToVertex As Long ' 终点地址
    Length As Double ' 边的长度
End Type
Private Type PASS_INFO
    Length As Double
    Vertex() As Long ' 所经过的数组
End Type
Private aVertexes() As VERTEX_INFO ' 顶点数组
Private cVertexHash As Collection ' 集合模拟散列表，用名称索引顶点数组下标
Private aEdges() As EDGE_INFO ' 边数组
Private aFloydTable() As PASS_INFO ' 结果矩阵，保存了图中任意两点的最短路径信息
Private dInfinite As Double ' 定义无穷大为全部边长度之和
[/code]

这里采用了顶点集合和边集合分开的方式，以便该算法的使用。另外构造了一个FloydTable用来保存结果，这是一个二维矩阵，行序号对应起点，列序号对应终点。可以看到，对于无向图而言，上下半区是对称的。

算法实现的代码如下：
[code=vb]
Private Sub FloydWarshall()
    Dim i&, j&, k&, nVertNum&, n&
    nVertNum = UBound(aVertexes)
    ReDim aFloydTable(1 To nVertNum, 1 To nVertNum)
    For i = 1 To nVertNum
        For j = 1 To nVertNum
            With aFloydTable(i, j)
                .Length = dInfinite
                ReDim .Vertex(0 To 0)
                If i = j Then .Length = 0
            End With
        Next
    Next
    For i = 1 To UBound(aEdges)
        With aEdges(i)
            aFloydTable(.FromVertex, .ToVertex).Length = .Length
        End With
    Next
    For k = 1 To nVertNum
        For i = 1 To nVertNum
            For j = 1 To nVertNum
                With aFloydTable(i, j)
                    If aFloydTable(i, k).Length + aFloydTable(k, j).Length < .Length Then
                        .Length = aFloydTable(i, k).Length + aFloydTable(k, j).Length
                        ' 保存新的路径，用新的经过 k 的路径替代原先的路径
                        ReDim .Vertex(0 To UBound(aFloydTable(i, k).Vertex) + _
                                           UBound(aFloydTable(k, j).Vertex) + 1)
                        For n = 1 To UBound(aFloydTable(i, k).Vertex)
                            .Vertex(n) = aFloydTable(i, k).Vertex(n)
                        Next
                        .Vertex(n) = k
                        For n = n + 1 To UBound(aFloydTable(k, j).Vertex) + n
                            .Vertex(n) = aFloydTable(k, j).Vertex(n - UBound(aFloydTable(i, k).Vertex) - 1)
                        Next
                    End If
                End With
            Next
        Next
    Next
End Sub
[/code]

lee1892

Bellman-Ford算法

与Dijkstra算法相同的是Bellman-Ford算法也是在顶点保存距离起始点最佳路径的总长度和该路径上的前驱顶点。在Dijkstra算法中，从前文的图示中可以看到，顶点是由起始点开始逐个松弛的。与之不同的是，Bellman-Ford算法是对边松弛的，对图中所有的边进行顶点数量-1次松弛操作，即可得到所有可能的最短路径。其优点是可以计算边的权值为负值的图，但相对的时间复杂度则较高。

伪代码如下：
[code=vb]
Sub BellmanFord（起始点）
    For Each 顶点 In 顶点集合
        顶点.总距离 = 无穷大
        顶点.前驱顶点 = 未定义
    Next
    起始点.总距离 = 0
    For i = 1 To 顶点数量 - 1
        For Each 边 In 边集合
            If 边.起点.总距离 + 边.长度 < 边.终点.总距离 Then
                边.终点.总距离 = 边.起点.总距离 + 边.长度
                边.终点.前驱顶点 = 边.起点
            End If
        Next
    Next
    For Each 边 In 边集合
        If 边.起点.总距离 + 边.长度 < 边.终点.总距离 Then
            MsgBox "存在负权值环，没有最佳路径"
            Exit Sub
        End If
    Next
End Sub
[/code]
另外，可以对该算法进行优化，比如队列优化。由于松弛操作只会发生在最佳路径上的前导顶点松弛过的顶点上，故而可以用一个队列来记录松弛过的顶点，从而可以尽早跳出循环，而进行负权环判定的过程。另外还有其它的优化方式。

在1楼的附件中是未经优化的原始Bellman-Ford算法的实现。

yclotus

值得学习一下。。。

sunsoncheng

对我这等业余者来说,可能不能用学习来说


至少是慢慢学习