|
|
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) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/390865f54705.html, оценка из 5, голосов 10
|