Algorithm ShortestPath(G, s): [Input]: A weighted graph G with nonnegative edge weights, and a distinguished vertex s of G [Output]: The length of a shortest path from s to v for each vertex v of G [Algorithm]: # 初始化, 点 s 标签为 0, 其他点均为正无穷 Initialize D[s] = 0and D[v] = +inf for each vertex v != s.
Q = PriorityQueue() # 优先级队列: key = D[v] value = v 且先包含所有点 whilenot Q.isEmpty() do # Q 是“非云” Q.remove(u) 相当于点 u 入云 u = value returned by Q.remove_min() # 挑出最小的 D[u] for each vertex v adjacent to u such that v isin Q do # 所有与 u 相邻的 v if D[u] + w(u, v) < D[v] then D[v] = D[u] + w(u, v) Change to D[v] the key of vertex v in Q # 边松弛操作, 改变 D[v] return the label of each vertex v
# 初始化所有点 v 的标签 d[v] for v in g.vertices(): if v is src: d[v] = 0# 源点为 0 else: d[v] = float('inf') # 暂时记为正无穷大 pqlocator[v] = pq.add(d[v], v) # (最短路 d[v], 点 v) 放入优先级队列, 同时记录位置在 pqlocator
whilenot pq.is_empty(): key, u = pq.remove_min() # 取出云外最小路 min d[v] out of cloud cloud[u] = key # 放入云内 cloud[u] = key 因为存的时候 key = d[u] del pqlocator[u] # pqlocator 删去点 u 在优先级队列里的位置
for e in g.incident_edges(u): # 所有通向点 u 的边 e v = e.opposite(u) # 对面的点 v if v notin cloud: # 若 v 不在云里 wgt = e.element() # 边权重 if d[u] + wgt < d[v]: # 比较 d[v] = d[u] + wgt # 更新为最小值 pq.update(pqlocator[v], d[v], v) # 同时更新优先级队列里的 (d[v], v) return cloud
if __name__ == '__main__': g = Graph(directed=False)
A = g.insert_vertex("A") B = g.insert_vertex("B") C = g.insert_vertex("C") D = g.insert_vertex("D") E = g.insert_vertex("E") F = g.insert_vertex("F")
AB = g.insert_edge(A, B, 8) AC = g.insert_edge(A, C, 2) AD = g.insert_edge(A, D, 4) BC = g.insert_edge(B, C, 7) CD = g.insert_edge(C, D, 1) BE = g.insert_edge(B, E, 2) CE = g.insert_edge(C, E, 3) CF = g.insert_edge(C, F, 9) DF = g.insert_edge(D, F, 5)
toA_shortest_path = shortest_path_lengths(g=g, src=A) for k in toA_shortest_path: print(f"From Vertex {k.element()}: {toA_shortest_path[k]}")
1 2 3 4 5 6
From Vertex A: 0 From Vertex C: 2 From Vertex D: 3 From Vertex E: 5 From Vertex B: 7 From Vertex F: 8
Algorithm FloydWarshall(G) [Input]: digraph G [Output]: transitive closure G* of G [Algorithm]:
i = 1 forall v = G.vertices() # 所有顶点 # 标记所有点 denote v as vi i = i + 1
G{0} = G # 初始 G{0} for k = 1 to n do G{k} = G{k−1} for i = 1 to n (i != k) do # vi for j = 1 to n (j != i, k) do # vi # G{k-1} 中 vi vk 相邻, vk vj 相邻 if G{k−1}.areAdjacent(vi, vk) and G{k−1}.areAdjacent(vk, vj) # 但 G{k} 中 vi vj 不相邻 ifnot G{k}.areAdjacent(vi, vj) # 则在 G{k} 中连边 vi vj G{k}.insertDirectedEdge(vi, vj, k) return G{n}
deffloyd_warshall_shortest_path(g: Graph) -> dict: """ 使用 Floyd-Warshall 算法计算图中所有顶点对的最短路径距离 :param g: 图 Graph 类 :return: 返回一个字典 {u: {v: distance}} 其中 distance 是 u 到 v 的最短距离 如果 u 和 v 之间不可达 distance = math.inf """ verts = list(g.vertices()) # 获取所有顶点 n = len(verts)
# 初始化距离字典, 格式为 dist[u][v] = distance dist = {u: {v: math.inf for v in verts} for u in verts}
# 设置对角线为 0 for u in verts: dist[u][u] = 0
# 初始化直接相连的边 for u in verts: for v in verts: edge = g.get_edge(u, v) if edge isnotNone: dist[u][v] = edge.element()
# Floyd-Warshall 算法 for k in verts: # 中间点 k for u in verts: # 起点 u for v in verts: # 终点 v # 如果经过 k 的路径更短，则更新 if dist[u][k] + dist[k][v] < dist[u][v]: dist[u][v] = dist[u][k] + dist[k][v]
# 如果是无向图，按 start < end 输出，避免重复 ifnot g.is_directed(): verts_sorted = sorted(verts, key=lambda x: x.element()) # 按顶点名称排序 for i inrange(len(verts_sorted)): start = verts_sorted[i] for j inrange(i + 1, len(verts_sorted)): end = verts_sorted[j] distance = shortest_path_dict[start][end] print(f"{start.element()} -> {end.element()}: " f"{distance if distance != math.inf else'No Path'}")
# 如果是有向图，输出所有可能的 start -> end else: for start in verts: for end in verts: if start != end: # 避免输出自己到自己的情况 distance = shortest_path_dict[start][end] print(f"{start.element()} → {end.element()}: " f"{distance if distance != math.inf else'No Path'}")
if __name__ == '__main__': print("=" * 15, "Shortest Path", "=" * 15) g = Graph(directed=True)
A = g.insert_vertex("A") B = g.insert_vertex("B") C = g.insert_vertex("C") D = g.insert_vertex("D") E = g.insert_vertex("E") F = g.insert_vertex("F")
AB = g.insert_edge(A, B, 8) AC = g.insert_edge(A, C, 2) AD = g.insert_edge(A, D, 4) BC = g.insert_edge(B, C, 7) CD = g.insert_edge(C, D, 1) BE = g.insert_edge(B, E, 2) CE = g.insert_edge(C, E, 3) CF = g.insert_edge(C, F, 9) DF = g.insert_edge(D, F, 5)
=============== Shortest Path =============== A → B: 8 A → C: 2 A → D: 3 A → E: 5 A → F: 8 B → A: No Path B → C: 7 ...
3 最小生成树 Prim-Jarnik & Kruskal
3.1 最小生成树
生成子图（spanning graph）：图 G 的生成子图包含其所有顶点。生成树（spanning tree）：为树的生成子图
最小生成树（minimum spanning tree/MST）：加权图的总权重最小的生成树
最小生成树的性质：
环性质（cycle property ）：令 T 为加权图 G 的一棵最小生成树，令 e 为图 G 中不属于 T 的边，且令 e 与 T 形成的环为 C 。则有：对环上的每一条边 f 均有 $weight(f) \leq weight(e)$ 。
因为如果可以找到一条边使得 $weight(f) > weight(e)$ 则用边 e 取代 f 即可得到一棵总权重更小的生成树。
分割性质（partition property）：考虑将 G 的所有顶点分为两个集合 U 和 V 的一个分割。令 e 为连接这两部分顶点集合的权重最小的边。则有：存在一棵包含边 e 的 G 的最小生成树。
考虑 G 的一棵最小生成树 T ，如果 T 不包含 e，考虑由 e 和 T 构成的环 C，及 T 中连接 U 和 V 的边 f 。由最小生成树的环性质可得：$weight(f) \leq weight(e)$ ，$weight(f) = weight(e)$ 。用 e 替代 f 即可得到另一棵最小生成树。
有两种解决最小生成树问题的经典算法，均为贪心算法：
Prim-Jarnik 算法
Kruskal 算法
3.2 Prim-Jarnik 算法
Prim 算法从一个“根”顶点 s 出发，以构建“云”的方式逐步形成一棵最小生成树，其思想与 Dijkstra 算法类似。
defMST_PrimJarnik(g): """最小生成树 返回边列表""" d = {} # d[v] is bound on distance to tree tree = [] # 最小生成树的边序列 pq = AdaptableHeapPriorityQueue() # d[v] maps to value (v, e=(u,v)) pqlocator = {} # {Vertex: pq's locator}
# 初始化标签 d[v] for v in g.vertices(): iflen(d) == 0: # d 空, 没有节点 d[v] = 0# 则设置一个起点 else: d[v] = float('inf') # positive infinity pqlocator[v] = pq.add(d[v], (v, None))
whilenot pq.is_empty(): key, value = pq.remove_min() u, edge = value # unpack tuple from pq del pqlocator[u] # u is no longer in pq
if edge isnotNone: tree.append(edge) # add edge to tree for link in g.incident_edges(u): v = link.opposite(u) # 寻找邻点 if v in pqlocator: # thus v not yet in tree # see if edge (u,v) better connects v to the growing tree wgt = link.element() if wgt < d[v]: # better edge to v? d[v] = wgt # update the distance pq.update(pqlocator[v], d[v], (v, link)) # update the pq return tree
3.2.2 性能分析
图操作：我们访问了所有顶点，并在将顶点放入“云”这一步访问了所有的边
标签操作：我们查询/修改一个顶点 z 的标签 O(deg(z)) 次，我们可以在 O(1) 的时间内完成这一工作
defunion(self, p, q): a = self.find(p) b = self.find(q) if a isnot b: if a._size > b._size: b._parent = a a._size += b._size else: a._parent = b b._size += a._size
for v in g.vertices(): position[v] = forest.make_group(v) # 每个点建群 for e in g.edges(): pq.add(e.element(), e) # 存储所有边 key = edge's weight
size = g.vertex_count() whilelen(tree) != size - 1andnot pq.is_empty(): weight, edge = pq.remove_min() # 最小权重边 u, v = edge.endpoints() a = forest.find(position[u]) b = forest.find(position[v]) if a != b: tree.append(edge) # 边加入最小生成树 forest.union(a, b) # 合并群 return tree
3.3.4 性能分析
使用这样的 Partition 结构存储集群，则：
集群的合并使用 union 方法
寻找集群的位置使用 find 方法
Kruskal 算法的运行时间为 O((n + m) log n)
优先级队列操作运行时间：O(m log n)
集群定位、合并操作运行时间：O(n log n)
4 拓扑排序
4.1 拓扑排序与有向非循环图 DAG
拓扑排序：使得有向图 G 的任何有向路径以增加的顺序遍历顶点（为顶点编号）。同一幅图可能有多个拓扑排序。
拓扑排序可以用来检查图是否为有向非循环图 DAG （即没有有向环），当拓扑排序没有包含所有点时，说明这个图存在有向循环/圈。
# 1. 获取所有点, 记录 {Vertex: in-degree} for u in g.vertices(): incount[u] = g.degree(u, False) if incount[u] == 0: # 入度为 0 可以作为起始点, 不受其他影响 ready.append(u)
# 2. 对每个点处理, 清空 ready whilelen(ready) > 0: u = ready.pop() topo.append(u) # 获取 u 的邻接点 for e in g.incident_edges(u): v = e.opposite(u) incount[v] -= 1# 前一点已加入 topo 结果, 则 v 度减 1 if incount[v] == 0: ready.append(v) # 直到此时 v 也成为了"起点" return topo
