|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Zinoviev 2:5020/1761 23 May 2003 08:41:52
To : Dmitriy Iassenev
Subject : Алгоритм Дейкстры/нахожденя кратчайшего пути в графе.
--------------------------------------------------------------------------------
22 May 03 12:35, Dmitriy Iassenev -> Alexey Zinoviev:
DI> Всё зависит от того, какой у вас граф.
Hеориентированный, отрицательных весов нет...
Исходные данные тоже любые, можно и матрицей и списком смежных вершин.
DI> то можно попробовать алгоритм A*. Последний отличается от Дийкстры всего
DI> одной строкой, поэтому поищите реализации A* в инете, их очень много
DI> (по-английски он называется A-star).
Thnx.
DI> Вот одна из ссылок :
DI> http://theory.stanford.edu/~amitp/GameProgramming/path.cpp
Посмотирим... Я вообще достаточно долго искал различные реализации, но ничего
толкового
не нашел :(
DI> P.S. Если Вам очень критична скорость, а среднее количество соседей у
DI> вершин невелико и Вы ищите не очень длинные пути, то вместо куч Вы
DI> можете использовать двухсвязные списки (некоторые используют сортированные
DI> списки).
Скорость совсем не критична.
DI> P.P.S. А для какой задачи Вы будете использовать поиск кратчайшего
DI> пути?
Пока что - курсовая работа в институте, я впервые столкнулся с реализацией
графов
и в связи с этим возникли вопросы.
With best regards,
Alexey.
[Гриб Сабжевик] [Fantasy] [Guitar]
--- GoldED/LNX 1.1.5 [Linux 2.4.18-4GB i686]
* Origin: Hастоящему индейцу завсегда, везде ништяк! (2:5020/1761)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
