dijsktra求最短路径

Dijkstra算法是一种用于解决带权有向图或无向图的单源最短路径问题的贪心算法。它的基本思想是从起点开始，逐步扩大范围，直到覆盖所有节点。在这个过程中，维护一个到起点的距离数组，每次选择距离最小的节点进行扩展，并更新与该节点相邻节点的距离。具体步骤如下：

1.初始化：将起点到各个节点的距离设为正无穷，将起点到自身的距离设为0。

2.选择距离最小的节点进行扩展，将该节点标记为已访问。

3.更新与该节点相邻节点的距离：如果起点到该节点的距离加上该节点到相邻节点的距离小于起点到相邻节点的距离，则更新起点到相邻节点的距离。

4.重复步骤2和3，直到所有节点都被访问过。

5.输出起点到各个节点的最短距离。

下面是一个Python实现的例子：

import sys

def dijkstra(graph, start):
    # 初始化距离数组
    dist = {node: sys.maxsize for node in graph}
    dist[start] = 0
    # 初始化已访问节点集合
    visited = set()
    # 循环直到所有节点都被访问过
    while len(visited) < len(graph):
        # 选择距离最小的节点进行扩展
        node = min((set(dist.keys()) - visited), key=dist.get)
        # 标记该节点为已访问
        visited.add(node)
        # 更新与该节点相邻节点的距离
        for neighbor, distance in graph[node].items():
            if neighbor not in visited:
                new_distance = dist[node] + distance
                if new_distance < dist[neighbor]:
                    dist[neighbor] = new_distance
    # 输出起点到各个节点的最短距离
    for node in sorted(dist):
        print(f"Distance from {start} to {node}: {dist[node]}")

# 测试
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}
dijkstra(graph, 'A')

输出结果为：

Distance from A to A: 0
Distance from A to B: 5
Distance from A to C: 1
Distance from A to D: 6
Distance from A to E: 9
Distance from A to F: 12