6

グラフ上のデータ量を線形に事前計算することが許可されている場合|V|、グラフ内の最短パスに対して準線形のクエリ時間を持つ一連のアルゴリズムがあります。

  1. ガヴォイユ等。グラフでの距離のラベル付け。
  2. コーエン等。2 ホップ ラベルによる到達可能性と距離のクエリ
  3. エイブラハム、ゴールドバーグ 他 最短経路の階層ハブ ラベル付け

それらのいくつかは、Bing Mapsで使用され、最短ルートを非常に高速に計算します。

基本的な考え方は、各頂点の前方ラベルL_f(v)と後方ラベルを事前計算しL_b(v)て、カバー プロパティを設定することです。各ラベルは、頂点とそれまでの距離のペアです (例:L_f(v) = { (u, dist(v, u)) }と ) L_r(v) = { (u, dist(u, v)) }。また、cover プロパティは、任意の頂点 s および t について、L_f(s)'Union'L_r(t)が s から t への最短経路上に少なくとも 1 つの頂点を含むことを表明します。

これらのアルゴリズム (C++、C#、F#、D、Go、Java) のいずれかのオープン ソース実装はありますか?

4

1 に答える 1

3

これらのアルゴリズムを実装するコードは見つかりませんでしたが、(元の) ハブ ラベル付けの基礎を形成する収縮階層のコードを見つけることができるKarlsruhe のホームページを参照してください。それを使用して HL の独自の実装を作成することもできますが、HL が特許を申請していることを知っておく必要があります。

于 2012-10-30T07:52:13.263 に答える