---

0.前言

接触计算机网络越久，越发觉得图是一个非常重要的数据结构。
在拓扑图、路由计算、流量分析场景中更是必备。

本文主要以SDN开源控制器ONOS为背景，介绍几个在ONOS中常见的路径搜索算法。

通过对这些路径搜索算法的了解，以能在将来的实际场景中快速选择出最适合的算法。

1.背景知识

图(graph)由一系列的顶点(vertex/node/point)和边(edge)构成。关于图的详细细节本文中不详细展开。

为了理解的方便，本文中的示例图如下：

每一个字母代表一个节点，节点与节点间有不同的权重。

上图对应的Edge List为：

8 12
1 2 1
1 3 3
2 4 2
2 3 1
2 5 4
3 5 1
4 8 5
4 5 1
5 6 1
6 4 1
6 7 1
6 8 1

可在https://visualgo.net/en/sssp中导入：

本文中的要搜索的实例均为：求 A点(0) 到 H点(7) 的最短路径。

映射表：

0	1	2	3	4	5	6	7
A	B	C	D	E	F	G	H

2.DFS & BFS

先回顾两个经典的遍历算法，DFS 和 BFS。

2.1 DepthFirstSearch(DFS)

先看DFS，深度优先搜索。

2.1.1 算法思想

以下是DFS的基本步骤：

1. 选择起始点：选择图中的一个点作为起始点
2. 访问节点：标记起始节点为已访问，并将该节点加入递归或栈中
3. 探索邻接节点：从该点周围取出一个点，检查它的所有未访问的邻接节点
4. 递归或迭代：对每个未访问的邻接节点，将其标记为已访问，然后将其推入递归或栈中
5. 回溯：当当前节点的所有邻接节点都被访问后，递归中回溯/从栈中弹出该节点，继续搜索上一个点的其他分支
6. 结束条件：当栈为空或找到目标节点时，搜索结束

2.1.2 动画

打开https://visualgo.net/en/dfsbfs?slide=1看一下动画：

动画中0点到7点的路径为：0(A)、1(B)、2©、4(E)、5(F)、3(D)、7(H)

2.1.3 测试代码

在ONOS中，DFS的测试代码路径为：utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java

自测代码为：

executeDefaultTest(3, 6, new TestDoubleWeight(5.0), new TestDoubleWeight(12.0));

输出为：

.DefaultPath{src=A, dst=H, cost=8.0, edges=[TestEdge{src=A, dst=B, weight=1.0}, TestEdge{src=B, dst=D, weight=2.0}, TestEdge{src=D, dst=H, weight=5.0}]}

即找到的A(0)到H(7)的路径为：A(0)、B(1)、D(3)、H(7)

总COST为：8.0。

根据最上面的权重拓扑图，我们知道最短COST应该为5.0，这是因为DFS只管找到一条路径后就返回了，也无法计算路径中的权值。

2.1.4 DFS实现代码

在ONOS中，DFS主要代码(DepthFirstSearch.java)：

    @Override
    protected SpanningTreeResult internalSearch(Graph<V, E> graph, V src, V dst,
                                             EdgeWeigher<V, E> weigher, int maxPaths) {

        // Prepare the search result.
        SpanningTreeResult result = new SpanningTreeResult(src, dst, maxPaths);

        // The source vertex has cost 0, of course.
        result.updateVertex(src, null, weigher.getInitialWeight(), true);

        // Track finished vertexes and keep a stack of vertexes that have been
        // started; start this stack with the source on it.
        Set<V> finished = new HashSet<>();
        // 定义一个栈，存储未访问的节点
        Deque<V> stack = new LinkedList<>();
        // 起点入栈
        stack.push(src);

        while (!stack.isEmpty()) {
            // 存在未访问的节点，取出栈顶元素
            V vertex = stack.peek();
            if (vertex.equals(dst)) {
                // If we have reached our destination, bail.
                break;
            }
            // 还没到达终点，继续遍历。当前节点!=终点，并取出当前节点的cost
            Weight cost = result.cost(vertex);
            boolean tangent = false;

            // Visit all egress edges of the current vertex.
            // 从图中取出这个点的所有边
            for (E edge : graph.getEdgesFrom(vertex)) {
                // If we have seen the edge already, skip it.
                if (result.isEdgeMarked(edge)) {
                    continue;
                }

                // Examine the destination of the current edge.
                V nextVertex = edge.dst();
                // 拿到这个边的顶点
                if (!result.hasCost(nextVertex)) {
                    // If this vertex have not finished this vertex yet,
                    // not started it, then start it as a tree-edge.
                    // 如果这个点还没有遍历过，则将此顶点标记为TREE_EDGE
                    result.markEdge(edge, EdgeType.TREE_EDGE);
                    // 将此边的cost累加
                    Weight newCost = cost.merge(weigher.weight(edge));
                    result.updateVertex(nextVertex, edge, newCost, true);
                    // 将此点入栈
                    stack.push(nextVertex);
                    tangent = true;
                    // 跳出for循环
                    break;

                } else if (!finished.contains(nextVertex)) {
                    // We started the vertex, but did not yet finish it, so
                    // it must be a back-edge.
                    // 此点正在遍历过程中，但还没遍历完，标记为BACK_EDGE
                    result.markEdge(edge, EdgeType.BACK_EDGE);
                } else {
                    // The target has been finished already, so what we have
                    // here is either a forward-edge or a cross-edge.
                    //
                    result.markEdge(edge, isForwardEdge(result, edge) ?
                            EdgeType.FORWARD_EDGE : EdgeType.CROSS_EDGE);
                }
            }

            // If we have not been sent on a tangent search and reached the
            // end of the current scan normally, mark the node as finished
            // and pop it off the vertex stack.
            if (!tangent) {
                finished.add(vertex);
                stack.pop();
            }
        }

        // Finally, but the paths on the search result and return.
        result.buildPaths();
        return result;
    }

