In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to introduce preferred paths.
So that, in the following graph, the final route would be the one in green instead of the one in grey:
The issue with this approach is that using euclidean distance makes the heuristic not admissible anymore. As an example, if we're at point A on the graph above, the euclidean distance from A to Finish can be higher than the eventual cost from A to B to Finish, considering the lowered cost between AB.
As a result, when putting many preferred routes on a much more complex graph than the one above, then the optimality of the solution is not guaranteed anymore and $A^*$ can sometimes give very erratic results.
The final objective for this question is to come up with a way to make some paths slightly preferred over the absolute, euclidean shortest paths, when trying to predict routes, in order to model non-geographical constraints, like density of traffic or tolls.
I can think of two main ways of avoiding the exposed issue:
- change the heuristic to make it admissible again (but then, how?)
- use a different strategy to deal with preferred path
Any help would be appreciated.