Если вам разрешено предварительно вычислять линейное по |V| количеству данных на графе, то существует семейство алгоритмов, которые имеют сублинейное время запроса для кратчайших путей на графе.
- Гавойль и др. Разметка расстояний на графиках.
- Коэн и др. Запросы достижимости и расстояния с помощью меток с двумя переходами
- Абрахам, Голдберг и др. Иерархическая маркировка концентраторов для кратчайших путей
Некоторые из них используются в Карты Bing для очень быстрого расчета кратчайших маршрутов.
Основная идея состоит в том, чтобы предварительно вычислить для каждой вершины прямые метки L_f(v) и обратные метки L_b(v), которые создают свойство покрытия. Каждая метка представляет собой пару вершины и расстояния до нее, например. L_f(v) = { (u, dist(v, u)) } и L_r(v) = { (u, dist(u, v)) }. А свойство покрытия утверждает, что для любых вершин s и t L_f(s) 'Union' L_r(t) содержит по крайней мере одну вершину на кратчайшем пути из s в t.
Существует ли реализация одного из этих алгоритмов с открытым исходным кодом (C++, C#, F#, D, Go, Java)?
