Shortest route

[motarules]

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

[SlickHawk]

Run Dijkstra's from A->D->F->H.
And then again from A->F->D->H.

See which one has a smaller cost.

[motarules]

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

[MrViggy]

That sounds like the Traveling salesman problem (http://en.wikipedia.org/wiki/Traveling_salesman_problem). If that is the case, there is no efficient algorithm for solving this.

Viggy