Floyd-Warshall アルゴリズムでは、頂点の任意のペアについて最短パス コストが計算されます。追加の簿記により、実際のパス (頂点のリスト) を最短パスに保つことができます。
Floyd-Warshall を拡張して、任意の頂点のペアについて、上位 K の最短経路が見つかるようにするにはどうすればよいですか? たとえば、K=3 の場合、3 つの最短経路が計算されて維持されるという結果になりますか?
私はSedgewickのJava 実装を使用しています。
1059 次
2 に答える
2
N 個の最短パスを返すように Dijkstra を簡単に変更できるように思えます。K 個の最短代替案が頂点に入るまで、探索は頂点に入ることができます。
詳細については、ウィキペディアの記事を確認してください
于 2014-08-23T23:58:34.640 に答える