Здравствуйте, AZIZE.
Вкратце про поиск кратчайшего (то есть наименьшей стоимости) пути в графе.

Алгоритм Дейкстры (Dijkstra) ищет кратчайшие пути от исходной вершины до всех остальных вершин. Если целевая вершина одна, то в общем случае это не упрощает задачу (хотя уменьшает количество итераций главного цикла; как только кратчайший путь до целевой вершины найден, алгоритм можно завершить). Алгоритм Дейкстры требует (для корректной работы), чтобы стоимости всех рёбер были ≥ 0. Если стоимости всех рёбер одинаковы, то алгоритм Дейкстры сводится к поиску в ширину.

Алгоритм A* ищет кратчайший путь от исходной вершины до целевой вершины. Алгоритму нужна эвристическая функция (обычно её обозначают буквой «h», видимо от слова «heuristic»), оценивающая стоимость кратчайшего пути от какой-то вершины до целевой вершины:

стоимость кратчайшего пути от какой-то вершины до целевой вершины ≥ ЭвристическаяФункция(какая-то вершина)

Легче всего придумать эвристическую функцию, когда граф разложен на какой-нибудь геометрии и стоимость ребра пропорциональна геометрической длине ребра. Если эвристическая функция тривиальная:

стоимость кратчайшего пути от какой-то вершины до целевой вершины ≥ 0

(то есть ЭвристическаяФункция(какая-то вершина) всегда равна 0), то A* сводится к алгоритму Дейкстры, при этом A* равномерно ползёт во все стороны от исходной вершины (нетривиальная эвристическая функция направляет A* в первую очередь в сторону целевой вершины).

Алгоритм Флойда-Уоршолла (Floyd-Warshall) ищет кратчайшие пути между всеми парами вершин. Вроде умеет справляться с отрицательными стоимостями рёбер.