Для отрицательных ребер, но без отрицательного цикла, Bellman-Ford предпочтительнее, если вы находите кратчайший путь из одного источника.Для всей пары можно использовать Floyd-Warshell.Но алгоритм Дейкстры не используется, когда в графе есть отрицательное ребро.
Не удалось прокомментировать алгоритм поиска A *.Я не полностью осознаю это.