|  |
| Волновой алгоритм
Прекрасно подойдет, если все пути из вершины в соседнюю равны по длине (цене, весу) Время O(n).
|
| Алгоритм Форда-Беллмана
Найти наименьшие стоимости проезда из 1-го города во все остальные за время O(n3) без ограничений на веса.
|
| Алгоритм Флойда
Найти наименьшие стоимости проезда из всех городов во все за время O(n3) без ограничений на веса.
|
| Алгоритм Дейкстры
Найти наименьшие стоимости проезда из 1-го города во все остальные за время O(n2) при положительных ценах.
|
| Нахождение k кратчайших путей в графе
Находить один путь мы уже умеем. Что, если у нас большой граф,а нам нужно k различных кратчайших путей ? Алгоритм Йена придет на помощь!.
|
| Smart Moves: Intelligent Pathfinding[Перевод]
Большая часть статьи посвящена различным случаям поиска кратчайшего пути на графе применительно к играм. Рассмотрено более 5 алгоритмов. Даны заметки к реализации.
|
