Python实现Dijkstra算法找最短路径

“纵有疾风来，人生不言弃”，这句话送给正在学习文章的朋友们，也希望在阅读本文《Python实现Dijkstra算法找最短路径》后，能够真的帮助到大家。我也会在后续的文章中，陆续更新文章相关的技术文章，有好的建议欢迎大家在评论留言，非常感谢！

Dijkstra算法适用于边权非负的图。1. 它不能处理含有负权边的图，因为一旦确定某个节点的最短路径，就不会再回头更新；2. 对于此类问题，更适合使用Bellman-Ford算法；3. Dijkstra适用于无向图和有向图，只要满足非负权边条件。

在Python中实现最短路径，Dijkstra算法是一个非常经典且高效的选择，尤其适用于边权非负的图。它的核心思想是逐步探索，每次都从已知最短路径的节点中，找到下一个距离起点最近的节点，然后以此更新其邻居的距离，直到所有可达节点的距离都被确定。

解决方案

实现Dijkstra算法，我们通常需要一个图的表示（比如邻接列表或字典），一个记录从起点到各节点当前最短距离的字典，一个记录路径前驱的字典，以及一个优先队列来高效地获取下一个要处理的节点。Python的heapq模块非常适合做这个优先队列。

首先，我们得把图给搭起来。一个字典套字典的结构，或者用defaultdict(list)来表示邻接列表，都挺直观的。我个人更倾向于后者，感觉在遍历邻居时更自然一些。

import heapq
from collections import defaultdict

def dijkstra(graph, start_node):
    # 存储从起点到各节点的最短距离
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0

    # 优先队列，存储 (距离, 节点) 对
    # heapq 默认是最小堆，正好符合我们的需求
    priority_queue = [(0, start_node)]

    # 存储路径的前驱节点，用于最终路径的重建
    predecessors = {}

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # 如果当前距离已经比记录的要长，说明我们找到了更短的路径，跳过
        # 这是为了处理同一个节点可能被多次加入优先队列的情况
        if current_distance > distances[current_node]:
            continue

        # 遍历当前节点的所有邻居
        for neighbor, weight in graph[current_node].items(): # 假设graph是 {node: {neighbor: weight}}
            distance = current_distance + weight

            # 如果通过当前节点到达邻居的距离更短
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node # 更新前驱
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances, predecessors

def reconstruct_path(predecessors, start_node, end_node):
    path = []
    current = end_node
    while current != start_node:
        if current not in predecessors: # 无法到达
            return None
        path.insert(0, current)
        current = predecessors[current]
    path.insert(0, start_node)
    return path

# 示例图
# graph = {
#     'A': {'B': 1, 'C': 4},
#     'B': {'A': 1, 'C': 2, 'D': 5},
#     'C': {'A': 4, 'B': 2, 'D': 1},
#     'D': {'B': 5, 'C': 1}
# }
# 也可以这样表示，更通用一些，尤其是处理稀疏图时
graph_adj = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start = 'A'
end = 'D'
shortest_distances, paths = dijkstra(graph_adj, start)
print(f"从 {start} 到各节点的最短距离: {shortest_distances}")
path = reconstruct_path(paths, start, end)
print(f"从 {start} 到 {end} 的最短路径: {path}")

# 输出示例：
# 从 A 到各节点的最短距离: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
# 从 A 到 D 的最短路径: ['A', 'B', 'C', 'D']

这里有个小细节，graph[current_node].items() 假设了 graph 是一个字典，其值也是字典（{node: {neighbor: weight}}）。如果用邻接列表，比如 graph = {'A': [('B', 1), ('C', 4)]}，那么遍历方式需要调整为 for neighbor, weight in graph[current_node]:。我个人觉得字典嵌套字典更直观地表达了“从A到B的权重是多少”这种关系。

Dijkstra算法适用于哪些图类型？

Dijkstra算法最核心的适用条件，就是图中的所有边权重都必须是非负数。这是它的基石，如果图中存在负权边，Dijkstra算法就可能给出错误的答案。为什么会这样呢？因为Dijkstra算法在每次确定一个节点的最终最短距离后，就认为这个距离是“不可被超越”的了。它不会回头去检查，如果后面通过一条负权边，可能会让之前“确定”的最短路径变得更短。

