Graph Expansion

I'm currently working on an interesting graph problem, I can't find any algorithms or other st开发者_开发百科ackoverflow questions which mention anything like this.

If I have a graph (undirected, cyclic) and a list of commonly used paths, what is the best way to reduce the average path length by adding in N more edges?

EDIT:: Important point, which might help, all paths start at the same node.

Answering my own question, to cover what I've already considered.

The obvious solution is simply to sort the common paths by order, and slot in a connection between the two ends, and keep doing this until you run out of edges to insert. However, I suspect there is a more intelligent solution.

You could just try inserting all possible edges and see how much the shortest path decreases for each of your given start/end points. Pick the best edge and repeat.

The usefulness of edges depends on what other edges have been added, so if you really want optimality, you'd have to try all sets of N edges. That sounds a tad expensive. Wouldn't surprise me if it was NP-hard.

Interesting question!

Another possible solution, which sounds like it might be the best heuristic, is to take the weighted average of all the end nodes (weighted by path importance), then find the node which is closest to the computed average point. Connect to that node.

Obviously that only works if the nodes are laid out in space somehow, but it's a good analogy.