非連続無向グラフの単一の最短経路

Question

start（v）とend（u）を指定すると、与えられたエッジの集合を通る最短経路を見つけるグラフアルゴリズムはありますか？uが切断された頂点である場合、 uがもはや切断されなくなるまで、欠けているエッジを追加する最短パスを決定します。

私は、線が255（黒）と0（白）で作られているピクセルマトリックスを持っています。行（255）はブレークやスパーを持つことができ、私は両方を取り除かなければなりません。私は7ピクセル程度の黒いピクセルの木を持つピクセルマトリックスフォレストを持つことができます。私は各木の真の終点を見つけ、各木の単一の最短経路を見つけ、すべての斜行木を結合して1つの単一の線（すなわち、元の行列の最も遠い2つの終点からの単一の最短経路） 。すべての辺の重みはDijkstra's algorithm、外した場合の実行について、VとUを接続する方法1.

おかげ

Answer 1

考えることができますか？ 「欠けているエッジを追加するための最良の場所」の基準は何ですか？エッジにはウェイト（距離など）がありますか？

編集： の一つのアイデアについては、「最高の場所、」あなたはすべての接続されたペア間の最短経路の最小合計を持ってパスを試みることができます。 Floyd–Warshall algorithmを使用して、すべてのペア間の最短パスを見つけることができます。したがって、vのツリーとuの各ノードに対してFloyd-Warshallを実行します。

Answer 2

あなたの問題は、切断されたグラフでは明確に定義されていません。私は常にvとuの間に追加してエッジをつけることができます。

実際にフォレストとして知られ、サブグラフとしてエッジのサブセットが与えられている非周期的な無向グラフを指定すると、頂点間の最短経路を見つけることができますか？完全なグラフのパスには、1つのパスしかありません。

これは一般的なグラフGで、森林サブグラフG 'について話している場合は、より多くの情報が必要です。これは重み付けされていますか？それは正の重みですか？体重がない場合は、Dijkstaの変形をします。 2つの葉の間の最長の経路の長さになるように樹木の直径を定義します（これは、そのような唯一の経路であるため、樹形でよく定義されています）。 SをG '内のすべての木の直径の合計とし、G'からすべての辺の重みを2Sに設定すると、Dijkstraのアルゴリズムは自動的にG 'をステップし、G' G 'を通って歩くことは常に安くなるからです。