c # — Существует ли реализация с открытым исходным кодом алгоритма кратчайшего пути с разметкой расстояний, как Гавойл и др.?
Если вам разрешено предварительно вычислить линейный в |V| количество данных на графе, то есть семейство алгоритмов, которые имеют сублинейные времена запроса для кратчайших путей в графе.
- Гавойл и соавт. Маркировка расстояний на графиках.
- Cohen et al. Достижимость и дистанционные запросы с помощью двухэтапных меток
- Abraham, Goldberg et al. Иерархические обозначения узлов для кратчайших путей
Некоторые из них используются в Карты 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) «Союз» L_r(t) содержит хотя бы одну вершину на кратчайшем пути из s в t.
Существует ли реализация с открытым исходным кодом одного из этих алгоритмов (C ++, C #, F #, D, Go, Java)?
Решение
Я не нашел ни одного кода, который реализует эти алгоритмы, но вы можете посмотреть на домашняя страница Карлсруэ где вы можете найти код для иерархий сокращения, которые составляют основу (оригинальной) маркировки концентратора. Вы можете использовать это для создания своей собственной реализации HL, но вы должны знать, что они подали патент для этого.
Другие решения
Других решений пока нет …