Существует ли допустимая эвристика для выполнения поиска A* (A-star) в ориентированном графе с циклами?

Я работаю над школьным проектом, который требует от нас создания случайного орграфа со взвешенными ребрами и выполнения ряда методов обхода графа, чтобы найти один из целевых узлов (отмечен зеленым) от начального узла (отмечен красным). Пример графика можно увидеть ниже:
Случайно сгенерированный диграф

Мне удалось реализовать запрошенные алгоритмы поиска неинформированного графа (поиск в глубину, поиск в ширину, итеративный поиск с углублением и поиск по единой стоимости). Однако нас также попросили выполнить поиск A * (A-star) на этом графике, и я изо всех сил пытаюсь найти допустимую эвристику, поскольку для манхэттенских или евклидовых расстояний требуются позиционные данные.

Существует ли действующая эвристика, которую можно использовать, или дело в недостатке информации?

Решение проблемы

Приемлемой эвристикой является то, что стоимость является некоторой константой, например 0.

Это превратит поиск A* в поиск по унифицированной стоимости.