Create the lowest-cost path between two vertices

Question

I have a weighted undirected graph. Given two vertices in that graph that have no path between them, I want to create a path between then by adding edges to the graph, increasing the total weight of the graph by as little as possible. Is there a known algorithm for determining which edges to add?

An analogous problem would be if I have a graph of a country's road system, where there are two cities that are inaccessible by road from each-other, and I want to build the shortest set of new roads that will connect them. There may be other cities in between them that are connected to neither, and if they exist I want to take advantage of them.

Here's a little illustration; red and green are the vertices I want to connect, black lines are existing edges, and the blue line represents the path I want to exist.

Is there a known algorithm that gives the edges that are missing from that path?

Answer 1

You could use the A* algorithm with a weight of zero for existing edges and distance (or whatever cost makes sense) for missing edges.

https://en.wikipedia.org/wiki/A*_search_algorithm

Answer 2

Actually Dijkstra with some preprocessing is best friend for you.

I answered problem that can be similar to this one: What is the time complexity if it needs to revisit visited nodes in BFS?

What I see in common - you want to use as much existing roads as possible. Also you sometimes need to break that and build new road. The point is in setting the proper weights for existing ones and for "possibly new ones".

What would be my approach - lets say, that each 1 km of existing road has cost of 1. You can sum all existing roads in your graph and lets say there are 1000km in total. Then I would preprocess whole graph and from each node(city) I would create path to all other non-diretly-connected cities and each of them would cost 1000 + 1000 per kilometer and then run Dijkstra on it.

It will automatically use as much existing roads as possible and create as less new roads as possible.

Also you can play with that settings a bit to achieve what you want.

Imagine there are two cities that are only 100m away from each other. And there is actually path between them from existing roads that takes 20 000km. With the settings I have suggested you will get 20000km path as the best one (which satisfy need of "dont build any new roads if not necessary"). Sometimes you actually want this. Sometimes you do not. In case you do not, you can think about "ok, if I build like a little of extra road and it dramatically lowers the distance, its still better solution". If this is the case, you can think about lower the price of new roads (like removing the initial cost, or per kilometer cost or both of it - it depends on what you take as best output).

Answer 3

I don't think that there's an accepted algorithm. But you could try and do the following. First run Vitterbi Triangulation, then run a depth first search on this fully connected graph. Take the sum of the new links in the path from A -> B. Remove the longest new link, and repeat. Once the path from A -> B cannot be reached, check the previous solutions to see which of the solutions had the smallest sum of new links.