Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Поиск минимального пути в ор графе

Автор: coach 16.3.2007, 16:15

Есть ли какой нибудь алгоритм, который выдает минимальный путь с минимальным  КОЛИЧЕСТВОМ вершин в ориентированном графе.

Автор: Tectoder 16.3.2007, 16:17

coach, чем не подходит метод Дейкстры, в котором длина каждого ребра положена равной одному?

Автор: Earnest 19.3.2007, 14:45

При равных весах достаточно простого поиска в ширину, вычисляющего длину пути до каждого узла.

Автор: pablo 19.3.2007, 17:34

Цитата(coach @  16.3.2007,  16:15 ) Есть ли какой нибудь алгоритм, который выдает минимальный путь с минимальным  КОЛИЧЕСТВОМ вершин в ориентированном графе.   Всё зависит от того, какие условия поиска. Если есть неотрицательные веса, то можно применить Алгоритм Дейкстры, если веса все равны то можно и простый поиском в ширину. Если есть отрицательные веса, то тогда надо применять алгоритм Белмана - Форда. Если же надо найти все пути от каждой вершины к каждой, то можно применить Алгоритм Флойда-Варшала.  Так что всё зависит от критериев поиска.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)