k最短経路ルーティング

このバリアントでは、パスがループなしである必要がないため、問題が単純化されます。^{[ 4 ]} 1975 年に BL Fox によって、k最短パスがO ( m + kn log n )の漸近時間計算量(ビッグO表記を使用) で決定されるという解決策が提示されました。^{[ 5 ]} 1998 年にDavid Eppstein は、パスの暗黙的表現を計算することで漸近的複雑度O ( m + n log n + k ) を維持するアプローチを報告しました。各パスは、O ( n ) の追加時間で出力できます。^{[ 2 ] [ 4 ]} 2015 年に Akibaらは、 Eppstein のアルゴリズムの大幅に高速な代替手段としてインデックス法を考案しました。この方法では、インデックスと呼ばれるデータ構造がグラフから構築され、任意の頂点ペア間のトップk距離を迅速に取得できます。 ^{[ 6 ]}

ループなしのバリアントでは、パスにループを含めることは禁止されており、複雑さがさらに増します。^{[ 4 ]}これは、 nノードの非負距離ネットワーク内の固定ノードから他のすべてのノードへのすべての最短パスの長さを見つけるYen のアルゴリズム^{[ 3 ] [ 4 ]}を使用して解決できます。この手法では、2 n ²回の加算とn ^{2 回の}比較のみが必要で、他の利用可能な最短パス アルゴリズムよりも少なくなっています。実行時間の複雑さは擬似多項式で、O ( kn ( m + n log n ))です(ここで、mとn はそれぞれエッジと頂点の数を表します)。^{[ 3 ] [ 4 ]} 2007年に、John HershbergerとSubhash Suriは、Lawler ^{[ 7 ]}とYenのアルゴリズムのより効率的な実装である置換パスアルゴリズムを提案した。これは、多数のグラフに対してO ( n )の時間改善をもたらすが、すべてのグラフに対してではない（したがって、Yenのアルゴリズムの漸近的境界は変更されない）。^{[ 8 ]}

以下の例では、Yenのモデルを使用して、通信エンドノード間のk個の最短経路を見つけます。つまり、最短経路、2番目に短い経路など、K^{番目に短い経路を見つけます。詳細は}こちらをご覧ください。この例で提供されているコードは、単方向リンクと双方向リンクが混在する15ノードネットワークのk最短経路ルーティング問題を解決しようとします。

別の例として、 k最短経路アルゴリズムを用いて複数の物体を追跡する方法があります。この手法は、 k最短経路ルーティングアルゴリズムに基づいた複数物体トラッカーを実装します。入力として、確率的占有マップのセットが使用されます。入力は物体検出器によって提供されます。

詳細については、「コンピュータビジョン研究所– CVLAB」をご覧ください。

k最短経路アルゴリズムのもう1つの用途は、公共交通機関における乗客の体験を向上させる交通ネットワークの設計です。このような交通ネットワークの例は、移動時間を考慮することで構築できます。移動時間に加えて、経済的および地理的な制約に応じて他の条件も考慮される場合があります。パラメータの変動にもかかわらず、k最短経路アルゴリズムは、ほぼすべてのユーザーのニーズを満たす最適なソリューションを見つけます。このようなk最短経路アルゴリズムの応用は一般的になりつつあり、最近ではXu、He、Song、およびChaudhry（2012）が交通ネットワークシステムにおけるk最短経路問題を研究しました。^{[ 9 ]}