|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Arthur Martirosyan 2:5061/103.51 04 May 2002 09:46:14 To : Vitaly Slobodskoy Subject : Дейкстра -------------------------------------------------------------------------------- Пятница Май 03 2002 21:48 You wrote: VS>>> Пож-ста, вот решение этой задачи тем алгоритмом, который я VS>>> приводил: VS>>> 1 | 2 | 3 | 4 | 6 | VS>>> -+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- VS>>> +--+- 2 | 2* VS>>> |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-+- 3 | VS>>> 5 | 4(1-2)* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- VS>>> 4 | 4 | 4(1) | 4(1)* VS>>> |-+--+--+--+--+--+--+--+--+--+--+--+-+- 5 | oo | 9(1-2) | VS>>> 8(1-2-3) | 8(1-2-3) | 8(1-2-3)* |-+--+--+--+- 6 | oo | oo VS>>> | 7(1-2-3) | 7(1-2-3)* |-+--+--+--+--+--+--+--+-+- 7 | oo | oo VS>>> | oo | oo | 14(1-2-3-6) | 13(1-2-3-5) VS>>> Вот, как бы и все! Так в чем проблема??? AM>> ОК! походу я немного прогнал, вернее делал не так.. все же пара AM>> вопросов осталась, а именно: почему у нас сразу отпадает 4-я AM>> вершина, путь дальше через нее не рассматривается, тогда, как 5-ю AM>> вершину мы рассматриваем до конца и получаем таки через нее AM>> кратчайший путь, чем это определяется? по логике все понятно, но AM>> как это обьяснять машине.. VS> Значит ты не уловил алгоритм. Рекомендую еще раз почитать мое письмо, VS> в котором я довольно подробно рассказал об алгоритме. Hа каждом новом VS> шаге (создавая новый столбец таблицы), мы выбираем из всех строк VS> минимальное значение (на первом шаге это 2 у 2-ого пункта, на 2-ом VS> шаге это 4 у 3-его пункта, на 3-ем шаге это 4 у 4-ого пункта и т.д.). VS> Ту строку, в которой нашли, дальше не рассматриваем, это означает, что VS> до пункта, соответствующего этой строке, кратчайший путь найден, далее VS> для этого пункта рассматривать нет смысла - вычеркиваем ее (мысленно) VS> и ставим эту новую вершину в заголовок нового столбца. Как формируется VS> новый столбец, я уже рассказывал. Все строго по алгоритму - машине VS> нужно только выбрать минимум и строить на новом шаге VS> новый столбец!! Hадеюсь, что теперь понятно. Да! вопросов нет! премногим благодарен!:) ... OK!____________________________________________________________________ --- Желаю удачи и всего хорошего, Arthur M. ------------------------------- * Origin: Все понять -все простить. (2:5061/103.51 Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/239273cd3ae1c.html, оценка из 5, голосов 10
|