Алгоритм Белмана-Форда
Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain
-
Romeo
- Сообщения: 3091
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
Готовых исходников под рукой нет. Могу подбросить алгоритм. Насколько мне позволяет судить память постановка задачи следующая:
Постановка:
Задан ориентированный граф без циклов. Из множества вершин выделены две: начальная и конечная. Каждая дуга подписана числом, число интерпритируется как количество времени требуемое на то, чтобы преодолеть растояние между вершинами, которые эта дуга соединяет. Требуется найти наименьший (либо один из наименьших) путей из начальной вершины в конечную вершину.
Алгоритм:
Движемся от конечной вершины назад к начальной (т.е. против ориентации дуг). Каждую вершину метим парой чисел (v, k), где v - номер (либо любой другой идентификатор) следующей вершины, k - расстояние о текущей вершины до конечной вершины. Конечная вершина считается по умолчанию помеченной парой (Nk, 0) (Nk - номер конечной вершины). Алгоритм считается завершённым когда будет помечена начальная вершина.
1. Помечаем конечную вершину парой (Nk, 0).
2. Организуем бесконечный цикл.
3. Пробегаем по всем вершинам графа.
4. Если некая вершина не помечена, а все её следующие вершины (вершины, на которые указывают дугу, исходящие из текущей вершины) помечены, то выполняем следующее.
4.1. Пусть из текущей вершины исходят N дуг. Тогда i изменяется от 1 до N. Вычисляем минимальное из чисел (E(i) +K(i)), где E(i) - длина i-той дуги, K(i) - число k из метки вершины, на которую указывает i-тая дуга.
4.2. Пусть такое минимальное число существует при i = min. Обозначим вершину, в которую указывает дуга номер min через Vmin.
4.3. Метим текущую вершину парой (E(min) + K(min), Vmin).
5. Если начальная вершина не помечена, то переходим на пункт 3.
6. Конец алгоритма.
Основная работа выполнена. Все необходимые вершины графа помечены. Обратим внимание, что пометка начальной вершины содержит численную информацию об искомом пути и о вершине, в которую нужно перейти, чтобы добраться до конечной вершины. Эта вершина также содержит информацию о следующей вершине и т.д. до конечной вершины. Таким образом мы можем не только вывести минимальный путь численно, но также и последовательность вершин в искомом минимальном пути.
Если будут вопросы по алгоритму - всегда помогу.
Постановка:
Задан ориентированный граф без циклов. Из множества вершин выделены две: начальная и конечная. Каждая дуга подписана числом, число интерпритируется как количество времени требуемое на то, чтобы преодолеть растояние между вершинами, которые эта дуга соединяет. Требуется найти наименьший (либо один из наименьших) путей из начальной вершины в конечную вершину.
Алгоритм:
Движемся от конечной вершины назад к начальной (т.е. против ориентации дуг). Каждую вершину метим парой чисел (v, k), где v - номер (либо любой другой идентификатор) следующей вершины, k - расстояние о текущей вершины до конечной вершины. Конечная вершина считается по умолчанию помеченной парой (Nk, 0) (Nk - номер конечной вершины). Алгоритм считается завершённым когда будет помечена начальная вершина.
1. Помечаем конечную вершину парой (Nk, 0).
2. Организуем бесконечный цикл.
3. Пробегаем по всем вершинам графа.
4. Если некая вершина не помечена, а все её следующие вершины (вершины, на которые указывают дугу, исходящие из текущей вершины) помечены, то выполняем следующее.
4.1. Пусть из текущей вершины исходят N дуг. Тогда i изменяется от 1 до N. Вычисляем минимальное из чисел (E(i) +K(i)), где E(i) - длина i-той дуги, K(i) - число k из метки вершины, на которую указывает i-тая дуга.
4.2. Пусть такое минимальное число существует при i = min. Обозначим вершину, в которую указывает дуга номер min через Vmin.
4.3. Метим текущую вершину парой (E(min) + K(min), Vmin).
5. Если начальная вершина не помечена, то переходим на пункт 3.
6. Конец алгоритма.
Основная работа выполнена. Все необходимые вершины графа помечены. Обратим внимание, что пометка начальной вершины содержит численную информацию об искомом пути и о вершине, в которую нужно перейти, чтобы добраться до конечной вершины. Эта вершина также содержит информацию о следующей вершине и т.д. до конечной вершины. Таким образом мы можем не только вывести минимальный путь численно, но также и последовательность вершин в искомом минимальном пути.
Если будут вопросы по алгоритму - всегда помогу.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
-
BAHTY3
- Сообщения: 104
- Зарегистрирован: 30 авг 2005, 02:53
- Откуда: Санкт-Петербург
- Контактная информация:
Ты прав, но мне нужен релиз алгоритма....Romeo писал(а):Готовых исходников под рукой нет. Могу подбросить алгоритм. Насколько мне позволяет судить память постановка задачи следующая:
Постановка:
Задан ориентированный граф без циклов. Из множества вершин выделены две: начальная и конечная. Каждая дуга подписана числом, число интерпритируется как количество времени требуемое на то, чтобы преодолеть растояние между вершинами, которые эта дуга соединяет. Требуется найти наименьший (либо один из наименьших) путей из начальной вершины в конечную вершину.
И не один из наименьших путей... Алгоритм подрузомивает выдачу 2-х значений: TRUE когда не сушествует отрицательного веса пути и FALSE когда таковой имеется....
Я уже мес гидет парюсь над этим, кучу книг прочитал ареализовать пока так и не смог (сам пока не написал, так ересь одна), да и релиза ни гиде не достать.....
Жизнь ― это то, что с нами происходит, пока мы строим планы.© Джон Леннон.
-
BAHTY3
- Сообщения: 104
- Зарегистрирован: 30 авг 2005, 02:53
- Откуда: Санкт-Петербург
- Контактная информация:
А есть у когонить исходники... хоть и не полные.... хотябы просто на алгоритм отыскания кратчайшего пути на графе из заданной точки....
Жизнь ― это то, что с нами происходит, пока мы строим планы.© Джон Леннон.