Главная страница


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
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Дейкстра   Arthur Martirosyan   14 Apr 2002 08:32:32 
 Дейкстра   Stanislav Shwartsman   19 Apr 2002 19:30:24 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 11:25:58 
 Дейкстра   Stanislav Shwartsman   20 Apr 2002 18:21:22 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 14:39:03 
 Дейкстра   Stanislav Shwartsman   21 Apr 2002 22:01:44 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 17:52:47 
 Re: Дейкстра   Andrew Bogatyrev   23 Apr 2002 02:45:51 
 Дейкстра   Stanislav Shwartsman   23 Apr 2002 17:17:56 
 Re: Дейкстра   Andrew Bogatyrev   24 Apr 2002 02:18:05 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 19:10:53 
 Дейкстра   Andrey Dashkovsky   20 Apr 2002 17:18:10 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 14:42:07 
 Re: Дейкстра   Vitaly Slobodskoy   20 Apr 2002 23:12:33 
 Дейкстра   Stanislav Shwartsman   22 Apr 2002 08:01:35 
 Re: Дейкстра   Vitaly Slobodskoy   23 Apr 2002 22:06:15 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 19:39:25 
 Re: Дейкстра   Vitaly Slobodskoy   26 Apr 2002 15:56:11 
 Дейкстра   Arthur Martirosyan   26 Apr 2002 10:20:02 
 Re: Дейкстра   Vitaly Slobodskoy   02 May 2002 21:43:52 
 Дейкстра   Arthur Martirosyan   01 May 2002 15:34:48 
 Re: Дейкстра   Vitaly Slobodskoy   03 May 2002 21:48:53 
 Дейкстра   Arthur Martirosyan   04 May 2002 09:46:14 
 Re: Дейкстра   Dmitry Volkov   03 May 2002 21:11:36 
 Дейкстра   Arthur Martirosyan   04 May 2002 09:36:53 
Архивное /ru.algorithms/239273cd3ada6.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional