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)

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

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

- single-pair shortest path problem
- single-source shortest path problem
- single-destination shortest path problem
- all-pairs 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

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

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

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

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

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.

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

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

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

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial