正の重みを持つエッジ、ノードのペア、およびノード間のパスを含むグラフが与えられた場合、グラフのエッジの重みを可能な限り最小限に変更して、指定されたパスがノード間の最短経路 (A* で計算)? (もちろん、最短パスを入力として指定した場合、出力は「変更なし」になります)。
注: 最小範囲とは、エッジの重みに加えられた変更の合計を指します。たとえば、他の極端な (最も破壊的な変更) は、指定されたパスに沿っていないすべてのエッジの重みを無限に変更し、パスに沿ったエッジの重みをゼロに変更することです。
Floyd-Warshall アルゴリズムを使用してすべてのパスの距離を計算し、目的のパスを変更して最短パスにすることができます。たとえば、次の 3 つのノードのグラフを想像してください。
パスを a -> b -> c とします。Floyd-Warshall アルゴリズムは、次の行列を計算します。
緑色の丸が付いた数字は、a -> b (2) および b -> c (4) の距離です。赤い丸で囲まれた数字は、a と c の間のパスの最短距離です (3)。2 + 4 = 6 ≠ 3 なので、パスを最小パスにするには 3 だけ調整する必要があることがわかります。
最短パスの距離を計算してそれに応じて目的のパスを調整するのではなく、このアプローチを提案する理由は、この方法では任意の 2 つのノード間の距離を確認できるため、必要に応じてエッジの重みを調整できるからです。 .