Dijkstra 算法实现 邻接表

Dijkstra 算法是一种用于计算图中最短路径的算法，可以用邻接表来实现。下面是一个使用邻接表实现 Dijkstra 算法的示例代码：

import heapq

def dijkstra(adj, start):
    # 初始化距离数组
    dist = [float('inf')] * len(adj)
    dist[start] = 0

    # 使用堆来存储未处理的节点
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue

        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

在这个实现中，我们使用了 Python 中的 heapq 库来实现堆。首先，我们初始化一个距离数组，将起点的距离设置为 0，其余节点的距离设置为无穷大。然后，我们将起点加入堆中。接下来，我们不断地从堆中取出距离最小的节点，并更新与之相邻的节点的距离。如果更新后的距离比原来的距离更小，我们就将它加入堆中。最后，我们返回距离数组。

在邻接表中，每个节点对应一个列表，其中包含该节点连向的所有节点及其权重。在示例代码中，我们将邻接表存储为一个列表，其中每个元素是一个包含节点和其邻居的列表。例如，如果节点 0 连向节点 1 和节点 2，权重分别为 2 和 5，则邻接表中的第一个元素为 [(1, 2), (2, 5)]。

注意，由于 Dijkstra 算法中使用了堆来实现优先队列，因此时间复杂度为 O((E+V)logV)，其中 E 表示边数，V 表示节点数。