graph - 1つのコストを無視して最も安いパスを見つける

Question

2つの頂点の間で最も安いパスを見つけたいので、無料で移動できるパスを1つ選択できます。例：

頂点1と6の間の最も安いパスは1-3-4-5-6です-私は無料でエッジ1-3（コスト30）に行き、それは私に合計コスト21を与えます。

すべてのパスを1つずつチェックする以外の方法はありますか？

Answer 1

これを行う1つの方法は、次のことを行うことです。

1. グラフを複製して、ノード1、2などを含む元のグラフGを作成します。ノード1'、2'などのコピーG'。および対応するエッジ。
2. Gの各エッジ（a、b）について、aからb'へのアーク（方向付けられた！）とbからa'へのアーク（両方ともコスト0）を作成します。
3. 最後に、サブグラフGの任意の頂点からG'の任意の頂点（この例では1から6'）への最短経路アルゴリズムを使用します。

基本的には、ジョーカーを使用するときにサブグラフGからG'に切り替えます。

そこから任意の数のジョーカーエッジに一般化するために、余分なコピーを追加し、それぞれの新しいコピーを最後にリンクします。ただし、その場合、最短パスに必要なエッジがジョーカーよりも少ない場合を考慮して、より少ないジョーカーを使用してターゲットを追加する必要があります。