Printable View
Hello everybody, i have a non directed graph with weighted edges and i'm having trouble trying to solve the following problem :
A man starts in a city (e.g. A), he goes to city (e.g. H), passing through some mandatory cities (e.g. D and F).
I need to find the path with minimum cost (the man can revisit the same city if necessary).
Run Dijkstra's from A->D->F->H.
And then again from A->F->D->H.
See which one has a smaller cost.
Well the solution needs to work up to 10000 intermediary cities. I already tried with dijkstra but always picking the closest next city doesn't give me the optimal solution, only brute force works (with a small number of cities).
That sounds like the Traveling salesman problem. If that is the case, there is no efficient algorithm for solving this.
Viggy