单源最短路径算法Python

单源最短路径算法是一种寻找从给定起点到图中其他所有节点最短路径的技术。在Python中，常见的单源最短路径算法有Dijkstra算法和Floyd-Warshall算法。

1. Dijkstra算法：用于带权重的无负边图，它是基于贪心策略，每次选择当前未访问节点中距离起点最近的一个进行扩展。Python中可以使用`heapq`库来实现优先队列，这是该算法的关键数据结构。

from heapq import heappop, heappush

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    unvisited = [(0, start)]
    
    while unvisited:
        current_distance, current_node = heappop(unvisited)
        
        if current_distance > distances[current_node]:
            continue  # 如果更新的距离比记录的还大，说明已经不再是更优解
            
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heappush(unvisited, (distance, neighbor))
                
    return distances

2. Floyd-Warshall算法：适用于任意带权图，通过动态规划求出所有节点对之间的最短路径。它在矩阵上进行操作，适合大规模图。

def floyd_warshall(graph):
    n = len(graph)
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist