反圈法求解最短路径算法伪代码

以下是使用反圈法求解最短路径的伪代码：

// 初始化所有节点的距离为正无穷，源节点的距离为0
for each node v in graph:
    distance[v] = INFINITY
distance[source] = 0

// 对所有边进行松弛操作
for i from 1 to |V|-1:
    for each edge (u, v) in graph:
        if distance[u] + weight(u, v) < distance[v]:
            distance[v] = distance[u] + weight(u, v)

// 对所有边进行第二次松弛操作
for each edge (u, v) in graph:
    if distance[u] + weight(u, v) < distance[v]:
        // 存在负权回路，算法结束
        return "Graph contains a negative-weight cycle"

// 最短路径已经求解出来
return distance

其中，`distance[v]` 表示源节点到节点 `v` 的最短距离，`INFINITY` 表示正无穷大，`weight(u, v)` 表示边 `(u, v)` 的权值。在第一次松弛操作中，算法会对所有边进行松弛操作，重复执行 $|V|-1$ 次。在第二次松弛操作中，算法仅对所有边进行一次松弛操作。如果存在负权回路，则算法会返回 "Graph contains a negative-weight cycle"，否则最短路径已经求解出来，可以返回 `distance` 数组。