贪心算法单源最短路径

贪心算法单源最短路径指的是在一个加权有向图中，从给定的源点到所有其他顶点的最短路径问题。Dijkstra算法是最常用的贪心算法之一，用于解决单源最短路径问题。其基本思想是从源点开始，每次选择当前最短路径的顶点，并更新其相邻顶点的距离，直到所有顶点都被遍历。具体步骤如下：

1.初始化：将源点到所有顶点的距离初始化为无穷大，源点到自身的距离为0。

2.选择当前最短路径的顶点：从未确定最短路径的顶点中选择距离最短的顶点。

3.更新相邻顶点的距离：对于当前选定的顶点，更新其相邻顶点的距离，如果经过当前顶点到达相邻顶点的距离比原来的距离更短，则更新距离。

4.重复步骤2和3，直到所有顶点都被遍历。

以下是一个使用Dijkstra算法求解单源最短路径的Python代码示例：

import heapq

def dijkstra(graph, start):
    # 初始化距离
    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_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 distances