- #1

haki

- 161

- 0

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...