Дейкстра

From

Arthur Martirosyan (2:5061/103.51)

To

Dmitry Volkov

Date

2002-05-04T09:36:53Z

Area

RU.ALGORITHMS

Hello, Dmitry !

 Пятница Май 03 2002 21:11 You wrote:

 DV>  - и алгоритм Дейкстры(Дийкстры), который находит кратчайший путь от
 DV> заданной вершины до всех остальных. Сложность - O(n^2)
 DV>    Область применения: ориентированный граф без ДУГ с отрицательным
 DV> весом. (Сюда, с соответственными ограничениями подойдут и
 DV> неориентированный граф, и даже дерево:)
Вот вот. скажи теперь какие ограничения?
С деревом вообще никаких проблем не вижу.. мне нужно найти путь (оптимальный) из одной вершины в другую в неориентированном графе.

 DV>    Значит, выбрали Дейсктру:) Очень хорошо...
Я ее не выбирал мне ее поручили:)

 DV> [прослушал...]

 DV> Спасибо, конечно, за пример :)
 DV> Но, к сожалению, ты не указал:
 DV> - начальный пункт (как я понимаю, ты имеешь в виду - пункт 1)
да.

 DV> - то, что у тебя выдавала РЕАЛИЗАЦИЯ алгоритма
не оптимальный вес.

 DV> - и то, что выдавал полный перебор
догадайся сам:)

 DV> Я хотя тебе, конечно, верю, но Дейкстре как-то больше верится:))
не сомневаюсь:)

 DV> Вопрос "на засыпку": почему же алгоритм работает правильно?
 DV> ( Далее по тексту "время"="расстояние")
непонял вопроса..

 DV> ЗЫ: Разбор примера оставляю Виталику, благо до меня дошли слухи, что
 DV> он подробно его(пример) разобрал (только слухи - версия почты
 DV> старая:).
Да. мне уже он не один разобрал, и я все понял по теории. за что всем откликнувшимся большое спасибо!


 DV> ЗЫ2: Есть же нормальные книги, типа Кормена и др."Алгоритмы:
 DV> построение и анализ", нестареющий:) Кнут, Шень "Программирование:
 DV> теоремы и задачи" и т.д.
 DV>      Думаю, в описанных там алгоритмах глюков не много. Берешь и
 DV> пишешь на нужном языке...
У меня этих книг не было..

 DV> ЗЫ3: В доказательстве мог наглючить(в чем (не)сильно сомневаюсь), но
 DV> уж Дейкстра-то точно не глючит:)
пример приводился для дерева, но нигде я не находил про оптимальный путь..


... OK!____________________________________________________________________
--- Желаю удачи и всего хорошего, Arthur M. -------------------------------
 * Origin: Dreams go by opposites (2:5061/103.51