Shortest path between a set of nodes

[sk]

Hi,

I am pretty new to graph theory so apologies if this is a stupid question.

I am trying to achieve the following:
I have a directed graph with a number of nodes connected both "forward" and "backwards" by separate weighted edges - this allows me to understand if I am traversing the network in the forward or reverse direction (the edges have the same weight in both directions).

If I have a subset of nodes that are in the graph what is the shortest 'route' between those nodes? I realise I may be dangerously close to a travelling salesman problem but believe there are some simplifications that mean it is not quite that case. I could be very wrong on that.

To illustrate this - if I had the following graph:

A<>B<>C<>D<>E

Where all weights are 1 and <> represents two bi directional edges.

Given the nodes B, C, D (In any order) I want to know that the shortest path between those nodes is B, C, D. I should get the same result when I ask for the shortest route between, say, D, B, C and D,B etc. I consider B, C, D to be equivalent to D, C, B - it is purely about the path through the network not whether I end up with the forward or backward path.

I may have branches and loops in this graph but in all cases I want to know the order of the nodes that travels through all of the nodes.

I am using this to allow a user to select a path through a network by clicking on nodes to specify the route. If they click on two nodes (B and D) then the shortest path between them is shown, if they click on a third node (C) then the shortest path between nodes B and C should be shown and then the shortest path between C and D. I believe the problem is when the nodes are not given in order such that the user clicked B, D and then C - the correct thing to highlight would not be B-D-C but B-C-D.

In order to solve this I have tried to create a new graph that consists of only the nodes selected. I then use the shortest path lengths and shortest path routes of the original graph to attempt to connect this new graph up as a single path. I try to choose nodes for connection based on which were closest together in the original graph, do not pass through other selected nodes in the original shortest path and do not connect the graph into loops or leave the graph split into two. Once I build this new graph I find which nodes have only one neighbour (the end of the path) and then ask for the shortest path between them. This gives me the correct node order, I then ask for the shortest paths between each of these nodes from the original graph.

I find that this works most of the time but I keep finding cases where my algorithms do not work. I can, and will, keep testing and fixing these but I can't help thinking I have missed something and that there is a simpler way to achieve this.

If anyone could point me in the direction of a better way to attach this I would very much appreciate it.

Kind regards
Stephen

[Daπid]

On 25 May 2016 at 15:19, sk <6b65...@gmail.com> wrote:
> realise I may be dangerously close to a travelling salesman problem

I think that is exactly what you have. The core of the problem is that
if you have N nodes, there are N! possible orderings, and no good way
of knowing in advance which one is the shortest: you have to try them
(almost) all. For small values of N this is brute-forceable (and your
precomputations help), but it will soon explode.

Since your user will be clicking, you won't have too many nodes, so I
think you can get near optimal solutions with simulated annealing:
start with some, order and try perturbing it and see if it helps. You
can keep trying options until your user gets bored of waiting.


/David.

[sk]

Thanks for the confirmation.

This will be for small graphs, probably less than 2000 nodes, with less than 100 selected nodes so it should remain in the realms of the possible to brute force (and I can probably optimise by ignoring unchanged parts).

I figured that since calculating all shortest paths between all nodes was computationally trivial there may be a trick to match up the 'chunks'. I was thinking that the travelling salesman issue was 'simplified' because I knew the shortest path between all of the node pairs already and the nodes will always form a simple 'path' - happy for the confirmation that the assumption was wrong.

Many thanks
Stephen

[Daπid]

On 25 May 2016 at 16:27, sk <6b65...@gmail.com> wrote:
> This will be for small graphs, probably less than 2000 nodes, with less than
> 100 selected nodes so it should remain in the realms of the possible to
> brute force (and I can probably optimise by ignoring unchanged parts).

100! ~= 10^158 I'd say a more reasonable limit for brute forcing is 10
nodes. There are better algorithms, still exact, that scale better
than brute force [1], but if you can live with a near optimal
solution, I think some of the heuristics will be much easier to
implement and faster to run [2]. Simulated annealing is probably the
easiest, and has the advantage that you can run it for an arbitrary
amount of time (tradeoff patience-shortness). It is also easy to
launch several parallel instances, and pick the best one.

> I was thinking that the travelling salesman issue was 'simplified' because I knew the shortest path between all of the node pairs already and the nodes will always form a simple 'path' - happy for the confirmation that the assumption was wrong.

Computing all the shortest pairs is just N^2, so comparably cheap. It
is the global ordering that matters.


[1] https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm
[2] https://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

[sk]

I overdid it with 100, I think 20 would be a more realistic max, but point taken.

Thank you so much for these links - they made me realise (amongst many other things) that I don't need the optimal solution, just one that looks about right - users can always select another node to force a route to be taken.

I think I have gone some way to implementing the Nearest Neighbour algorithm (without realising it), and added another rule of not passing through the same nodes twice. I was really struggling to know how to describe these things and so that link was very helpful. I will look at implementing some of these optimal approximations.

Many thanks
Stephen

[Daπid]

On 25 May 2016 at 17:40, sk <6b65...@gmail.com> wrote:
> I overdid it with 100, I think 20 would be a more realistic max, but point
> taken.

If finding the shortest path takes you a microsecond (a realistic
value), checking all the 20! combinations only takes 77 millennia.
Exponentials grow *very* fast.

If you have a local optimiser, in my experience, adding hard
constraints, like not passing twice through the same node, harm more
than help because they create "forbidden regions" in the configuration
space, making much more difficult to go around than through. They only
make sense if they can greatly reduce the search space.