DijkstraのシングルソースShourtest Path 'w'の余分なエッジ付き

Question

最近のインタビューでは、わずかな修正を加えた単一ソースの最短経路アルゴリズム（無向グラフと正の重み付きグラフ）を実装するように求められました。ウェイト「w」のエッジ。 SSSPアルゴリズムによって計算されたパスよりも短いパスが見つかったら、すでに接続されていない2つのノード間にウェイトwで余分なエッジを接続します。 Here's an image. As according to SSSP the shortest path between A(source) & D(destination)is A-B-C-D i.e. total of 8.

しかし余分なエッジがある。これは、まだ接続されていないAとDの間で接続することができ、SSSPアルゴリズムを通じて得られる最短経路を最小限に抑えることができます。 Image of graph with extra edge contributing the shortest path

解決策を考えました。しかし、これまでに何も打たなかった。私は最短経路を見つけるためにDijkstraアルゴリズムを実装しました。しかし、この小さな変更は私を困惑させました。だから少し助けてくれますか？

Answer 1

2つのオプションがあります。

1. 私たちは余分なエッジを必要としませんが。このケースは、標準のダイクストラアルゴリズムによって処理されます。

2. 余分なエッジを持つ最短パスは、次のようになります。shortest_path(start, V) + (V, U) + shortest_path(U, target)。つまり、最初からいくつかの頂点Vまで、元のグラフの最短パスで行ってから、この余分なエッジ（VとUは接続しないでください）を追加してU（やはり任意の頂点）に行き、 Uから元のグラフの最短経路でターゲットノードに行きます。

3. O(n^2)解決策を得るためにパスの構造を使用することができます。開始ノードから他のすべてのノード（Dijkstraのアルゴリズムの1つ）と最短パスを計算できます他のノード（1回以上実行）。これですべての可能なペア(V, U)を繰り返して、最良のものを選ぶことができます。

4. ボーナス：で疎なグラフを解決できます。すべての(U, V)のペアをチェックするのではなく、Vに接続されていないすべての頂点のうちターゲットまでの最小距離がdegree(V) * log V（または直線的）であるようなUを見つけることができます（この問題は、セット内にない最小の要素を見つける）。

Answer 2

私はあなたの質問にお答えできません。あなたは重み付けされたグラフを持ち、wでエッジを追加することができ、最短パスを作る場所を追加できます。 私はspfa + dpを使って問題を解決できると思います。他のすべてのエッジをwに設定し、ブール値行列mを作成する。m [i、j] = 1は、i、j、dp [u、0]の間にエッジがないことを意味する。 、1]余分なエッジを使用することを意味します。私はdp転送方程式を書いていません。だから私たちはspfaで反復することができます。また、dpの最善の方法をバックトラックして余分なエッジを設定する場所を取得することもできます。

上記ソリューションではダイクストラアルゴリズムを使用していません。

spfaもシングルソースのShourtest Pathアルゴリズムであり、負の加重エッジを処理できますが、負のサイクルは処理できません。

私はそれを試していないと思っています。しかし、それを解決することが考えられます。 間違っている場合は、教えてください。