class QNode: def init(self, p, pre): self.vno = p self.pre = pre def Shortpath(G, u, v): visited = [0] * len(G.adjlist) res = [] qu = deque() qu.append(QNode(u, None)) visited[u] = 1 while len(qu) > 0: p = qu.popleft() if p.vno == v: q = p.pre while q != None: res.append(q.vno) q = q.pre res.reverse() return res for j in range(len(G.adjlist[p.vno])): w = G.adjlist[p.vno][j].adjvex if visited[w] == 0: qu.append(QNode(w, p)) visited[w] = 1 return None完善代码并写出主程序有向图并·给出图例

完善代码：

from collections import deque

class QNode:
    def __init__(self, p, pre):
        self.vno = p
        self.pre = pre

def Shortpath(G, u, v):
    visited = [0] * len(G.adjlist)
    res = []
    qu = deque()
    qu.append(QNode(u, None))
    visited[u] = 1
    while len(qu) > 0:
        p = qu.popleft()
        if p.vno == v:
            q = p.pre
            while q != None:
                res.append(q.vno)
                q = q.pre
            res.reverse()
            return res
        for j in range(len(G.adjlist[p.vno])):
            w = G.adjlist[p.vno][j].adjvex
            if visited[w] == 0:
                qu.append(QNode(w, p))
                visited[w] = 1
    return None

主程序：

class EdgeNode:
    def __init__(self, adjvex, weight):
        self.adjvex = adjvex
        self.weight = weight
        self.next = None

class VertexNode:
    def __init__(self, data):
        self.data = data
        self.firstedge = None

class GraphAdjList:
    def __init__(self, vertexlist):
        self.vertexlist = vertexlist
        self.adjlist = [None] * len(vertexlist)
        for i in range(len(vertexlist)):
            self.adjlist[i] = VertexNode(vertexlist[i])
    
    def add_edge(self, start, end, weight):
        node = EdgeNode(end, weight)
        node.next = self.adjlist[start].firstedge
        self.adjlist[start].firstedge = node

# 构造有向图
vertexlist = ['A', 'B', 'C', 'D', 'E']
graph = GraphAdjList(vertexlist)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 3, 30)
graph.add_edge(0, 4, 100)
graph.add_edge(1, 2, 50)
graph.add_edge(2, 4, 10)
graph.add_edge(3, 2, 20)
graph.add_edge(3, 4, 60)

# 计算最短路径
path = Shortpath(graph, 0, 4)
print(path)

图例：

       10       50
 (0)------>(1)------>(2)
  |         ^ \       / ^
  |30     20|   \   /   |10
  V         |   V V   V  |
 (3)------>(4)<-------'
       60      100

其中，数字表示边的权重，箭头表示有向边的方向。例如，从节点 0 到节点 1 有一条权重为 10 的有向边，从节点 1 到节点 2 有一条权重为 50 的有向边，等等。