python - 将dijkstras转换为a * python

所以，假设我在dijkstras.py中有一些代码，在给定图g的情况下执行dijkstras。

def shortest_path(G, start, end):
   def flatten(L):       # Flatten linked list of form [0,[1,[2,[]]]]
      while len(L) > 0:
         yield L[0]
         L = L[1]
   q = [(0, start, ())]  # Heap of (cost, path_head, path_rest).
   visited = set()       # Visited vertices.
   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): #where h is the heuristic function
   def flatten(L):       # Flatten linked list of form [0,[1,[2,[]]]]
      while len(L) > 0:
         yield L[0]
         L = L[1]
   q = [(0, start, ())]  # Heap of (cost, path_head, path_rest).
   visited = set()       # Visited vertices.
   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)) #modification here

但我还没跑，所以我不知道怎么跑。我只是想在我开始编写更多代码之前把它从某人身上弹下来。

最佳答案

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