|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Arthur Martirosyan 2:5061/103.51 04 May 2002 09:36:53 To : Dmitry Volkov Subject : Дейкстра -------------------------------------------------------------------------------- Пятница Май 03 2002 21:11 You wrote: DV> - и алгоритм Дейкстры(Дийкстры), который находит кратчайший путь от DV> заданной вершины до всех остальных. Сложность - O(n^2) DV> Область применения: ориентированный граф без ДУГ с отрицательным DV> весом. (Сюда, с соответственными ограничениями подойдут и DV> неориентированный граф, и даже дерево:) Вот вот. скажи теперь какие ограничения? С деревом вообще никаких проблем не вижу.. мне нужно найти путь (оптимальный) из одной вершины в другую в неориентированном графе. DV> Значит, выбрали Дейсктру:) Очень хорошо... Я ее не выбирал мне ее поручили:) DV> [прослушал...] DV> Спасибо, конечно, за пример :) DV> Hо, к сожалению, ты не указал: 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 Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/239273cd3ada6.html, оценка из 5, голосов 10
|