Re: Дейкстра

From

Dmitry Volkov (2:5015/185.5)

To

Arthur Martirosyan

Date

2002-05-03T21:11:36Z

Area

RU.ALGORITHMS

Привет, многоуважаеый Arthur, 

Правильно ли помню я, что 26.04.02 9:20:02 
разговаривал ты с Vitaly Slobodskoy про "Дейкстра"?

 AM>>>>>>> Проблема такого характера: Нужно написать прогу по алгоритму
 AM>>>>>>> Дейкстра, реализовав его не для дерева, что, я понимаю, есть метод
 AM>>>>>>> оптимизации путей в сетях,.. а нужно реализовать поиск кратчайшего
 AM>>>>>>> пути из "А" (начального пункта) в "В" (конечный пункт).

Итак, во-первых, НЕ существует алгоритма, который ищет кратчайший путь
только между заданными вершинами. Есть на выбор два алгоритма:

 - алгоритм Флойда, который ищет кратчайший путь между ВСЕМИ парами вершин.
Его сложность O(n^3).
   Область применения: ориентированный граф без ЦИКЛОВ с отрицательным весом.

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

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

[прослушал...]
 VS>> Так в чем проблема с Дейкстрой?? Есть у тебя, например, матрица
 VS>> расстояний от i-ого пункта в j-ый, если прямого пути нет, то это как-то
 VS>> выделяется, например, -1. К примеру, тебе надо узнать ВСЕ кратчайшие
 VS>> пути из пункта 1 во все остальные пункты. Строишь таблицу (реализуешь
 VS>> программно как захочешь):
[прослушал...]
  Как примечание: собственно, эта матрица - матрица кратчайших расстояний
от начального пункта(в нашем случае - пункта 1) до всех остальных. Очевидно,
что Mas[1] = 0 и еще:

 VS>> Вот, теперь во втором столбике указываешь из исходной матрицы
 VS>> расстояния из 1-ого пункта в соответственно пункт, соответствуюший
 VS>> строке таблицы, например, так:
[прослушал...]

 VS>> путь, тебе нужно будет еще хранить маненькую историю. Все это очень
 VS>> легко программируется. Вот и весь алгоритм Дейкстры.
[прослушал...]
 AM> кратчайшего пути этот алгоритм (тобой приведенный) не дает.. в моей
 AM> задаче это получился даже не второй и не третий по величине путь.. Так
 AM> вот вопрос в том, работает ли вообще алгоритм Дейкстры для нахождения
 AM> кратчайшего пути в неориентированном графе? У меня выбор кратчайшего
 AM> пути
 AM> получается простым перебором всех вариантов.. Кстати. вот моя задача:
 AM> для
 AM> понимания проще нарисовать неориентированный граф, я же привожу
 AM> матрицу..
[прослушал...]

 AM> Это простой пример, который я просто еру за основу.. Опять же,
 AM> встречаются и вообще тупиковые ситуации, когда придется двигаться
 AM> обратно..

Спасибо, конечно, за пример :)
Но, к сожалению, ты не указал:
- начальный пункт (как я понимаю, ты имеешь в виду - пункт 1)
- то, что у тебя выдавала РЕАЛИЗАЦИЯ алгоритма
- и то, что выдавал полный перебор
Я хотя тебе, конечно, верю, но Дейкстре как-то больше верится:))

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

 На каждом шаге мы выбераем пункт L, куда мы еще не "ходили" и куда мы можем
попасть за минимальное (из оставшихся пунктов) "время" и пытаемся из него с
помощью "его" ребер сминимизировать "время" до оставшихся пунктов.
 Очевидно, "время" до тех пунктов, которые уже просмотрены, "сминимизить"
нельзя (действительно, для всех I (где I - пункт, который уже промотрен) Mas[I]
< Mas[L] + NewPut[I, L], т.к. Mas[I] < Mas[L] - по алгоритму, а все дуги имеют
неотрицательный вес )
 Далее, предположим для выбранной вершины "время" не минимально. Тогда
существует путь с суммарным весом меньше, чем mas[I]. Обозначим за J
-предпоследний пункт в этом пути. Получили, что:
        Mas[I] > Mas[J] + Duga[I, J].
 Очевидно, получили противоречие.

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

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

ЗЫ3: В доказательстве мог наглючить(в чем (не)сильно сомневаюсь), но уж
Дейкстра-то точно не глючит:)
 
 Ветра в спину, Arthur,
 Не забывай в своих прогах о
               2mi3 (DiMiTry Volkov)


--- WP/95 Rel 1.78E (215.0) Reg.
 * Origin: Ибо Митин. (с) Теория сусликов (2:5015/185.5)