Single shortest path of an acyclic undirected disconnected graph

Question

Hi,

Is there a graph algorithm that given a start(v) and an end(u) will find a shortest path through the given set of edges, but if u is a disconnected vertex, it will also determine the shortest path to add missing edges until u is no longer disconnected?

I have a pixel matrix where lines are made of 255's(black) and 0's(white). lines(255) can have breaks or spurs and I must get rid of both. I could have a pixel matrix forest with say 7 or so trees of black pixels. I need to find the true end points of each tree, find the single shortest path of each tree, then union all skew trees together to form 1 single line(ie, a single shortest path from the furthest 2 end points in the original matrix). all edge weights could be considered 1.

Thanks

Answer 1

How about running Dijkstra's algorithm and if disconnected, connect v and u? What's your criteria for "best place to add a missing edge?" Do edges have weights (like distance)?

Edit: For one idea of "the best place," you could try the path that has minimal sum of shortest paths between all connected pairs. Floyd–Warshall algorithm can be used to find shortest paths between all pairs. So, run Floyd-Warshall for each node in v's tree and u.

Answer 2

Your problem isn't well defined for disconnected graphs. I can always add and edge between v and u.

If you meant that given an acyclic undirected disconnected graph, actually known as a forest, and given a subset of edges as a subgraph, can you find the shortest path between vertices, than this problem is trivial since if there is a path in the full graph, there is one path only.

If this is a general graph G, and you are talking about a forest subgraph G', than we need more info. Is this weighted? Is it only positive weights? If it is unweighted, do some variant of Dijksta. Define the diameter of a tree to be the length of the longest path between two leaves (this is well defined in a tree, since ther is only one such path). Let S be the sum of the diameters of all the trees in G', then set the weight all edges out of G' to 2S, then Dijkstra's algorithm will automatically prefer to step through G', stepping outside G' only when there is no choice, since walking through G' would always be cheaper.