Здравствуйте, AZIZE, Вы писали:

AZI>Прошу прощения, но я забыл упомянуть в вопросе, что иеются и отрицательные вершины
Обычно стоимость назначена не вершинам, а рёбрам. Но если стоимость назначена именно вершине, то можно преобразовать эту вершину в ребро и тогда задача сведётся к обычному случаю (стоимость назначена только рёбрам).
Если есть рёбра с отрицательной стоимостью, то тогда, насколько я знаю, надо использовать алгоритм Флойда-Уоршолла.

AZI>Не могли бы вы дать мне ссылки на алгоритмы которые вы описали или более подробно их описать
Во-первых, есть классическая книга «Алгоритмы: построение и анализ»

Автор(ы): Томас Кормен, Чарльз Лейзерсон, Рональд Ривест
Эта книга — перевод учебника по курсу построения и анализа эффективных алгоритмов, написанного в Массачусетском технологическом институте. В ней разбираются важнейшие классы быстрых алгоритмов и приемы их построения. Изложение подробное и математически строгое. Книгу можно использовать в качестве учебника и справочника; она будет полезна как студентам, так и профессионалам в области информатики и программирования.

(Кормен, Лейзерсон, Ривест). Там описаны поиск в ширину, алгоритм Дейкстры, алгоритм Флойда-Уоршолла и ещё много чего. Но вот A* я там не видел .
Во-вторых, есть русскоязычный сайт про алгоритмы algolist.ru, там есть раздел «Графы и маршруты».
В-третьих, есть универсальные поисковики (например, Google). Они выдают полезные ссылки по запросу «A* algorithm».