Python 中 Dijkstra 算法求解最短路径的示例代码

在图论和算法领域，求解最短路径是一个常见且重要的问题。Dijkstra 算法是一种用于解决单源最短路径问题的经典算法。在 Python 中，我们可以通过以下示例代码来实现 Dijkstra 算法。

我们需要定义一个表示图的数据结构。可以使用邻接表或邻接矩阵来表示图。在这个示例中，我们使用邻接表来表示。

class Graph:
    def __init__(self):
        self.vertices = {}

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, source, destination, weight):
        self.vertices[source].append((destination, weight))

接下来，实现 Dijkstra 算法的核心函数。

import heapq

def dijkstra(graph, source):
    distances = {vertex: float('inf') for vertex in graph.vertices}
    distances[source] = 0
    priority_queue = [(0, source)]

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

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph.vertices[current_vertex]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

然后，我们可以创建一个图，并使用 Dijkstra 算法求解从某个源顶点到其他顶点的最短路径。

graph = Graph()
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')
graph.add_vertex('E')

graph.add_edge('A', 'B', 6)
graph.add_edge('A', 'D', 1)
graph.add_edge('B', 'D', 2)
graph.add_edge('B', 'E', 2)
graph.add_edge('C', 'B', 5)
graph.add_edge('C', 'E', 5)
graph.add_edge('D', 'E', 1)

source_vertex = 'A'
shortest_distances = dijkstra(graph, source_vertex)

for vertex, distance in shortest_distances.items():
    print(f"从 {source_vertex} 到 {vertex} 的最短距离为: {distance}")

通过以上示例代码，我们成功地在 Python 中实现了 Dijkstra 算法来求解最短路径问题。Dijkstra 算法在许多实际应用中都非常有用，比如网络路由、物流配送路径规划等。

在实际应用中，可能需要根据具体的问题对代码进行一些优化和扩展，以满足不同的需求。但这个基本的示例为理解和使用 Dijkstra 算法提供了一个良好的起点。