Дейкстра
- From
- Arthur Martirosyan (2:5061/103.51)
- To
- Vitaly Slobodskoy
- Date
- 2002-04-26T10:20:02Z
- Area
- RU.ALGORITHMS
Hello, Vitaly !
Пятница Апрель 26 2002 15:56 You wrote:
AM>>>>>> Проблема такого характера: Нужно написать прогу по алгоритму
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