|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Iassenev 2:5020/400 22 May 2003 12:35:59
To : Alexey Zinoviev
Subject : Re: Алгоритм Дейкстры/нахожденя кратчайшего пути в графе.
--------------------------------------------------------------------------------
> Поделитесь плс, если у кого есть сабж(желательно реализованный на C/C++).
>
> PS: Можно и не Дейкстры...
Всё зависит от того, какой у вас граф. Если в графе есть циклы
отрицательного веса, то задача нахождения кратчайшего пути NP-полная, если
есть отрицательные веса, но нет циклов отрицательного веса, то нужно
применять не Дийкстру, а другой алгоритм (забыл имена авторов) или
преобразовать веса графа согласно алгоритму, изложенному у Седжвика и
применить Дийкстру, если же граф с неотрицательными весами, то есть смысл
использовать алгоритм Дийкстры, если же на графе задана Эвклидова метрика,
то можно попробовать алгоритм A*. Последний отличается от Дийкстры всего
одной строкой, поэтому поищите реализации A* в инете, их очень много
(по-английски он называется A-star).
Вот одна из ссылок :
http://theory.stanford.edu/~amitp/GameProgramming/path.cpp
Желаю удачи,
Дмитрий Ясенев.
P.S. Если Вам очень критична скорость, а среднее количество соседей у вершин
невелико и Вы ищите не очень длинные пути, то вместо куч Вы можете
использовать двухсвязные списки (некоторые используют сортированные списки).
P.P.S. А для какой задачи Вы будете использовать поиск кратчайшего пути?
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Алгоритм Дейкстры/нахожденя кратчайшего пути в графе. 