Romeo » 30 авг 2005, 11:44
Готовых исходников под рукой нет. Могу подбросить алгоритм. Насколько мне позволяет судить память постановка задачи следующая:
Постановка:
Задан ориентированный граф без циклов. Из множества вершин выделены две: начальная и конечная. Каждая дуга подписана числом, число интерпритируется как количество времени требуемое на то, чтобы преодолеть растояние между вершинами, которые эта дуга соединяет. Требуется найти наименьший (либо один из наименьших) путей из начальной вершины в конечную вершину.
Алгоритм:
Движемся от конечной вершины назад к начальной (т.е. против ориентации дуг). Каждую вершину метим парой чисел (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. Конец алгоритма.
Основная работа выполнена. Все необходимые вершины графа помечены. Обратим внимание, что пометка начальной вершины содержит численную информацию об искомом пути и о вершине, в которую нужно перейти, чтобы добраться до конечной вершины. Эта вершина также содержит информацию о следующей вершине и т.д. до конечной вершины. Таким образом мы можем не только вывести минимальный путь численно, но также и последовательность вершин в искомом минимальном пути.
Если будут вопросы по алгоритму - всегда помогу.
Готовых исходников под рукой нет. Могу подбросить алгоритм. Насколько мне позволяет судить память постановка задачи следующая:
[b]Постановка[/b]:
Задан ориентированный граф без циклов. Из множества вершин выделены две: [i]начальная[/i] и [i]конечная[/i]. Каждая дуга подписана числом, число интерпритируется как количество времени требуемое на то, чтобы преодолеть растояние между вершинами, которые эта дуга соединяет. Требуется найти наименьший (либо один из наименьших) путей из начальной вершины в конечную вершину.
[b]Алгоритм[/b]:
Движемся от конечной вершины назад к начальной (т.е. против ориентации дуг). Каждую вершину метим парой чисел (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. Конец алгоритма.
Основная работа выполнена. Все необходимые вершины графа помечены. Обратим внимание, что пометка начальной вершины содержит численную информацию об искомом пути и о вершине, в которую нужно перейти, чтобы добраться до конечной вершины. Эта вершина также содержит информацию о следующей вершине и т.д. до конечной вершины. Таким образом мы можем не только вывести минимальный путь численно, но также и последовательность вершин в искомом минимальном пути.
Если будут вопросы по алгоритму - всегда помогу.