How to Find the Shortest Path Through N Points in a Weighted, Undirected Graph?

[haki]

I've got a small assignment to do on graphs but it's a bit frustrating that no standard algoritms such as Dijkstra, Bellman-Ford, etc. can be used or at least I don't know how could they help.

Given a graph one is to find shortest path through N points. That's it. Starting point can be anything you like just the path must go trough N distinct points where the path itself should be as short as possible. The graph is weighted, undirected.

Simple Greedy algorithm works fine for small inputs but when N gets > 100 then it is useless. I'd like to see it work for N > 1000 in resonable time. Sadly I don't see how any of the well known algorithms could be put into practice here. Any ideas, pointers would be greately apprichiated...

 

[Hurkyl]

Given a graph one is to find shortest path through N points. That's it. Starting point can be anything you like just the path must go trough N distinct points where the path itself should be as short as possible. The graph is weighted, undirected.

This is essentially the travelling salesman problem.

 

[haki]

This is essentially the travelling salesman problem.

silly me, will look into TSP algorithms, just need to modify not to go trough all the points but just N points. Since the graph can have M points but I am interested in visiting only N points and not all.

For starters something along the lines of a simple BFS with heuristic to always select shortest neighbor and only visit N nodes should work out fine.

Sometimes it helps to think out loud.

I was a bit to eager to try out Dijkstra or Bellman-Ford, can not match an algorithm to a problem, it goes the other way around.

 

[haki]

There is just a slight problem, if I am not mistaken the TSP requires that the graph is complete.

But my graph is not complete - it is more like railway diagram, where the vertices are train stations and edges are the rails, it is connected but not complete and I want to visit N train stations where my path will be shortest. Any ideas?

 

[-Job-]

If your problem is equivalent to TSP then don't bother searching for an efficient (polynomial time) algorithm.

The problem is similar to TSP, on the other hand i can't think of a polynomial time reduction from TSP to your problem off the top of my head. Until you have a reduction to TSP (or to any NP-Complete problem) it's possible that there is an efficient solution for your problem.

 

[Hurkyl]

There is just a slight problem, if I am not mistaken the TSP requires that the graph is complete.

Nope. But it's easy to show that solving the TSP on an arbitrary graph is equivalent to solving the TSP on a complete graph.

 

[Hurkyl]

The problem is similar to TSP, on the other hand i can't think of a polynomial time reduction from TSP to your problem off the top of my head.

The TSP is the N=M case of his problem.

 

[-Job-]

That's not sufficient by itself though because supposing we're given a TSP instance with N nodes, if i pass it to a solver of Haki's problem and ask for the shortest sequence of N nodes, then the sequence it returns may not be a hamiltonian cycle - the start and end nodes could be disconnected.

What else did you have in mind?

 

[haki]

Nope. But it's easy to show that solving the TSP on an arbitrary graph is equivalent to solving the TSP on a complete graph.

What if my arbitrary graph is
6 train stations where the geometric layout is like the 5 stations are at the edges of a 5 pointed star with 6th station being in the center as the hub, and the 5 stations are only connected to the hub station i.e. G({a,b,c,d,e,h},{a-h,b-h,c-h,d-h,e-h}).

There is no way for the sales person to visit all the stations without going trought the hub 5 times ... but doesn't TSP state that each station should be visited only once? Or am I missing something? Graphs are not my strong point.

As algorithm goes a pointer for approximation algorithm would be great.

 

[Hurkyl]

There is no way for the sales person to visit all the stations without going trought the hub 5 times ... but doesn't TSP state that each station should be visited only once?

Good call; I hadn't realized you were allowing the salesman to return to a node. I still think there is an equivalence, but it's more difficult, and I haven't worked out the details.

 

[haki]

The salesman should not visit any node more than once.

In the 5 point star graph, if I'd put it in my problem solver let's say the solver is PS(G,N) where PS is the solver, G is the graph(not-connected, undirected, weighted) and N is the number of stations to visit.

for PS(G({a,b,c,d,e,h},{a-h,b-h,c-h,d-h,e-h}),2) I'd want it to output any edge, a-h would work fine, for N = 3, I'd want it to output a-h,h-b or any other combination, but for N=4 I'd want it to fail saying there is no path where the salesman would visit 4 stations without revisiting any station more than once.

Right now I have something in the lines of DFS. I take a random starting point and select next shortest neighbour repeating until the desired number of stations is visited but handling of dead ends is quite poor.

In the 5 star graph for N=3, if the algorithm starts at the center, it would take next shortest neigbour let say a, so we have first edge h-a, but a is a dead end, so it would go back and select next neighbour b, edge h-b is another dead end, then with c,d and e and then it would finally conclude this is a bad starting point and start with a different starting point. I am sure there is a better way just don't know of it.

If I could use Lin-Kernighan or something similar that's awesome, but for LK afaik it takes a matrix of distances between any pair of cities, but in my case the shortest distances between 2 cities could require a revisit of already visited city.