Дейкстра
- From
- Arthur Martirosyan (2:5061/103.51)
- To
- Vitaly Slobodskoy
- Date
- 2002-05-01T15:34:48Z
- Area
- RU.ALGORITHMS
Hello, Vitaly !
Четверг Май 02 2002 21:43 You wrote:
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>> обратно..
VS> Пож-ста, вот решение этой задачи тем алгоритмом, который я приводил:
VS> 1 | 2 | 3 | 4 | 6 |
VS> -+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
VS> 2 | 2* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+---
VS> 3 | 5 | 4(1-2)* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
VS> 4 | 4 | 4(1) | 4(1)* |-+--+--+--+--+--+--+--+--+--+--+--+---
VS> 5 | oo | 9(1-2) | 8(1-2-3) | 8(1-2-3) | 8(1-2-3)* |-+--+--+--+-
VS> 6 | oo | oo | 7(1-2-3) | 7(1-2-3)* |-+--+--+--+--+--+--+--+---
VS> 7 | oo | oo | oo | oo | 14(1-2-3-6) | 13(1-2-3-5)
VS> В скобках указана история. В принципе, это не предусматривается
VS> алгоритмом, т.к. его задача - это - минимальное расстояние, но,
VS> согласись, хранить ее не сложно. Итак, мы имеем такие кратчайшие пути
VS> из пункта 1 во все остальные: в пункт 2: 1->2 (длина 2) в пункт 3:
1->2->> 3 (длина 4) в пункт 4: 1->4 (длина 4) в пункт 5: 1->2->3->5
VS> (длина 8) в пункт 6: 1->2->3->6 (длина 7) в пункт 7: 1->2->3->5->7
VS> (длина 13)
VS> Вот, как бы и все! Так в чем проблема???
ОК! походу я немного прогнал, вернее делал не так.. все же пара вопросов осталась, а именно: почему у нас сразу отпадает 4-я вершина, путь дальше через нее не рассматривается, тогда, как 5-ю вершину мы рассматриваем до конца и получаем таки через нее кратчайший путь, чем это определяется? по логике все понятно, но как это обьяснять машине..
... OK!____________________________________________________________________
--- Желаю удачи и всего хорошего, Arthur M. -------------------------------
* Origin: A dream comes true (2:5061/103.51