python实现dijkstra算法

Dijkstra算法是一种贪心算法，用于解决单源最短路径问题。在 Python 中实现 Dijkstra 算法的一种常见方法是使用堆数据结构。

算法步骤:
1. 初始化图中所有点的距离值为无穷大，起点的距离值为0。
2. 将所有点的距离值加入堆中，并将起点设为当前点。
3. 重复以下操作，直到堆为空：
a. 取出堆顶元素，将其设为当前点。
b. 遍历当前点的所有邻点，如果邻点的距离值大于当前点的距离值加上当前点到邻点的距离，则更新邻点的距离值。
c. 将邻点加入堆中。
4. 最短路径已求出，距离值存储在每个点的距离值中。

代码如下:

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    heap = [(0, start)]
    while heap:
        current_distance, current_vertex = heapq.heappop(heap)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

该代码中,graph 是一个邻接表表示的图，其中键为点，值为一个字典，该字典的键为Dijkstra算法是一种用于计算图中单源最短路径的算法。在Python中可以使用heapq库来实现Dijkstra算法。

下面是一个简单的例子：

import heapq

def dijkstra(graph, start):
    heap = [(0, start)]
    visited = set()
    while heap:
        (cost, current) = heapq.heappop(heap)
        if current in visited:
            continue
        visited.add(current)
        for neighbor, c in graph[current].items():
            if neighbor not in visited:
                heapq.heappush(heap, (cost + c, neighbor))
    return visited

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

print(dijkstra(graph, 'A'))

这里的图是一个字典，其中key是节点，value是该节点的邻居节点及边权。dijkstra函数接受图和起始点作为参数，返回所有访问过的节点。

注意：上面代码是一个简单的实现，并不能解决负权边问题，需要根据实际需求修改代码