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


ru.algorithms

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