单源最短路

请确保自己已经了解图的相关内容。包括但不限于：

• 图，邻接表，邻接矩阵
• 路径，最短路，权，环
• 有向图，无向图

定义

顾名思义，求单一起点到其他可连通节点的最短路径。有两种比较经典的算法：

最短路算法	Dijkstra	Bellman–Ford
最短路类型	单源最短路	单源最短路
作用于	非负权图	任意图
能否检测负环？	不能	能
时间复杂度	$O(M\log M)$	$O(NM)$

注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。

Dijkstra

迪杰斯特拉算法是一个经典的求单源最短路的算法。其优点是容易理解，在数据量不大的情况下拥有较好的效率。缺点则是无法处理存在负权边的图。

过程

先介绍Dijkstra算法要用到的松弛操作（后面的Bellman–Ford算法也会用到松弛操作）。

对于边(u,v)，松弛操作对应下面的式子：dis(v)=min(dis(v), dis(u)+w(u,v))。

这么做的含义是显然的：我们尝试用S->u->v（其中S->u的路径取最短路）这条路径去更新v点最短路的长度，如果这条路径更优，就进行更新。

再来看Dijkstra算法。

将结点分成两个集合：已确定最短路长度的点集（记为S 集合）的和未确定最短路长度的点集（记为T集合）。一开始所有的点都属于T集合。

初始化dis(s)=0，其他点的dis均为+inf。

然后重复这些操作：

1. 从T集合中，选取一个最短路长度最小的结点，移到S集合中。
2. 对那些刚刚被加入S集合的结点的所有出边执行松弛操作。

直到T集合为空，算法结束。

实现

代码

import heapq

def dijkstra(graph, start):
    
    # 初始化距离字典，将起点距离设为0，其他点距离设为无穷大
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    # 使用优先队列存储顶点和对应的距离
    pq = [(0, start)]

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        # 如果当前顶点的距离大于已知最短路径的距离，则跳过
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 如果新路径比已知的最短路径还要短，则更新距离和优先队列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances


# 建图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# A为源点测试
start_vertex = 'A'
for vertex, distance in dijkstra(graph, start_vertex).items():
    print(f"到达顶点 {vertex} 的距离为: {distance}")

运行结果

到达顶点 A 的距离为: 0
到达顶点 B 的距离为: 1
到达顶点 C 的距离为: 3
到达顶点 D 的距离为: 4

理论

正确性

此证明包含大量盯真成分，仅供粗略理解。严谨数学证明可参考**《算法导论》第24章相关内容**

算法导论（原书第3版） | Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein | download on Z-Library (singlelogin.re)

Dijkstra的核心思想是贪心，通过局部最优累加出总体最优。要证明其正确性，关键在于证明局部的叠加能够得到整体最优解。

采取反证法。

假设存在一个顶点v，算法得出的从源点s到v的最短路径d[v] 不是当前最短路径，即存在一条更短的路径。令u为d[v]上v的任意前一顶点。

根据Dijkstra算法的贪心性质，其得出的结果总是有d[u] + w(u, v) >= d[v]，其中w(u, v)为边(u, v)的权重，d[u]是源点s到u的最优解。

因此，d[v]不可能大于d[u] + w(u, v)。排除闪现的可能，即以通过权边的方式到达v，更短的路径不存在，假设不成立。因此可以认为Dijkstra算法得到的最短路径是最优的。

时间复杂度

朴素Dijkstra

假设图有V个顶点和E条边：

1. 初始化所有顶点的距离为无穷大，标记数组表示是否已经找到最短路径：O(V)。
2. 执行V次循环，每次找到距离最小且未被标记的顶点，遍历所有顶点来找到距离最小的顶点：O(V^2^)。
3. 对于每个被选中的顶点，考虑每条边一次，以更新其相邻顶点的距离：O(E)。

综上所述，朴素Dijkstra算法的总时间复杂度为O(V^2^ + E)。如果图是稀疏的（即E接近V^2^），则可以将时间复杂度简化为O(V^2^)。

优先队列优化

使用最小堆实现优先队列，假设图有V个顶点和E条边：

1. 初始化距离数组和优先队列：O(V)。
2. 在优先队列不为空时执行循环，最坏情况下需要执行V次：
   • 从优先队列中弹出顶点：O(logV)。每次弹出都要调整堆，最坏情况下是堆的高度logV。
   • 对于每个弹出的顶点，遍历其所有邻居并更新距离：O(E)。在最坏情况下，每个边都会被考虑一次。
   • 更新优先队列中的顶点：O(logV)。更新优先队列中的顶点的距离可能需要调整堆。

综上，优化Dijkstra总时间复杂度为 O(VlogV + ElogV)。如果图是稀疏的（即E接近V^2^），则可以将时间复杂度简化为 O( (V+E) logV )。

空间复杂度

朴素Dijkstra

实现该算法需要一个大小为V的数组来存储每个顶点到起始顶点的距离，空间复杂度为O(V)；需要一个大小为V的数组来标记每个顶点是否已经找到最短路径，空间复杂度为O(V)；需要一个大小为 V^2^ 的矩阵或 V 个链表来表示图中顶点之间的关系。空间复杂度为O(V^2^)或O(E)，取决于图的稠密程度。其他变量和数据结构如临时变量、堆栈等的空间消耗通常是常量级别的，可以忽略不计。

综上所述，朴素Dijkstra算法的总空间复杂度为 O(V^2^)

优先队列优化

需要一个大小为V的数组来存储每个顶点到源点的最短距离，空间复杂度为O(V)；优先队列的大小最多为V，因为每个顶点最多只会入队一次，空间复杂度为O(V)；邻接矩阵或邻接列表空间复杂度为O(V^2^)或O(E)。

因此，使用优先队列优化的Dijkstra算法的总空间复杂度为 O(V)~（距离数组）~+ O(V)~（优先队列）~+ O(V^2^)或O(E)~（邻接矩阵或邻接列表）~。

Bellman-Ford

贝尔曼福特算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

在国内OI界，你可能听说过的**「SPFA」，就是Bellman–Ford算法**的一种实现。

过程

回顾前面的松弛操作。

对于边(u,v)，松弛操作对应下面的式子：dis(v)=min(dis(v), dis(u)+w(u,v))。

Bellman–Ford算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

每次循环是O(m)的，那么最多会循环多少次呢？

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少+1，而最短路的边数最多为n-1，因此整个算法最多执行n-1轮松弛操作。故总时间复杂度为O(nm)。

但还有一种情况，如果从s点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行n-1轮，因此如果第n轮循环时仍然存在能松弛的边，说明从S点出发，能够抵达一个负环。利用这个特点，我们可以实现对图中是否存在负环进行判断。

实现

代码

class Edge:
    def __init__(self, u, v, weight):
        self.u = u
        self.v = v
        self.weight = weight

def bellman_ford(edges, V, start):
    
    # 初始化dist，将起点距离设为0，其他点距离设为无穷大
    dist = [float("inf")] * V
    dist[start] = 0

    # 对所有边进行V-1次松弛操作
    for _ in range(V - 1):
        for edge in edges:
            if dist[edge.u] + edge.weight < dist[edge.v]:
                dist[edge.v] = dist[edge.u] + edge.weight

    # 检查负权环
    for edge in edges:
        if dist[edge.u] + edge.weight < dist[edge.v]:
            print("图中存在负权环")
            return None

    return dist

# 建图
edges = [
    Edge(0, 1, -1),
    Edge(0, 2, 4),
    Edge(1, 2, 3),
    Edge(1, 3, 2),
    Edge(1, 4, 2),
    Edge(3, 2, 5),
    Edge(3, 1, 1),
    Edge(4, 3, -3)
]

V = 5  # 图中顶点的数量
start = 0  # 源点

distances = bellman_ford(edges, V, start)
if distances:
    for i in range(V):
        print(f"到达顶点 {i} 的距离为: {distances[i]}")

运行结果

到达顶点 0 的距离为: 0
到达顶点 1 的距离为: -1
到达顶点 2 的距离为: 2
到达顶点 3 的距离为: -2
到达顶点 4 的距离为: 1

理论

正确性

此证明包含大量盯真成分，仅供粗略理解。严谨数学证明可参考**《算法导论》第24章相关内容**

对于最短路径：在循环的过程中，对于每条边(u, v)，如果dist[u] + weight(u, v) < dist[v]，则更新dist[v] = dist[u] + weight(u, v)，确保了每个顶点的距离是最短路径的长度。

对于负权环：循环结束时，如果存在负权环，则在此时再进行一次遍历，仍然存在可以松弛的边。因此，如果在第V次迭代时仍然可以松弛边，则存在负权环。如果不存在负权环，则在第V次迭代后，dist数组将包含最短路径的长度。

因此，Bellman-Ford算法可以找到含有负权边但没有负权回路的图中的最短路径。

时间复杂度

初始化距离数组的时间复杂度为O(V)，其中V是顶点的数量；对每条边进行V-1次松弛操作，每次操作需要遍历所有边。假设图中有E条边，则V-1次松弛操作的时间复杂度为O((V-1)*E) = O(VE)；检测负权回路需要再遍历所有边一次，时间复杂度为O(E)。

综上，Bellman-Ford算法的总时间复杂度为O(V) + O(VE) + O(E) = O(VE)。

空间复杂度

储存距离的距离数组的空间复杂度为O(V)，其中V是顶点的数量；其他辅助变量和数据结构的空间复杂度为常量级别，可以忽略不计。得出Bellman-Ford算法的总空间复杂度为O(V)。

队列优化：SPFA

即 Shortest Path Faster Algorithm。

在很多时候，我们并不需要那么多无用的松弛操作。很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。

那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。

SPFA也可以用于判断s点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少n条边时，说明s点可以抵达一个负环。

from collections import deque


class Edge:
    def __init__(self, v=0, w=0):
        self.v = v
        self.w = w


e = [[Edge() for i in range(maxn)] for j in range(maxn)]
dis = [0x3F3F3F3F] * maxn
cnt = [0] * maxn
vis = [False] * maxn

q = deque()


def spfa(n, s):
    dis[s] = 0
    vis[s] = True
    q.append(s)
    while q:
        u = q.popleft()
        vis[u] = False
        for ed in e[u]:
            v, w = ed.v, ed.w
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                cnt[v] = cnt[u] + 1  # 记录最短路经过的边数
                if cnt[v] >= n:
                    return False
                # 在不经过负环的情况下，最短路至多经过 n - 1 条边
                # 因此如果经过了多于 n 条边，一定说明经过了负环
                if not vis[v]:
                    q.append(v)
                    vis[v] = True

虽然在大多数情况下SPFA跑得很快，但其最坏情况下的时间复杂度为O(nm)，将其卡到这个复杂度也是不难的，所以在面对可能出现特殊情况，尤其是考试时要谨慎使用（在没有负权边时最好使用Dijkstra算法，在有负权边且题目中的图没有特殊性质时，若SPFA是标算的一部分，题目不应当给出Bellman–Ford算法无法通过的数据范围)。