K shortest path routing とは

k最短経路ルーティングアルゴリズムは、所与のネットワークにおける最短経路ルーティングアルゴリズムの拡張アルゴリズムである。
特定のネットワーク内の2つのノード間に複数のパスを設定することが重要な場合があります。追加の制約がある場合、最短経路とは異なる他の経路を計算することができる。最短経路を見つけるには、DijkstraのアルゴリズムやBellman Fordアルゴリズムなどの最短経路アルゴリズムを使用し、それらを拡張して複数の経路を見つけることができます。 k最短経路ルーティングアルゴリズムは、最短経路問題の一般化である。このアルゴリズムは、最短経路だけでなく、コストの降順でk-1個の他の経路も見つける。 kは見つけるべき最短経路の数である。この問題は、ループのない最短パスk(ループなしk最短パス)またはループを持つように制限することができます。