Shortest route
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Shortest route

  1. #1
    Join Date
    Apr 2009
    Posts
    2

    Shortest route

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

  2. #2
    Join Date
    Mar 2009
    Posts
    19

    Re: Shortest route

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

    See which one has a smaller cost.

  3. #3
    Join Date
    Apr 2009
    Posts
    2

    Re: Shortest route

    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).
    Last edited by motarules; April 7th, 2009 at 07:14 AM.

  4. #4
    Join Date
    Feb 2002
    Posts
    4,640

    Re: Shortest route

    That sounds like the Traveling salesman problem. If that is the case, there is no efficient algorithm for solving this.

    Viggy

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center