:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Графы и маршруты » Кратчайшие пути
На правах рекламы
Нужно купить лабораторные весы измерительные - заходите.
  Задача о кратчайших путях




Волновой алгоритм
Прекрасно подойдет, если все пути из вершины в соседнюю равны по длине (цене, весу) Время O(n).

Алгоритм Форда-Беллмана
Найти наименьшие стоимости проезда из 1-го города во все остальные за время O(n3) без ограничений на веса.

Алгоритм Флойда
Найти наименьшие стоимости проезда из всех городов во все за время O(n3) без ограничений на веса.

Алгоритм Дейкстры
Найти наименьшие стоимости проезда из 1-го города во все остальные за время O(n2) при положительных ценах.

Нахождение k кратчайших путей в графе
Находить один путь мы уже умеем. Что, если у нас большой граф,а нам нужно k различных кратчайших путей ? Алгоритм Йена придет на помощь!.

Smart Moves: Intelligent Pathfinding[Перевод]
Большая часть статьи посвящена различным случаям поиска кратчайшего пути на графе применительно к играм. Рассмотрено более 5 алгоритмов. Даны заметки к реализации.