Математика : Графы: Кратчайшие пути

Пусть имеется n городов, пронумерованных числами от 1 до n. Для каждой пары городов с номерами i, j в таблице a[i][j] хранится целое число - цена прямого авиабилета из города i в город j. Считается, что рейсы существуют между любыми городами, a[i,i] = 0 при всех i, a[i][j] может отличаться от a[j,i]. Наименьшей стоимостью проезда из i в j считается минимально возможная сумма цен билетов для маршрутов (в том числе с пересадками), ведущих из i в j. (Она не превосходит a[i][j], но может быть меньше.)

Предположим, что не существует замкнутых маршрутов, для которых сумма цен отрицательна. В этом случае маршрут с наименьшей стоимостью существует.

Во всех алгоритмах предполагается, что это условие (отсутствие циклов с отрицательной суммой) выполнено.

Архив статей.

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

Вверх по странице, к оглавлению и навигации