算法导论第二十五章习题解答

def PARENT(i): return (i-1) // 2 def LEFT(i): return i*2 + 1 def RIGHT(i): return i*2 + 2 def MIN_HEAPIFY(A, i, size): l = LEFT(i) r = RIGHT(i) if l < size and A[l] < A[i]: largest = l else: largest = i if r < size and A[r] < A[largest]: largest = r if largest != i: temp = A[i] A[i] = A[largest] A[largest] = temp MIN_HEAPIFY(A, largest, size) def BUILD_MIN_HEAP(A): size = len(A) for i in range(len(A)//2, -1, -1): MIN_HEAPIFY(A, i, size) def HEAP_MINIMUM(A): return A[0] def HEAP_EXTRACT_MIN(A, size): assert(size > 0) iMIN = A[0] size = size - 1 A[0] = A[size] MIN_HEAPIFY(A, 0, size) return iMIN def HEAP_DECREASE_KEY(A, i, key): assert(A[i] == key) A[i] = key while i > 0 and PARENT(i) >= 0 and A[PARENT(i)] > A[i]: temp = A[i] A[i] = A[PARENT(i)] A[PARENT(i)] = temp i = PARENT(i) def MIN_HEAP_INSERT(A, key): A.append(float("inf")) HEAP_DECREASE_KEY(A, len(A)-1, key) #模拟获取index的功能，假设为常数时间 def HEAP_INDEX(A, size, x): for i in range(0, size): if A[i] == x: return i #====================================================== WHITE, GRAY, BLACK = (0, 1, 2) def PRINT_GRAPH_MATRIX(G): format_str = "%-8.2f" * len(G) for row in G: print(format_str % tuple(row)) def CREATE_GRAPH_MATRIX(n, val = None): g = [[val for i in range(n)] for j in range(n)] return g class Vertex: def __init__(self, u): self.value = u self.vertexs = [] self.isInGraph = False self.pi = None self.d = float("inf") self.h = float("inf") self.color = WHITE def __lt__(self, u): return self.d < u.d class Edge: def __init__(self, u, v, w): self.fromV = u self.toV = v self.weight = w class Graph: def __init__(self): self.vertexs = [] self.edges = [] def weight(edges, u, v): for e in edges: if e.fromV == u and e.toV == v: return e.weight print(u.value, v.value) return None def INITGRAPH(G, edges): for e in edges: if not e.fromV.isInGraph: G.vertexs.append(e.fromV) e.fromV.isInGraph = True if not e.toV.isInGraph: G.vertexs.append(e.toV) e.toV.isInGraph = True G.edges.append(e) e.fromV.vertexs.append(e.toV) def INITIALIZE_SINGLE_SOURCE(G, s): for v in G.vertexs: v.d = float("inf") v.pi = None s.d = 0 s.pi = None def DIJKSTRA(G, s): def RELAX(Q, size, u, v, edges): if v.d > u.d + weight(edges, u, v): index = HEAP_INDEX(Q, size, v) v.d = u.d + weight(edges, u, v) HEAP_DECREASE_KEY(Q, index, v) v.pi = u print("relax", u.value, v.value, v.d) INITIALIZE_SINGLE_SOURCE(G, s) S = [] Q = [] for v in G.vertexs: Q.append(v) size = len(Q) BUILD_MIN_HEAP(Q) while size != 0: u = HEAP_EXTRACT_MIN(Q, size) size = size - 1 S.append(u) for v in u.vertexs: RELAX(Q, size, u, v, G.edges) def BELLMAN_FORD(G, s): def RELAX(u, v, edges): if v.d > u.d + weight(edges, u, v): v.d = u.d + weight(edges, u, v) v.pi = u print(u.value, v.value, v.d) INITIALIZE_SINGLE_SOURCE(G, s) for i in range(1, len(G.vertexs)-1): for edge in G.edges: RELAX(edge.fromV, edge.toV, G.edges) for edge in G.edges: if edge.toV.d > edge.fromV.d + weight(G.edges, edge.fromV, edge.toV): return False return True def INSERT_SOURCE_VERTEX(G): s = Vertex(0) for v in G.vertexs: G.edges.append(Edge(s, v, 0)) s.vertexs.append(v) s.isInGraph = True G.vertexs.append(s) return s def CREATE_NEW_WEIGHT_GRAPH(G): new_edges = [] old_edges = G.edges for v in G.vertexs: v.h = v.d for e in old_edges: w = e.weight + e.fromV.h - e.toV.h new_edges.append(Edge(e.fromV, e.toV, w)) G.edges = new_edges return old_edges def JOHNSON(G): n = len(G.vertexs) s = INSERT_SOURCE_VERTEX(G) if BELLMAN_FORD(G, s): CREATE_NEW_WEIGHT_GRAPH(G) D = CREATE_GRAPH_MATRIX(n, float("inf")) for u in G.vertexs: if u == s: continue DIJKSTRA(G, u) for v in G.vertexs: if v == s: continue D[u.value-1][v.value-1] = v.d + v.h - u.h return D if __name__ == "__main__": node1 = Vertex(1) node2 = Vertex(2) node3 = Vertex(3) node4 = Vertex(4) node5 = Vertex(5) node6 = Vertex(6) edges = [] edges.append(Edge(node1, node5, -1)) edges.append(Edge(node2, node1, 1)) edges.append(Edge(node2, node4, 2)) edges.append(Edge(node3, node2, 2)) edges.append(Edge(node3, node6, -8)) edges.append(Edge(node4, node1, -4)) edges.append(Edge(node4, node5, 3)) edges.append(Edge(node5, node2, 7)) edges.append(Edge(node6, node2, 5)) edges.append(Edge(node6, node3, 10)) G = Graph() INITGRAPH(G, edges) D = JOHNSON(G) PRINT_GRAPH_MATRIX(D)