Re: Дейкстра
- From
- Vitaly Slobodskoy (2:5015/128.22)
- To
- Arthur Martirosyan
- Date
- 2002-05-02T21:43:52Z
- Area
- RU.ALGORITHMS
Привет, Arthur!
До меня докатились слухи, что ты что-то там написал о "Дейкстра"! Так, так...
надо бы разобраться...
AM>>>>>>> Проблема такого характера: Нужно написать прогу по алгоритму
AM>>>>>>> Дейкстра, реализовав его не для дерева, что, я понимаю, есть метод
AM>>>>>>> оптимизации путей в сетях,.. а нужно реализовать поиск кратчайшего
AM>>>>>>> пути из "А" (начального пункта) в "В" (конечный пункт).
AM> Да. то, что ты написал довольно легко программируется.. Вопрос в том, что
AM> кратчайшего пути этот алгоритм (тобой приведенный) не дает..
Да ладно!!! Мною привиденный алгоритм и есть алгоритм Дейкстры и ОН всегда
дает кратчайший путь (точнее, его величину)!
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)