以邻接表作存储结构实现求从源点到其余各顶点的最短路径的 Dijkstra 算法

Dijkstra 算法是一种基于贪心策略的图论算法，用于解决带权有向图或无向图中的单源最短路径问题。下面是使用邻接表实现的 Dijkstra 算法的伪代码：

1. 初始化距离数组 dis，将源点的距离设为 0，其余点的距离设为无穷大。
2. 创建一个优先队列 pq 并将源点插入队列中。
3. 当队列不为空时，取出队列中的顶点 u，并遍历它的所有邻接点 v。
4. 如果从源点到 v 的距离 dis[u] + w(u, v) 比当前记录的距离 dis[v] 更小，则更新距离 dis[v] 并将 v 插入优先队列中。
5. 重复步骤 3、4 直到队列为空。

其中，w(u, v) 表示从顶点 u 到顶点 v 的边权值。

下面是使用 Python 实现的 Dijkstra 算法代码：

import heapq

def dijkstra(graph, src):
n = len(graph)
dis = [float('inf')] * n
dis[src] = 0
pq = [(0, src)]

while pq:
d, u = heapq.heappop(pq)
if d > dis[u]:
continue
for v, w in graph[u]:
if dis[u] + w < dis[v]:
dis[v] = dis[u] + w
heapq.heappush(pq, (dis[v], v))

return dis

其中，graph 是邻接表表示的图，src 是源点的编号。graph[u] 表示顶点 u 的邻接点列表，每个元素都是一个二元组 (v, w)，表示从顶点 u 到顶点 v 的边权值为 w。heappush 和 heappop 分别是将元素插入堆和从堆中取出最小元素的函数，heapq 是 Python 自带的堆模块。