有向グラフ G=(V,E) と重み関数 w : E - > R+ (グラフ内のエッジの正の重みのみ) が与えられた場合、V のすべての頂点 v から特定の頂点までの最短経路をすべて見つける必要があります。 k.
グラフのエッジを逆にして、頂点 k からダイクストラのアルゴリズムを実行することを考えました。k から v1 への最短経路 p は、元のグラフ (エッジを反転する前) の v1 から k への最短経路であるかどうか疑問に思います。
誰かがそれが起こる/起こらないかどうか、そしてその理由を説明できれば幸いです.
前もって感謝します。
(これは世界で最も正式な証拠ではありませんが、自分自身を納得させるには十分であることを願っています)。
グラフGの頂点vについて、 vからkへの最短経路の長さはmであるとしましょう。知りたい 2 つのことは次のとおりです。 1. 逆グラフ G* には、 kからvまで
の長さmのパスがあります。2. 逆グラフ G* では、 mより短いkからvへ
のパスはありません。
始める前に、信仰について 1 つ考えてもらえますか?
補題 1 : 頂点vから頂点wへの有向パスがあり、そのパスのすべてのエッジを反転させると、頂点 w から頂点 v へのパスが得られます。これは証明可能ですが、かなり常識的だと思います。あなたが望むなら、私はそれを証明します。
ポイント 1 について: m 個のエッジから構成されるvからkまでのGのパスを考えます。これらのエッジのそれぞれを逆にすると、kからvまでの長さmのパスが得られます(補題 1による)。
ポイント 2 について: 逆グラフ G* にkからvまでの長さn < mのパスが存在するとします。このパスを逆にすると、vからkまでの長さnのパスが存在します( Lemma 1 )。これは、m より短い元のグラフの v から k へのパスが存在することを意味し、長さmのパスが最短であるというステートメントと矛盾します。