Shortest Path Algorithm

sgs2010
sgs2010 used Ask the Experts™
on

 I am developing a GPS application . The two tables of interest are  - Nodes and Arcs . Arc Table has FromNode , ToNode and Cost fields.
 Please give me some code samples or pseudocode for shortest path algorithm.
 We are using Geomedia Map objects . ( If there is a solution using the Road.net file generated from GeoMedia ,  that would be excellent)
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Commented:
A* is the most common path finding algorithm (and a very good one as well)

wikipedia has a pretty good explanation with example code. If can handle weighings as well (your cost fields). So check it out:
http://en.wikipedia.org/wiki/A*_search_algorithm
Jose ParrotGraphics Expert

Commented:
By looking to that as pure algorithm, the most important generalizations:
  • single-pair shortest path problem
  • single-source shortest path problem
  • single-destination shortest path problem
  • all-pairs shortest path problem
are detailed at http://en.wikipedia.org/wiki/Shortest_path_problem
The most used algorithm in routing probles (like yours) is the Dijkstra's algorithm:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
As you are working with real data, the path will be an Euclidean 3D, and not a distribution of the cities on a single plane. In real applications, distances are often asymetric, say, distance from city A to city B isn't the same as B to A, mainly in mountain areas...
About the Geomedia file format, I think it is good approach to develop a simple translator, than to use the complicated GIS information. If you intend to develop a professional application, then you need money enough to develop such interface, which is a great feature bau, sincerely, I have doubts if it is the best direction.
The first thing to do, I think, is to construct the distances matrix or, better, an adjacent list. Then apply the Dijkstra algorithm, by chosing the source and destin nodes. A Java source code of this creative algorithm can be reached at http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/GraphAlgorithm.java
Jose
Jose ParrotGraphics Expert

Commented:
Right now I have noticed you're looking forward c#...
The c# code of Dijkstra algorithm in
http://www.hann3mann.de/web-artikel/anzeige/dijkstra-algorithmus-in-c-csharp/
has the data structure very similar to yours, so seems to be easy to reuse it. The code also organizes the data in a List (probably an adjacent list). BTW the kind of list is, in this case, transparant to the program.
Jose

Commented:
Don't forget to weight your distances by the cost value that you have as well.

Geomedia also has an add-in called GeoMedia Transportation Analyst that will have this functionality.  Not sure how much it costs though.

Author

Commented:
Thanks for all the comments.
@JoseParrot:
The Dijikstra Algorithm ,  with C# code (which I have tried before ) is not performing well when I try on a large distance ( It takes too too long to calculate)

@dslamb:
Have you  worked on GeoMedia Transportation Analyst  ? ( I am sure there is a way of finding Shortest Path by using Road.net file . But I don't know how this is made possible)

Personally, the most efficient code that I have seen used either a Genetic Algorithm or an Ant Colony Optimization algorithm.  I think a Particle Swarm Optimization algorithm could work too.  It won't be 100% correct all the time, but it's meant to get the closest answer the fastest way.  Search keywords like "genetic algorithm traveling salesman problem" or look through genetic algorithm books in the computer science & regular science sections of your local bookstores and libraries.  A genetic algorithm is definitely what I would use.  Dijikstra Algorithm code is probably easier to find though.
Jose ParrotGraphics Expert

Commented:
The aim of shortest path problem is to find the most economical path from an orign A to a destin B. TSP is quite different , say, in the TSP the source and target are the same (the path ends where started), and requires a path passing through ALL the points, instead of passing only by selected ones from A to B.
DFS or BFS also could be used, but Dijkstra is the algorithm of choice for this case, although of course it isn't the only solution.
Jose
 

Commented:
Sorry, I haven't used it before.  If you have a license (I would imagine it costs extra), then there should be something in the help files that came with it...hopefully.

Jose ParrotGraphics Expert

Commented:
An addition comment on Dijkstra. That's right, it takes a long time for large paths, because it makes the right solution and such problem isn't polynomial.
At thispoint I have some considerations.
First, what is "large distance"? 30 nodes in a universe of 100? If so, this is not a real large number. If Dijkstra runs poorly with paths that size, then the problem is C#.
When student, I had a chance of runing the same code in C++ and C# for a FFT problem. C# ran 30 (thirty) times slower than C++. Let me suggest to try C++. Or check the C# settings. Personally I do preffer C++ for algorithms, due its higher peformance.
C# enthusiasts will refuse that information, alleging that C# can be set correctly for speedy. It is true in part. Personnaly I never saw a C# program runing as fast as C++.
Jose
Oh, I'm sure C++ runs faster than C# and Java...but it's hard for me to believe 30 times faster.  Maybe 2 times.  Certain things are slower (like the initial program start and garbage collection when memory needs to be deleted), but besides those areas, in my personal experience, my algorithms in Java just run about 1.5 times slower (on an average machine by today's standards with the latest JDK).  Even if using assembly in C++ and taking advantage of a 64-bit system (which Java can also do), I wouldn't think 30 times faster; probably 5-10 times more there.

I would more than likely think that the implementation of the algorithm is the culprit.  @sgs2010, if you're knowledgeable in C#, perhaps you can possibly split the algorithm up into multiple threads?  Also, you could try asking in the C# zone on how to speed up a program (and provide the source code you have).  If you can find a C or C++ implementation, perhaps you could try that as well, as @JoseParrot somewhat suggested.  If it still runs slowly, you'll have to use a genetic algorithm, particle swarm optimization, or ant colony optimization algorithm....as you must have tons of nodes and arcs.
Jose ParrotGraphics Expert

Commented:
Performance is the point in your case, so the faster the compiled program the better for your needs. But when the algorithm complexity is exponential then the language isn't the bottleneck. Please accept my comment on the suggestion to go to C/C++ as an approach to try use all the possible ways to achieve the quickest response. You're right, not all equivalent programs in C# and C++ will rate a 30:1 run time. What I have cited is a real case of exercises in the graduation class on FFT.
About hyperthreading, don't expect so much improvements, except if the therads are distributed along different cores or CPUs. Even in this case, the gain is in the best case, by a factor of the number of cores.
Again aggreding with you, the algorithm is the culprit. So, if the exact solution solves the path with unacceptable times, then the solution is to search for heuristic algorithms. Of course, the price is the low optimization. So that is the dillema: slow optimal solution x quick good/reasonable.
Based on the information about TONS of nodes, then let me suggest a totally different approach: problem reduction. To clarify that, I'll use screenshots of my TSP solver, which is a related problem to yours.
In Fig. 1 we see a 35 nodes porblem, with arcs form all to all nodes. There are 595 edges, which is a prohibitive number for brute force algorithm.
 

TSP-35-ALLedges.gif
Jose ParrotGraphics Expert

Commented:
... continuing
The optimal tour by using a Branch-and-bound algorithm spent 35 seconds. When limited to 7 seconds the solution was only near to optimal, as in Fig 2, in opposition to a 3-opt, which is heuristic solution and very quick, as shown in Fig. 3.
In Fig. 4, the number of edges was terrificaly dropped, by using a Delaunay triangulation.
In Fig. 5, the heuristic solution with backtracking, limited to 15 seconds.
So, the results were from 20100 untis for optimal tour. up to 23836 for an heuristic one, but from 35 sec to 15 seconds execution time.
Jose

TSP-35-BaB-7sec.gif
TSP-35-BaB-3opt-20sec.gif
TSP-35-Delaunay.gif
TSP-35-Delaunay-Backtrack-15sec.gif
Jose ParrotGraphics Expert

Commented:
Another approach is to reduce the scope of the problem. For the exposed case, let me suggest a space reduction.
To make the drawings clear, only the Delaunay edges are represented, but you can use an ALL to ALL approach as well.
If Fig 6, the selected source and destin nodes.
Fig. 7 shows  the following sequence: the blue line links source and destin; we find all the edges crossed by the blue line; these are the green lines. Now we reduce the problem to just the nodes at the green lines, which are the yellow nodes. All the other nodes will be ignored.
Fig. 8 shows the selected edges, those which link the selected nodes.
Fig. 9 shows, in red, the solution, based on Delaunay triangles.
Finally, in Fig. 10, the optimal path, in black, determined by using all the possile edges. It is your choice, to go to optimal or heuristic, depending in the restrictions, constraints and, of course, needs.
Jose

Short-Delaunay.PNG
Short-Delaunay-2.PNG
Short-Delaunay-3.PNG
Short-Delaunay-4.PNG
Short-Delaunay-5.PNG

Author

Commented:
led to solution

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial