So, let's say I have some code in dijkstras.py that performs dijkstras given a graph G.
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))
and G is something like this:
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}
}
How would we transform the existing algorithm, shortest_path(G, start, end) to utilize a* with the fewest modifications.
What I'm thinking is:
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
But I haven't even ran that yet, so I don't know how it's going to run. I just wanted to bounce this off of someone before I start to code more.
As alfa had suggested, the correct solution is to use cost + cost2 + h(v2).