Dijkstra optimization - URGENT!

[hardcoder]

Hi

I have a VB proggy that takes a Map and then searches for the shortest path between two points - actually between several pairs in one run - as many as 600-800 pairs -
naturally the proggy gets damn slow!

Please suggest what optimizations can be done to improve the algo?

I compute the paths on demand right now - any suggestions on saving the paths to a db?

Broad picture : i am allocating shift employees to pick and drop cabs - several hunderd employees in 8 - 10 shifts a day - cabs for each shift for pick and drop - so a day's route report requires starting with the first shift and allocating the employees to the cabs keeping in mind the requirement of minimum distance travelled by each cab...

visit my WS www.Lyracomputing.com too...

thanks!

[thinktank2]

Your problem is related to the "The travelling salesman problem"

To find a optimal solution you can use Genetic Algorithms.

Just Search google..

http://www.google.com/search?hl=en&q...lem+algorithms

[sql_lall]

Have you heard of the A+ (or maybe just A) Algorithm. It's this thing written to help find the shortest route, and can be found all over the 'net. It might be able to help.

[hardcoder]

Hi guys,
Thanks.

Yeah,my problem is related to the TSP... I already did some research thru it - but in the end I ended up using an implementation of Dijkstra in a somewhat crude manner - i'll getinto real optimizatinos in a few days and will get back to u.

I have heard of the A+ algo too- but Dijkstra was enough brainracking for me at least for now!

Thanks again
Hardcoder