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


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vitaly Slobodskoy                    2:5015/128.22  02 May 2002  21:43:52
 To : Arthur Martirosyan
 Subject : Re: Дейкстра
 -------------------------------------------------------------------------------- 
 
 До меня докатились слухи, что ты что-то там написал о "Дейкстра"! Так, так...
 надо бы разобраться...
 
  AM>>>>>>> Проблема такого характера: Hужно написать прогу по алгоритму
  AM>>>>>>> Дейкстра, реализовав его не для дерева, что, я понимаю, есть метод
  AM>>>>>>> оптимизации путей в сетях,.. а нужно реализовать поиск кратчайшего
  AM>>>>>>> пути из "А" (начального пункта) в "В" (конечный пункт).
 
  AM> Да. то, что ты написал довольно легко программируется.. Вопрос в том, что
  AM> кратчайшего пути этот алгоритм (тобой приведенный) не дает.. 
 
  Да ладно!!! Мною привиденный алгоритм и есть алгоритм Дейкстры и ОH всегда
 дает кратчайший путь (точнее, его величину)!
 
  AM> в моей
  AM> задаче это получился даже не второй и не третий по величине путь.. 
 
  Интересно, как ты считал...
 
  AM> Так
  AM> вот вопрос в том, работает ли вообще алгоритм Дейкстры для нахождения
  AM> кратчайшего пути в неориентированном графе? 
 
  Конечно, по сути, неориентированный граф - это частный случай
 ориентированного, только матрица для него симметричная.
 
  AM> У меня выбор кратчайшего пути
  AM> получается простым перебором всех вариантов.. 
 
  Стремно...
 
  AM> Кстати. вот моя задача: для
  AM> понимания проще нарисовать неориентированный граф, я же привожу матрицу..
 
  AM>  |   1   2   3   4   5   6   7 
  AM> -|----------------------------- 
  AM> 1|  oo   2   5   4  oo  oo  oo  | 
  AM> 2|   2  oo   2  oo   7  oo  oo  | 
  AM> 3|   5   2  oo   1   4   3  oo  | 
  AM> 4|   4  oo   1  oo  oo   4  oo  | 
  AM> 5|  oo   7   4  oo  oo   5   5  | 
  AM> 6|  oo  oo   3   4   5  oo   7  | 
  AM> 7|  oo  oo  oo  oo   5   7  oo  |
 
  AM> Это простой пример, который я просто еру за основу.. Опять же,
  AM> встречаются и вообще тупиковые ситуации, когда придется двигаться
  AM> обратно..
 
 Пож-ста, вот решение этой задачи тем алгоритмом, который я приводил:
 
       1  |  2      |  3       |  4        |  6          |
 ---------------------------------------------------------------------
  2 |  2* |-----------------------------------------------------------
  3 |  5  | 4(1-2)* |-------------------------------------------------
  4 |  4  | 4(1)    | 4(1)*    |--------------------------------------
  5 | oo  | 9(1-2)  | 8(1-2-3) | 8(1-2-3)  | 8(1-2-3)*   |------------
  6 | oo  | oo      | 7(1-2-3) | 7(1-2-3)* |--------------------------
  7 | oo  | oo      | oo       | oo        | 14(1-2-3-6) | 13(1-2-3-5)
 
  В скобках указана история. В принципе, это не предусматривается алгоритмом,
 т.к. его задача - это - минимальное расстояние, но, согласись, хранить ее не
 сложно.
  Итак, мы имеем такие кратчайшие пути из пункта 1 во все остальные:
 в пункт 2: 1->2 (длина 2)
 в пункт 3: 1->2->3 (длина 4)
 в пункт 4: 1->4 (длина 4)
 в пункт 5: 1->2->3->5 (длина 8)
 в пункт 6: 1->2->3->6 (длина 7)
 в пункт 7: 1->2->3->5->7 (длина 13)
 
  Вот, как бы и все! Так в чем проблема???
 Пока, 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)
 
 

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

 Тема:    Автор:    Дата:  
 Дейкстра   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/39086b657481.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional