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