代码中定义的EdgeType有：

TREE_EDGE, FORWARD_EDGE, BACK_EDGE, CROSS_EDGE

其定义分别为：

• Tree edge(树边)，从一个节点首次访问另一个未访问的节点所经过的边
• Back edge(回溯边)，指向当前 DFS 栈中祖先节点（已经被访问，尚未完成处理）的边
• Forward edge(前向边)，指向某个已经访问并且已经处理完的子孙节点的边
• Cross edge(交叉边)，指向另一个不在当前 DFS 栈中的非祖先也非子孙节点的边

结合代码，总结一下DFS的特征：

1. 一旦遇到目标（终点），就停止当前路径继续搜索
2. 不会尝试所有可能的路径后再选最短的
3. 不具备“全局最优性”：DFS 找到的是第一个可行路径，不一定是最短路径

这也可以解释搜索出来结果的COST为8.0的而非5.0的原因

2.2 BreadthFirstSearch(BFS)

与DFS类似的还有一个BFS，即：广度优先搜索。

2.2.1 算法思想

BFS的核心思想为“先广后深”，即：先访问离起点最近的节点，再逐步扩展到更远的节点。

主要步骤为：

1. 初始化队列：使用一个队列来存储待访问的节点
2. 标记已访问节点：使用一个集合记录已访问的节点，避免重复访问
3. 从起点开始：将起点加入队列，并标记为已访问
4. 循环处理队列：从队列中取出一个节点
   1. 检查该节点是否为目标节点（如果有目标节点的条件）
   2. 如果不是目标节点，将其所有未访问的邻接节点加入队列，并标记为已访问

2.2.2 动画

打开https://visualgo.net/en/dfsbfs?slide=1看一下动画：

动画中0(A)点到7(H)点的路径为：0(A)、1(B)、3(D)、7(H)。
而在DFS部分的动画中，其路径为：0(A)、1(B)、2©、4(E)、5(F)、3(D)、7(H)。

这也是BFS与DFS相比的一大特点：BFS可以找到经过节点最少的路径。

2.2.3 测试代码

在ONOS中，BFS的测试代码路径为：utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java

自测代码为：

executeDefaultTest(7, 3, new TestDoubleWeight(8.0));

输出为：

.DefaultPath{src=A, dst=H, cost=8.0, edges=[TestEdge{src=A, dst=B, weight=1.0}, TestEdge{src=B, dst=D, weight=2.0}, TestEdge{src=D, dst=H, weight=5.0}]}

即找到的A(0)到H(7)的路径为：A(0)、B(1)、D(3)、H(7)

总COST为：8.0。

这里的返回结果与前面的DFS部分一致，这是在因为此处使用的测试数据导致的。（DFS找到的路径具有一定的随机性，不一定能找到最短(经过节点数)的路径，但此测试例中恰好找到了）

2.2.4 BFS实现代码

在ONOS中，BFS实现的主要代码(BreadthFirstSearch.java)：

    @Override
    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
                               EdgeWeigher<V, E> weigher, int maxPaths) {

        // Prepare the graph result.
        DefaultResult result = new DefaultResult(src, dst, maxPaths);

        // Setup the starting frontier with the source as the sole vertex.
        // 定义遍历节点的队列，并先将src节点放入
        Set<V> frontier = new HashSet<>();
        result.updateVertex(src, null, weigher.getInitialWeight(), true);
        frontier.add(src);

        boolean reachedEnd = false;
        while (!reachedEnd && !frontier.isEmpty()) {
            // Prepare the next frontier.
            Set<V> next = new HashSet<>();

            // Visit all vertexes in the current frontier.
            for (V vertex : frontier) {
                Weight cost = result.cost(vertex);

                // Visit all egress edges of the current frontier vertex.
                for (E edge : graph.getEdgesFrom(vertex)) {
                    // 遍历src节点的所有边，并依次遍历每条边的节点
                    V nextVertex = edge.dst();
                    if (!result.hasCost(nextVertex)) {
                        // If this vertex has not been visited yet, update it.
                        Weight newCost = cost.merge(weigher.weight(edge));
                        result.updateVertex(nextVertex, edge, newCost, true);
                        // If we have reached our intended destination, bail.
                        if (nextVertex.equals(dst)) {
                            reachedEnd = true;
                            break;
                        }
                        next.add(nextVertex);
                    }

                    if (reachedEnd) {
                        break;
                    }
                }
            }

            // Promote the next frontier.
            frontier = next;
        }

        // Finally, but the paths on the search result and return.
        result.buildPaths();
        return result;
    }

