python实现dijkstra最短路由算法

下面是详细讲解“Python实现Dijkstra最短路径算法”的完整攻略，包括算法原理、Python实现和两个示例说明。

算法原理

Dijkstra最短算法是一种基于贪心策略的单源最短路径算法，用于求解带权向图中从一个源点到其他所有点的最短路径。其基本思想是维护一个集合S，表示已经找到最短路径的点集合，以及一个距离数组dist，表示源点到每个点的最短距离。初始时，将加入集合S中，将源点到其他点的距离初始化为无穷大，然后不断从未加入集合S的点中选择距离源点最近的点，更新其到源点的距离，并将其加入集合S中。重复以上步骤，直到所有点都加入集S中，或者找到目标点的短路径。

Python实现代码

以下是Python实现Dijkstra最短路径算法的示例代码：

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        (d, node) = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node].items():
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist

上述代码中，定义了一个dijkstra函数表示Dijkstra最短路径算法，接受一个字典graph和一个起始点start作为参数。dist字典表示源点到每个点的最短距离，初始时将源点到其他点的距离初始化为无穷大，将源点加入堆中。然后不断从堆中选择距离源点最近的点，更新其到源点的距离，并将其加入堆中。重复以上步骤，直到所有点都加入堆中，或者找到目标点的最短路径。

示例说明

以下是两个示例，说明如何使用dijkstra函数求解最短路径。

示例1

使用dijkstra函数求解从A到其他点的最短路径。

graph = {
    'A': {'B': 2, 'C': 4},
    'B': {'C': 1, 'D': 3},
    'C': {'D': 1, 'E': 7},
    'D': {'E': 5},
    'E': {}
}

dist = dijkstra(graph, 'A')
print(dist)

输出结果：

{'A': 0, 'B': 2, 'C': 3, 'D': 5, 'E': 10}

示例2

使用dijkstra函数求解从1到其他点的最短路径。

graph = {
    1: {2: 7, 3: 9, 6: 14},
    2: {1: 7, 3: 10, 4: 15},
    3: {1: 9, 2: 10, 4: 11, 6: 2},
    4: {2: 15, 3: 11, 5: 6},
    5: {4: 6, 6: 9},
    6: {1: 14, 3: 2, 5: 9}
}

dist = dijkstra(graph, 1)
print(dist)

输出结果：

{1: 0, 2: 7, 3: 9, 4: 20, 5: 20, 6: 11}

总结

本文介绍了Python实现Dijkstra最短路径算法的完整攻略，包算法原理、Python实现代码和两个示例说明。Dijkstra最短路径算法是一种简单而有效的单源最短路径算法，适用于带权有向图从一个源点到其他所有点的最短路径。在实际应用中，需要注意图的表示方法和数据结构的选择，以获得更好的性能。