假设我在dijkstras.py中有一些代码，用于在给定图G的情况下执行Dijkstra算法。

def shortest_path(G, start, end):   def flatten(L):       # 展平形如[0,[1,[2,[]]]]的链表      while len(L) > 0:         yield L[0]         L = L[1]   q = [(0, start, ())]  # 堆，包含(cost, path_head, path_rest)。   visited = set()       # 已访问的顶点。   while True:      (cost, v1, path) = heapq.heappop(q)      if v1 not in visited:         visited.add(v1)         if v1 == end:            return [('cost', cost)] + [('path', list(flatten(path))[::-1] + [v1])]         path = (v1, path)         for (v2, cost2) in G[v1].iteritems():            if v2 not in visited:               heapq.heappush(q, (cost + cost2, v2, path))

图G的结构如下：

 G = {                's': {'u':10, 'x':5},                'u':{'v':1, 'x':2},                'v':{'y':4},                'x':{'u':3, 'v':9, 'y':2},                'y': {'s':7, 'v':6}        }

我们如何以最少的修改将现有的算法shortest_path(G, start, end)转换为使用A*算法？

我的想法是：

def shortest_path(G, start, end, h): #其中h是启发式函数   def flatten(L):       # 展平形如[0,[1,[2,[]]]]的链表      while len(L) > 0:         yield L[0]         L = L[1]   q = [(0, start, ())]  # 堆，包含(cost, path_head, path_rest)。   visited = set()       # 已访问的顶点。   while True:      (cost, v1, path) = heapq.heappop(q)      if v1 not in visited:         visited.add(v1)         if v1 == end:            return [('cost', cost)] + [('path', list(flatten(path))[::-1] + [v1])]         path = (v1, path)         for (v2, cost2) in G[v1].iteritems():            if v2 not in visited:               heapq.heappush(q, (cost + cost2 + h(v2), v2, path)) #在这里进行了修改

但我还没有运行这段代码，所以我不知道它会如何运行。我只是想在开始更多编码之前与某人讨论一下这个想法。

回答：

正如alfa所建议的，正确的解决方案是使用cost + cost2 + h(v2)。