Re: Дейкстра
- From
- Vitaly Slobodskoy (2:5015/128.22)
- To
- Arthur Martirosyan
- Date
- 2002-05-03T21:48:53Z
- Area
- RU.ALGORITHMS
Привет, Arthur!
До меня докатились слухи, что ты что-то там написал о "Дейкстра"! Так, так...
надо бы разобраться...
VS>> Пож-ста, вот решение этой задачи тем алгоритмом, который я приводил:
VS>> 1 | 2 | 3 | 4 | 6 |
VS>> -+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
VS>> 2 | 2* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+---
VS>> 3 | 5 | 4(1-2)* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
VS>> 4 | 4 | 4(1) | 4(1)* |-+--+--+--+--+--+--+--+--+--+--+--+---
VS>> 5 | oo | 9(1-2) | 8(1-2-3) | 8(1-2-3) | 8(1-2-3)* |-+--+--+--+-
VS>> 6 | oo | oo | 7(1-2-3) | 7(1-2-3)* |-+--+--+--+--+--+--+--+---
VS>> 7 | oo | oo | oo | oo | 14(1-2-3-6) | 13(1-2-3-5)
VS>> Вот, как бы и все! Так в чем проблема???
AM> ОК! походу я немного прогнал, вернее делал не так.. все же пара вопросов
AM> осталась, а именно: почему у нас сразу отпадает 4-я вершина, путь дальше
AM> через нее не рассматривается, тогда, как 5-ю вершину мы рассматриваем до
AM> конца и получаем таки через нее кратчайший путь, чем это определяется? по
AM> логике все понятно, но как это обьяснять машине..
Значит ты не уловил алгоритм. Рекомендую еще раз почитать мое письмо, в
котором я довольно подробно рассказал об алгоритме. На каждом новом шаге
(создавая новый столбец таблицы), мы выбираем из всех строк минимальное
значение (на первом шаге это 2 у 2-ого пункта, на 2-ом шаге это 4 у 3-его
пункта, на 3-ем шаге это 4 у 4-ого пункта и т.д.). Ту строку, в которой нашли,
дальше не рассматриваем, это означает, что до пункта, соответствующего этой
строке, кратчайший путь найден, далее для этого пункта рассматривать нет смысла
- вычеркиваем ее (мысленно) и ставим эту новую вершину в заголовок нового
столбца. Как формируется новый столбец, я уже рассказывал. Все строго по
алгоритму - машине нужно только выбрать минимум и строить на новом шаге новый
столбец!!
Надеюсь, что теперь понятно.
Пока, Arthur..
Vitaly Slobodskoy
FIDO: 2:5015/128.22
E-Mail: vital@mail.nnov.ru
--- WP/95 Rel 1.78E (215.0) Reg.
* Origin: ЭТО вам не ЭТО! Понятно! (ДМБ) (2:5015/128.22)