- #1

- 161

- 0

## Main Question or Discussion Point

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

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