Дейкстра

From

Arthur Martirosyan (2:5061/103.51)

To

Vitaly Slobodskoy

Date

2002-05-04T09:46:14Z

Area

RU.ALGORITHMS

Hello, Vitaly !

 Пятница Май 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> в котором я довольно подробно рассказал об алгоритме. На каждом новом
 VS> шаге (создавая новый столбец таблицы), мы выбираем из всех строк
 VS> минимальное значение (на первом шаге это 2 у 2-ого пункта, на 2-ом
 VS> шаге это 4 у 3-его пункта, на 3-ем шаге это 4 у 4-ого пункта и т.д.).
 VS> Ту строку, в которой нашли, дальше не рассматриваем, это означает, что
 VS> до пункта, соответствующего этой строке, кратчайший путь найден, далее
 VS> для этого пункта рассматривать нет смысла - вычеркиваем ее (мысленно)
 VS> и ставим эту новую вершину в заголовок нового столбца. Как формируется
 VS> новый столбец, я уже рассказывал. Все строго по алгоритму - машине
 VS> нужно только выбрать минимум и строить на новом шаге
 VS> новый столбец!! Надеюсь, что теперь понятно.
Да! вопросов нет! премногим благодарен!:)


... OK!____________________________________________________________________
--- Желаю удачи и всего хорошего, Arthur M. -------------------------------
 * Origin: Все понять -все простить. (2:5061/103.51