Python最短路径思想和代码

Python中常用的最短路径算法有Dijkstra算法和A*算法。其中Dijkstra算法适用于有向无环图（DAG）和正权重边的情况，A*算法通过启发式函数估计目标距离来优化Dijkstra算法，在图较大时更为高效。以下是Dijkstra算法的Python代码实现：

import heapq

def dijkstra(graph, start, end):
    heap = [(0, start)]
    visited = set()
    while heap:
        (weight, node) = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        if node == end:
            return weight
        for neighbor, neighbor_weight in graph[node].items():
            if neighbor not in visited:
                heapq.heappush(heap, (weight + neighbor_weight, neighbor))
    return -1  # 如果没有找到最短路径，返回-1

# 例子：有向图 {(a,b,1), (b,c,2), (c,d,3), (d,e,4)}，从a到e的最短路径长度为7
graph = {'a': {'b': 1}, 'b': {'c': 2}, 'c': {'d': 3}, 'd': {'e': 4}, 'e': {}}
print(dijkstra(graph, 'a', 'e'))

注意，这只是最短路径算法的一种实现，并不是最优的或者唯一的实现。