BFS的实现代码与DFS相比要简短一些，采用分层遍历的方式逐步遍历即可。

这也就意味着在不考虑最短路径搜索的情况下，仅要实现找到一条路径，以程序计算耗时最短为目标，一般都采用DFS，因为它是真的快。

2.3 DFS/BFS对比

项目	DFS（深度优先搜索）	BFS（广度优先搜索）
遍历策略	一条路走到底，回溯再找新路径	一层一层地展开，按距离分层遍历
数据结构	栈（递归或显式栈）	队列（先进先出）
空间复杂度	O(V)（递归栈最大深度）	O(V)（队列最大宽度）
找最短路径	❌ 不保证最短路径	✅ 可以找到从起点到某点的最短路径
适合图类型	任意图，尤其适合解决路径或拓扑问题	无权图，适合找最短路径或最小步数问题

小结：BFS和DFS都不能找到最小权重的路径，但BFS可能找到最短路径(经过的节点最少)。

3.DijkstraGraphSearch(Dijkstra)

我们有时会说：贪心算法(greedy algorithm)无法求得问题的最优解，但Dijkstra算法除外。

是的，接下来进入路径规划算法王者——Dijkstra(狄克斯特拉)算法。

Dijkstra算法：从一个顶点到其余各顶点的最短路径算法，解决的是有权图中的最短路径问题。

即：从图中的某个顶点出发，到达另外一个顶点的所经过的边的权重和最小的一条路径——最短路径。

3.1 算法思想

算法思想：迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

实现步骤：

1. 初始化：
   • 起点(D)到自身的距离设为 0
   • 其他点的距离设为 ∞
2. 维护一个最短路径集合，S（已确定最短路径的点）
3. 每次从未处理的节点(U)中选出当前距离起点最小的点，加入集合
4. 更新其邻接节点的距离（松弛操作）
5. 重复直到所有点都处理完，或到达目标节点

松弛操作(Relaxation)：是 Dijkstra 算法（以及其他最短路径算法）中的核心步骤。它的作用是：尝试通过当前路径，更新到某个节点的最短距离估计。

松弛操作示例如下，假设当前：

dist[A] = 0

dist[B] = ∞

有边 A → B，权重为 5
if dist[B] > dist[A] + 5:
    dist[B] = dist[A] + 5 = 5

3.2 动画

打开https://visualgo.net/en/sssp，输入示例的图数据，并运行：

动画中0(A)点到7(H)点的路径为：0(A)、1(B)、2©、4(E)、5(F)、7(H)，对应的路径权重为：5。
这比前面的DFS/BFS权重8都要小。

3.3 测试代码

在ONOS中，BFS的测试代码路径为：utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java

自测代码为：

executeDefaultTest(7, 5, new TestDoubleWeight(5.0));

即找到的A(0)到H(7)的路径也为：0(A)、1(B)、2©、4(E)、5(F)、7(H)，与前面的动画一致。

3.4 Dijkstra实现代码

在ONOS中，Dijkstra实现的主要代码(DijkstraGraphSearch.java)：

    @Override
    protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
                               EdgeWeigher<V, E> weigher, int maxPaths) {

        // Use the default result to remember cumulative costs and parent
        // edges to each each respective vertex.
        DefaultResult result = new DefaultResult(src, dst, maxPaths);

        // Cost to reach the source vertex is 0 of course.
        result.updateVertex(src, null, weigher.getInitialWeight(), false);

        if (graph.getEdges().isEmpty()) {
            result.buildPaths();
            return result;
        }

        // Use the min priority queue to progressively find each nearest
        // vertex until we reach the desired destination, if one was given,
        // or until we reach all possible destinations.
        Heap<V> minQueue = createMinQueue(graph.getVertexes(),
                                          new PathCostComparator(result));
        while (!minQueue.isEmpty()) {
            // Get the nearest vertex
            V nearest = minQueue.extractExtreme();
            if (nearest.equals(dst)) {
                break;
            }

            // Find its cost and use it to determine if the vertex is reachable.
            if (result.hasCost(nearest)) {
                Weight cost = result.cost(nearest);

                // If the vertex is reachable, relax all its egress edges.
                for (E e : graph.getEdgesFrom(nearest)) {
                    result.relaxEdge(e, cost, weigher, true);
                }
            }

            // Re-prioritize the min queue.
            minQueue.heapify();
        }

        // Now construct a set of paths from the results.
        result.buildPaths();
        return result;
    }

4. 小结

用一个列表对比一下本文中介绍的几种路径搜索算法：

算法	支持权重	找到最小权重路径
BFS	❌（仅支持统一权重）	❌（只找最少边数路径）
DFS	❌	❌（不能保证）
Dijkstra	✅（正权）	✅

最近稍微忙起来了，后面再对ONOS中剩余的BellmanFord、KShortest、SuurballeGraphSearch、Srlg、遗传算法GA进行介绍。