五项一起对得上吗
运行下面这段程序:
def build(edges):
g = {}
for a, b, w in edges:
g.setdefault(a, []).append((b, w))
g.setdefault(b, []).append((a, w))
for u in g:
g[u].sort()
return g
import heapq
def dijkstra(g, s):
INF = 10 ** 9
d = {u: INF for u in g}
d[s] = 0
done = set()
pq = [(0, s)]
while pq:
du, u = heapq.heappop(pq)
if u in done:
continue
done.add(u)
for v, w in g[u]:
if du + w < d[v]:
d[v] = du + w
heapq.heappush(pq, (d[v], v))
return d
def bellman(g, s):
INF = 10 ** 9
d = {u: INF for u in g}
d[s] = 0
for _ in range(len(g) - 1):
for u in g:
if d[u] == INF:
continue
for v, w in g[u]:
if d[u] + w < d[v]:
d[v] = d[u] + w
return d
def make(verts):
return {u: u for u in verts}
def find(p, x):
while p[x] != x:
p[x] = p[p[x]]
x = p[x]
return x
def union(p, a, b):
ra, rb = find(p, a), find(p, b)
if ra == rb:
return False
p[ra] = rb
return True
def kruskal(edges, verts):
p = make(verts)
total = 0
picked = []
for a, b, w in sorted(edges, key=lambda e: (e[2], e[0], e[1])):
if union(p, a, b):
total += w
picked.append((a, b))
return total, picked
import heapq
def prim(edges, verts, s):
ad = {u: [] for u in verts}
for a, b, w in edges:
ad[a].append((w, b))
ad[b].append((w, a))
seen = {s}
pq = [(w, s, v) for w, v in ad[s]]
heapq.heapify(pq)
total = 0
picked = []
while pq and len(seen) < len(verts):
w, u, v = heapq.heappop(pq)
if v in seen:
continue
seen.add(v)
total += w
picked.append((u, v))
for w2, x in ad[v]:
if x not in seen:
heapq.heappush(pq, (w2, v, x))
return total, picked
g = build([(0, 1, 2), (0, 2, 1), (1, 3, 3),
(2, 4, 9), (3, 4, 1), (5, 6, 7)])
ok = (dijkstra(g, 0)[4] == 6
and dijkstra({0: [(1, 4), (2, 5)], 1: [(3, 1)], 2: [(1, -3)], 3: []}, 0)[3] == 5
and bellman({0: [(1, 4), (2, 5)], 1: [(3, 1)], 2: [(1, -3)], 3: []}, 0)[3] == 3
and kruskal([(0, 1, 2), (0, 2, 1), (1, 3, 3), (2, 4, 9), (3, 4, 1)], [0, 1, 2, 3, 4])[0] == 7
and prim([(0, 1, 2), (0, 2, 1), (1, 3, 3), (2, 4, 9), (3, 4, 1)], [0, 1, 2, 3, 4], 0)[0] == 7)
print(ok)
全部评论