迪杰斯特拉算法

Question

迪杰斯特拉（Dijkstra）算法是一种用于计算图中最短路径的算法，由荷兰计算机科学家艾兹赫·迪杰斯特拉于 1956 年提出。该算法可以计算出某个节点到图中其他节点的最短路径。

算法的基本思想是从起点开始，通过不断选择与当前节点距离最短的节点进行扩展，直到到达目标节点为止。在计算过程中，算法会维护一个到达每个节点的当前最短路径和距离。具体的步骤如下：

1. 创建一个空的距离表 dist[]，初始化为无穷大，表示起点到各个节点的距离为无穷大。
2. 将起点的距离设置为 0，表示到自身的距离为 0。
3. 创建一个空的集合 visited[]，表示已经找到最短路径的节点集合。
4. 选择一个没有访问过的节点，将其加入 visited[]中，并更新该节点到其相邻节点的距离。
5. 重复上述步骤，直到所有节点都被加入 visited[]中。
6. 找到目标节点，得到最短路径。

迪杰斯特拉算法的时间复杂度为 O(V^2)，其中 V 表示节点数量。在实际应用中，可以使用最小堆（优先队列）数据结构来优化算法的时间复杂度至 O((V+E)logV)，其中 E 表示边的数量。

下面是一个基于邻接矩阵的迪杰斯特拉算法的示例代码：

import sys

def dijkstra(graph, start):
    # 初始化距离表
    dist = [sys.maxsize] * len(graph)
    dist[start] = 0

    # 初始化访问标志列表
    visited = [False] * len(graph)

    for _ in range(len(graph)):
        # 找到距离最短的未访问节点
        min_dist = sys.maxsize
        min_idx = -1
        for i in range(len(graph)):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                min_idx = i

        visited[min_idx] = True

        # 更新与最短路径节点相邻节点的距离
        for i in range(len(graph)):
            if graph[min_idx][i] > 0 and not visited[i]:
                new_dist = dist[min_idx] + graph[min_idx][i]
                if new_dist < dist[i]:
                    dist[i] = new_dist

    return dist

# 邻接矩阵表示图
graph = [
    [0, 2, 4, 0, 0, 0],
    [2, 0, 1, 4, 2, 0],
    [4, 1, 0, 0, 3, 0],
    [0, 4, 0, 0, 3, 2],
    [0, 2, 3, 3, 0, 2],
    [0, 0, 0, 2, 2, 0]
]

start_node = 0
distances = dijkstra(graph, start_node)
print("从节点{}出发的最短路径:".format(start_node))
for i in range(len(distances)):
    print("到达节点{}的最短距离为: {}".format(i, distances[i]))

这个示例代码通过邻接矩阵表示图，使用迪杰斯特拉算法计算从指定起点到其他节点的最短路径。在这个示例中，我们假设图中共有 6 个节点。运行以上代码，将会输出从节点 0 出发到其他节点的最短距离。