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