单源最短路径算法代码

在Python中，常见的单源最短路径算法有Dijkstra算法（适用于非负权边）和Floyd-Warshall算法（适用于任意权重，但不支持负权重环）。这里我会演示如何使用Python实现Dijkstra算法。

首先，我们需要定义一个图的数据结构。我们可以用字典或邻接矩阵来表示：

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous_nodes = {}

    while len(distances) != len(graph):  # 检查是否所有节点都访问过
        current_node, min_distance = None, float('inf')
        for node, distance in distances.items():
            if distance < min_distance and node not in previous_nodes:
                min_distance = distance
                current_node = node

        if current_node is None:  # 如果没有未访问的节点，说明已找到所有最短路径
            break

        for neighbor, weight in graph[current_node].items():  # 更新邻居的距离
            new_distance = distances[current_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                previous_nodes[neighbor] = current_node

    return distances, previous_nodes

这个`dijkstra`函数接受一个邻接列表形式的图（键是起点，值是另一个字典，其中键是终点，值是权重），以及起点。它返回两个结果：一个是每个节点到起点的最短距离，另一个是构建最短路径时的前驱节点信息。