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