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


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vitaly Slobodskoy                    2:5015/128.22  26 Apr 2002  15:56:11
 To : Arthur Martirosyan
 Subject : Re: Дейкстра
 -------------------------------------------------------------------------------- 
 
 До меня докатились слухи, что ты что-то там написал мне о "Дейкстра"! Так,
 так... надо бы разобраться...
 
  AM>>>>> Проблема такого характера: Hужно написать прогу по алгоритму
  AM>>>>> Дейкстра, реализовав его не для дерева, что, я понимаю, есть метод
  AM>>>>> оптимизации путей в сетях,.. а нужно реализовать поиск кратчайшего
  AM>>>>> пути из "А" (начального пункта) в "В" (конечный пункт).
 
  AM> Мне нужен именно Дейкстра из пункта в пункт, если у тебя есть нормально
  AM> работающий алгоритм, замыль в меня плиз..
 
  Так в чем проблема с Дейкстрой?? Есть у тебя, например, матрица расстояний от
 i-ого пункта в j-ый, если прямого пути нет, то это как-то выделяется, например,
 -1. К примеру, тебе надо узнать ВСЕ кратчайшие пути из пункта 1 во все
 остальные пункты. Строишь таблицу (реализуешь программно как захочешь):
      1:
 ----------
  2 |    |
  3 |    |
  . |    |
  . |    |
  . |    |
  n |    |
 -----------
 
  Вот, теперь во втором столбике указываешь из исходной матрицы расстояния из
 1-ого пункта в соответственно пункт, соответствуюший строке таблицы, например,
 так:
 
      1:
 ----------
  2 | 5  |
  3 | 2  |
  . | .  |
  . | .  |
  . | .  |
  n | 10 |
 -----------
 
  Теперь выбираешь минимум из полученных значений столбика (у нас это, к
 примеру, 2 в строке пункта 3), сохраняешь значение 2, например, в k, помечаешь
 эту ячейку звездочкой, зачеркиваешь строку 3-его пункта, начиная со всех
 следующих столбцов и делаешь новый столбец с заголовком 3:
 
      1:   3:
 ----------------
  2 | 5  |    |
  3 | 2* |----|----------
  . | 3  |    |
  . | 4  |    |
  . | 6  |    |
  n | 10 |    |
 ----------------
 
  Теперь заполняешь новый столбец по следующему принципу - значение ячейки i-ой
 строки будет равно min( расстояние из 3 пункта в пункт, соотв. i-ой строке + k
 ; значение ячейки предыдущего столбца). Есесно, если расстояние = -1, то оно
 как бы считается бесконечно большим и берешь альтернативу.
  Потом опять выбираешь min, вычеркиваешь новую строку, заполняешь оставшиеся
 столбцы. В итоге у тебя все расстояния из 1-ого пункта в i-ые помечены
 звездочками.
  Для того, чтобы определить путь, тебе нужно будет еще хранить маненькую
 историю. Все это очень легко программируется.
  Вот и весь алгоритм Дейкстры.
 
 Может свидимся ..
                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/390865f54705.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional