Dijkstra 算法概述 | Baeldung中文网

1. 简介

在软件开发中，我们经常需要在图中找到两个点之间的最优路径。这种需求在很多场景中都会出现，比如游戏中的寻路、地图类软件（如 Google Maps）的路线规划，以及其他各种需要路径计算的系统中。

Dijkstra 算法是一种非常流行的最短路径查找算法，广泛用于图结构中两点之间的最短路径计算。

2. 什么是路径查找（Pathfinding）

路径查找是一种图遍历算法，用于从起点到终点之间找出最优路径。这里的“最优”可以是步数最少，也可以是每一步的“代价”总和最小。

路径代价取决于图的类型。例如在现实地图中，代价可能是距离（米），而在游戏如 Civilization 中，代价可能根据单位类型和地形类型来决定。

路径查找还被用于状态机的遍历，图中的每个节点代表一个状态，边代表状态之间的转换。比如解决魔方问题时，就可以用路径查找找出最短的状态转换路径。

3. Dijkstra 算法原理

Dijkstra 算法是一种贪心算法，它会从起点开始，逐步探索所有可达路径，并记录到达每个节点的最短代价，最终找到通往目标节点的最短路径。

算法核心思想是：

为每个节点维护一个“当前最短距离”
每次选取当前未访问节点中距离最短的节点，作为当前节点
遍历该节点的所有邻居，尝试更新它们的最短距离
直到目标节点被访问或所有可达节点都已处理完毕

3.1 流程图

Dijkstra Algorithm Flowchart

3.2 伪代码详解

主算法逻辑

algorithm Dijkstra(graph, startNode, targetNode):
    // INPUT
    //     graph, startNode, targetNode
    // OUTPUT
    //     从 startNode 到 targetNode 的最短路径

    for each node in graph:
        node.score <- infinity
        node.visited <- false

    startNode.score <- 0

    while true:
        currentNode <- nodeWithLowestScore(graph)
        currentNode.visited <- true

        for nextNode in currentNode.neighbors:
            if nextNode.visited = false:
                newScore <- calculateScore(currentNode, nextNode)
                if newScore < nextNode.score:
                    nextNode.score <- newScore
                    nextNode.routeToNode <- currentNode

        if currentNode = targetNode:
            return buildPath(targetNode)

        if nodeWithLowestScore(graph).score = infinity:
            throw a NoPathFound exception

辅助函数 1：找出当前得分最低（最短路径）的未访问节点

algorithm nodeWithLowestScore(graph):
    // INPUT
    //     graph = 输入图
    // OUTPUT
    //     未访问且得分最低的节点

    result <- null
    for each node in graph:
        if node.visited = false and (result is null or node.score < result.score):
            result <- node

    return result

辅助函数 2：计算新路径得分

algorithm calculateScore(currentNode, nextNode):
    // INPUT
    //     currentNode, nextNode
    // OUTPUT
    //     从 currentNode 到 nextNode 的新得分

    return currentNode.score + currentNode.edgeCost(nextNode)

辅助函数 3：构建最终路径

algorithm buildPath(targetNode):
    // INPUT
    //     targetNode
    // OUTPUT
    //     从起点到终点的路径节点列表

    route <- create an empty list
    currentNode <- targetNode

    while currentNode != null:
        route.add(currentNode)
        currentNode <- currentNode.routeToNode

    return route

💡 小贴士：

Dijkstra 适合无负权边的图结构
如果图中存在负权边，应使用 Bellman-Ford 算法
若图是网格结构（如地图），可以考虑 A* 算法，效率更高

4. 总结

我们介绍了路径查找的基本概念，以及 Dijkstra 算法的核心思想和实现逻辑。该算法虽然简单，但非常实用，是图遍历中最基础也是最重要的算法之一。

✅ 适用场景：

路径规划（地图导航）
网络路由
游戏 AI 寻路
状态机路径查找

❌ 不适用场景：

图中存在负权边
实时性要求极高，需要更快的启发式算法

⚠️ 踩坑提醒：

初始化所有节点得分时，务必设为无穷大（可模拟为一个极大值）
访问过的节点不能再参与后续计算，否则可能陷入死循环
构建路径时要记得反转顺序，因为是从终点回溯到起点

掌握 Dijkstra 算法后，你可以在此基础上尝试实现更高效的 A* 算法，或结合实际场景进行优化。

Persistence

REST

Security