迪杰斯特拉算法是什么

迪杰斯特拉算法是一种解决带权图的单源最短路径问题的贪心算法。它的核心思想是从起始点开始，每次选择距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。该算法通过给每个顶点标号来计算最短路径，临时标号T表示从起始点到该顶点的最短路径的上界，固定标号P表示从起始点到该顶点的最短路径。

以下是迪杰斯特拉算法的实现范例，求始点V1到其余顶点的最短路径：

import sys

def dijkstra(graph, start):
    # 初始化距离字典，将起始点到所有顶点的距离设为无穷大
    distance = {vertex: sys.maxsize for vertex in graph}
    distance[start] = 0

    # 初始化已访问集合和未访问集合
    visited = set()
    unvisited = set(graph)

    while unvisited:
        # 选择距离最小的顶点
        current = min(unvisited, key=lambda vertex: distance[vertex])

        # 更新当前顶点的邻接节点的距离
        for neighbor, weight in graph[current].items():
            if distance[current] + weight < distance[neighbor]:
                distance[neighbor] = distance[current] + weight

        # 将当前顶点标记为已访问，并从未访问集合中移除
        visited.add(current)
        unvisited.remove(current)

    return distance

# 示例图的邻接表表示
graph = {
    'V1': {'V2': 2, 'V4': 1},
    'V2': {'V3': 3, 'V4': 2},
    'V3': {'V5': 1},
    'V4': {'V2': 1, 'V3': 1, 'V5': 4},
    'V5': {}
}

start_vertex = 'V1'
shortest_paths = dijkstra(graph, start_vertex)
print("Shortest paths from", start_vertex, "to each vertex:")
for vertex, distance in shortest_paths.items():
    print("Distance to", vertex, ":", distance)

输出结果为：

Shortest paths from V1 to each vertex:
Distance to V1 : 0
Distance to V2 : 2
Distance to V3 : 3
Distance to V4 : 1
Distance to V5 : 5