Einfacher kürzester Pfad eines azyklischen ungerichteten getrennten Graphen

Question

Gibt es einen Graphenalgorithmus, der bei einem Start (v) und einem Ende (u) den kürzesten Pfad durch die gegebene Menge von Kanten findet, aber wenn u ein nicht verbundener Knoten ist, Er bestimmt auch den kürzesten Pfad zum Hinzufügen fehlender Kanten, bis du nicht mehr getrennt bist.

Ich habe eine Pixelmatrix, wo Linien aus 255 (schwarz) und 0 (weiß) gemacht werden. Linien (255) können Pausen oder Sporen haben und ich muss beide loswerden. Ich könnte eine Pixelmatrix-Gesamtstruktur mit sagen wir 7 Bäumen von schwarzen Pixeln haben. Ich muss die wahren Endpunkte jedes Baumes finden, den kürzesten Weg jedes Baumes finden, dann alle Bäume zusammenführen, um eine einzelne Linie zu bilden (dh einen einzigen kürzesten Weg von den letzten 2 Endpunkten in der ursprünglichen Matrix) . alle Kantengewichte 1.

Dank

Answer 1

Wie wäre es Dijkstra's algorithm läuft in Betracht gezogen werden könnte und wenn getrennt, verbinden v und u? Was ist Ihr Kriterium für "den besten Ort, um eine fehlende Kante hinzuzufügen?" Haben Kanten Gewichte (wie Entfernung)?

bearbeiten: Für eine Idee von „der beste Ort“, der Pfad versuchen könnte, die minimale Summe der kürzesten Wege zwischen allen angeschlossenen Kabelpaaren hat. Floyd–Warshall algorithm kann verwendet werden, um kürzeste Wege zwischen allen Paaren zu finden. Führen Sie also Floyd-Warshall für jeden Knoten in vs Baum und u.

Answer 2

Ihr Problem ist für nicht verbundene Graphen nicht gut definiert. Ich kann immer zwischen v und u hinzufügen und kanten.

Wenn Sie gemeint haben, dass ein azyklischer ungerichteter getrennter Graph, eigentlich bekannt als Wald, und eine Untermenge von Kanten als Untergraphen gegeben ist, können Sie den kürzesten Weg zwischen Scheitelpunkten finden, dann ist dieses Problem trivial Pfad im gesamten Graph gibt es nur einen Pfad.

Wenn dies ein allgemeiner Graph G ist, und Sie sprechen über einen Wald-Teilgraphen G ', dann brauchen wir mehr Informationen. Ist das gewichtet? Sind es nur positive Gewichte? Wenn es nicht gewichtet ist, machen Sie eine Variante von Dijksta. Definieren Sie den Durchmesser eines Baumes als die Länge des längsten Pfades zwischen zwei Blättern (dies ist in einem Baum gut definiert, da es nur einen solchen Pfad gibt). Sei S die Summe der Durchmesser aller Bäume in G ', dann setze das Gewicht alle Kanten von G' auf 2S, dann wird Dijkstras Algorithmus automatisch vorziehen, durch G 'zu gehen und nur dann außerhalb von G' zu gehen, wenn es keine gibt Wahl, da G 'immer billiger wäre.