algorithm - 全ペア最短経路アルゴリズムを無向対称グラフに最適化するにはどうすればよいですか?

Question

全ペア最短経路アルゴリズムを無向対称グラフに最適化するにはどうすればよいですか?

別の質問を誤解した結果、この質問に出くわしました。誰かが興味を持っているのではないかと思いました。

All-Pairs Shortest Paths はおそらくもっと興味深い質問ですが、Single-Source Shortest Path に重要な最適化が見られる場合は、気軽に言及してください。

特に対称グラフに焦点を当てていない限り、最短経路アルゴリズムの比較を探しているわけではありません。

Answer 1

うまく説明するために、蝶の比喩を使用します (翼が左右対称であると仮定します)。

共通の頂点: 対称線を構成するすべての頂点 (つまり、蝶の胴体)。

アルゴリズム：

• 対称辺の 1 つ (およびそれらに接続されたエッジ) にあるすべての頂点をグラフから削除します。

  蝶の羽の 1 つを削除します。

• この新しいグラフで任意の最短経路アルゴリズムを実行します

• これで、すべての共通頂点から他のすべての頂点への/からの最短経路が得られました (グラフは無向であり、削除されたすべての頂点はこの新しいグラフで対称頂点を持ち、共通頂点までの距離が同じであるため)

  これで、蝶の体から、または翼の任意の点までの最短経路が得られました。これは、蝶の胴体のある点から翼のある点までの距離が、胴体のその点から他の翼の同じ点までの距離と同じであり、逆の距離でもあるためです。これらのいずれかのパス。

• ここで、各非共通頂点a、各非共通頂点b、および各共通頂点について、 からまでcの距離を記録します(から までの距離とからまでの距離が既にあるため、一定時間演算 (加算のみ) )。 からの対称頂点(または の対称頂点)までの最小距離は、すべての共通頂点間での最小距離になります。acbaccb
abab

  一方の翼の任意の点からもう一方の翼の任意の点までの最短経路を決定するために、最初の点から本体の各点まで、および本体の各点から 2 番目の点までのすべての経路をチェックし、そのような最小のものを見つけます。距離。