Is there an admissable heuristic for performing A* (A-star) search on a Directed Graph with cycles?

Question

I am working on a school project which requires us to generate a random digraph with weighted edges and perform a number of graph traversal techniques to find one of the target nodes (marked in green) from the starting node (marked in red). A sample graph can be seen below: Randomly Generated Digraph

I've managed to implement the requested uninformed graph search algorithms (Depth-First Search, Breadth-First Search, Iterative Deepening Search and Uniform Cost Search). However, we were also asked to perform A* (A-star) search on this graph and I am struggling to find an admissable heuristic since positional data is required for the Manhattan or Euclidian distances.

Is there a valid heuristic which can be used or is it the case of not having enough information?

Answer 1

An acceptable heuristic is that the cost is some constant - such as 0.

This will turn A* search into Uniform Cost Search.