h(x) be your heuristic for node
h*(x) the perfect heuristic (where you know the EXACT distance to your goal from
0 < h(x) <= h*(x) for every node of the graph then the heuristic is admissible.
h(x) = 0 you have no information and A* degenerates into
h(x) = h*(x) you do know the answer
and therefore there is no problem to solve.
- The closer
h(x) is to
h*(x), the shorter A* will take to find the shortest path.
h(x) > h*(x) then your solution is not guaranteed to be optimal (i.e. found path might not be the least cost path.)
Some well known heuristics that meet this criteria are Euclidean distance and Manhattan distance.
h(x) <= d(x,y) + h(y) for every edge
x, y of the graph, where
d(x,y) is the actual distance between the nodes, the heuristic is said to be monotone (or consistent) and no nodes need to be processed more than once.
Said that, any heuristic that doesn't overestimate the distance will do fine. It doesn't matter if your nodes have different weights, that's part of
d(x) (the actual distance of your walked path), not
h(x) which is just a roughly estimate to favor some paths before others. As long as
h(x) (remember, it's just an estimate) is
< h*(x) you'll get the optimal route.
In an ordinary case, I would just use the same way I got to goal to go back, but since one of the streets could have been a one-way, that may not be possible.
It doesn't really matter if you have one-way streets. Your graph can be directed and you just don't let your algorithm generate that route. You don't need to go back while executing A*, because it would become a longer route that if you didn't take that path in the first place. If you want to go back from
NODE that's just a new search in your search space, not a single problem.
Regarding MSalters' notice, I don't think you can derive a heuristic in a graph with just weights. You need a problem that meets some kind of criteria that offers extra information to guess from. If you only have weights, then you can't to it better than Dijkstra's because you lack any more information. It depends entirely on the problem domain, so a broad answer that fits any graph can't be given.