举个例子，假设A到B是10，A到C是1，C到B是-100。Dijkstra会先确定A到C是1，然后用1去更新C的邻居。如果它先确定了A到B是10，然后就“锁死”了B的距离，但实际上A->C->B的路径是1 + (-100) = -99，比10短得多。这时候Dijkstra就傻眼了。

对于含有负权边的图，我们通常会考虑使用Bellman-Ford算法，它虽然时间复杂度更高，但能正确处理负权边，甚至能检测出负权环。不过，Dijkstra的优势在于其高效性，对于绝大多数实际应用中边权非负的场景，它都是首选。无论是无向图还是有向图，只要满足非负权边这个条件，Dijkstra都能胜任。

Dijkstra算法的时间复杂度是多少，如何优化？

Dijkstra算法的时间复杂度取决于图的表示方式和优先队列的实现。

如果使用朴素的数组来查找下一个最小距离的节点（即每次遍历所有未访问节点找到距离最小的那个），那么时间复杂度是 O(V^2)，其中V是图中节点的数量。这种方式在节点数量不多的时候还能接受，但当V变得很大时，性能瓶颈就非常明显了。

当我们引入二叉堆（Binary Heap）作为优先队列时，时间复杂度可以显著优化到 O(E log V)，其中E是图中边的数量。这里的log V是每次从堆中取出最小元素或更新元素时，堆调整操作的开销。Python的heapq模块底层就是基于二叉堆实现的，所以我们上面的代码就是这种优化过的版本。

更高级的优化，比如使用斐波那契堆（Fibonacci Heap），可以将时间复杂度进一步优化到 O(E + V log V)。不过，斐波那契堆的实现非常复杂，常数因子也比较大，所以在实际工程中，除非图的规模特别巨大且对性能有极致要求，否则通常还是使用基于二叉堆的Dijkstra算法。heapq已经足够满足大部分需求了，它既简单易用，性能也相当不错。在大多数情况下，图的边数E通常比V的平方小得多（稀疏图），所以O(E log V)的性能提升是实实在在的。

在实际项目中，Dijkstra算法有哪些常见的应用场景？

Dijkstra算法在实际生活和技术领域中有着非常广泛的应用，它的核心价值在于找到“最优”或“最短”的连接方式，这在很多场景下都是关键。

最直观的，也是大家最熟悉的，就是GPS导航系统。当你输入目的地，导航软件计算出一条最优路线时，Dijkstra算法（或其变种，如A*算法，它在Dijkstra基础上加入了启发式搜索，进一步提升了效率）就在幕后默默工作。它将道路网络抽象成图，交叉路口是节点，路段是边，路段的长度或通行时间就是边的权重。

除了导航，它还在网络路由中扮演重要角色。互联网上的数据包需要从源头传输到目的地，路由器需要决定数据包的下一跳去哪里，以确保数据能以最快（或最经济）的方式抵达。OSPF（开放最短路径优先）等路由协议就使用了Dijkstra算法来计算网络拓扑中的最短路径。

在资源分配和调度方面，Dijkstra也能派上用场。比如，在物流配送中，如何规划送货车辆的路线，使其在最短时间内送达所有包裹；或者在云计算环境中，如何将任务分配给不同的服务器，以最小化处理时间或成本。这些都可以建模成最短路径问题。

甚至在游戏AI里，Dijkstra也有它的身影。比如，一个NPC（非玩家角色）需要从A点移动到B点，并避开障碍物，或者找到最近的补给点。游戏地图可以被视为一个网格图，Dijkstra可以帮助NPC规划出最佳的移动路径。

总的来说，任何可以被抽象成“在带权图中寻找最短路径”的问题，Dijkstra算法都值得被考虑。它的通用性和高效性，使得它成为了算法工具箱里不可或缺的一员。

本篇关于《Python实现Dijkstra算法找最短路径》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！