algorithm - 頂点とエッジの両方のコストを使用する最短経路アルゴリズム

Question

これは一般的なアルゴリズムの質問です。エッジと頂点の両方にコストが関連付けられている無向グラフで最短経路アルゴリズムを実行したいと思います。最短経路探索アルゴリズムのほとんどは、頂点コストを考慮していません。この問題を補う方法はありますか？

Answer 1

エッジが接続する 2 つの頂点のコストの半分をエッジのコストに追加することによって、グラフを拡張します (それをエッジの拡張コストと呼びます)。

次に、頂点コストを無視して、拡張グラフで通常の最短経路アルゴリズムを実行します。

パスごとに

v_0 -e_1-> v_1 -e_2-> v_2 -e_2-> ... -e_n-> v_n

拡張グラフのコストは

(1/2*C(v_0) + C(e_1) + 1/2*C(v_1)) + (1/2*C(v_1) + C(e_2) + 1/2*C(v_2)) + ... + (1/2*C(v_(n-1)) + C(e_n) + 1/2*C(v_n))
= C(v_0) + C(e_1) + C(v_1) + C(e_2) + ... + C(e_n) + C(v_n) - 1/2*(C(v_0 + C(v_n))

したがって、2 つの頂点間のパスaとb拡張グラフ内のパスのコストは、元のグラフ内の同じパスのコストから開始頂点と終了頂点の合計コストの半分を引いたものになります。

したがって、そのパスが拡張グラフで最短パスである場合に限り、そのパスは元のグラフでの最短パスになります。