Люди! нужно максимум способов нахождения максимального и минимального пути в графе от вершины А к вершине В;
В случае максимального, исключать циклический поиск;
Методы Краскала, Прима, в ширину и в глубину можно не предлагать они уже реализованы
заранее спасибо

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

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

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

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

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

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

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

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

Здравствуйте, Пётр Седов,
Огромное вам спасибо за Ваш ответ
Прошу прощения, но я забыл упомянуть в вопросе, что иеются и отрицательные вершины
Не могли бы вы дать мне ссылки на алгоритмы которые вы описали или более подробно их описать
Заранее благодарен
AZIZE

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

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

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

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

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