基于python写一个最短路径算法

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

import heapq

def dijkstra(graph, start, end):
    # 初始化距离字典，用于存储每个节点距离起点的距离
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    
    # 初始化堆，用于帮助我们找到最短的距离
    pq = [(0, start)]
    
    while pq:
        # 找到距离起点最近的节点
        current_distance, current_vertex = heapq.heappop(pq)
        
        # 如果这个节点就是我们要找的终点，则返回距离
        if current_vertex == end:
            return current_distance
        
        # 如果这个节点已经被处理过，就跳过
        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(pq, (distance, neighbor))
    
    # 如果找不到最短路径，则返回无穷大
    return float('infinity')

下面是一个测试用例：

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

print(dijkstra(graph, 'A', 'D')) # 输出 5

这个测试用例展示了如何使用Dijkstra算法找到从A到D的最短路径。在这个例子中，最短路径是A->B->C->D，距离为5。