Notices
Results 1 to 2 of 2

Thread: shortest path optimizations

  1. #1 shortest path optimizations 
    New Member
    Join Date
    Nov 2007
    Posts
    1
    I'm using dijkstras shortest path algorithm with about 1.5 million edges. As you figured, this is pretty slow. I'm trying to find some ways to optimize dijkstra's algorithm to determine the shortest path faster. Since dijkstra's finds the shortest path to ALL of the points, i made it stop if it finds the end point. This helps quite a bit, but still needs more.

    Some other information:
    I'm using road data from the census TIGER/LINE files for the edges. I'm only using 1 state's roads to start. I'm using the class in skmDataStructures for graph and node datatypes & coding in c#.net 2005. Dijkstra's is working well for a few points, but takes a long time to run on more nodes. is there a better algorithm or implementation? is there a way to compromise accuracy for speed? any information would be appreciated!


    Reply With Quote  
     

  2.  
     

  3. #2  
    New Member
    Join Date
    Nov 2007
    Location
    india
    Posts
    1
    first of all ..tough job there
    dijkstra's alg is unfortunately the fastest known as far as i know.
    but like you said ,there are some know optimisations..
    i am unfamiliar with c#/.net.
    but i am sure they are like any other OOP.
    my thoughts are that after using proper data structure,you must make sure you inline most of the function calls.
    the number of vertices can help decide something more important..
    if it is dense,you might as well go for a much faster 2D array..
    i will try to think more if you give me the number of vertices,the pseudocode of your program


    Reply With Quote  
     

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