Hi Kholoud Sanyour,

I think that implementation of Dijkstras algorithm is quite problematic because it has following limitations:

- Can’t have negative cycles

- The distance is calculated 1-to-many. Many-to-many is better

- Limited memory due the 1-to-many approach.

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

This link can satisfy your problem.

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Dear Kholoud:

You need to kow about nodes and edges to implement Dijkstra algorithm and you don't have access to google maps database. An alternative is to use OpenStreetMaps. You can download the data [1] you need and implement the solution [2]

[1] http://wiki.openstreetmap.org/wiki/Downloading_data

[2] http://stackoverflow.com/questions/11127852/openstreetmap-routing-java-swing-application

Kind regards

Take a look: https://graphhopper.com/#overview It uses OpenStreetMaps.

"GraphHopper offers memory efficient algorithms in Java for routing on graphs. E.g. Dijkstra and A* but also optimized road routing algorithms like Contraction Hierarchies. It stands under the Apache License and is build on a large test suite."

And the source code for Android is available in Github: https://github.com/graphhopper/graphhopper/tree/master/android

Regards

I'm not sure why you would want to do this. Dijstra's algorithm works at the graph level, calculating the cost of  traversing from a start node to every other node in the graph. Within the various APIs available for Google Maps none of them allow this level of access. But the routing APIs allow fast path finding, with options for multiple routes, way points  and modes of travel. If you need to find many routes at once, the DistMatrix API allows you to calculate many routes in one API call to Google.

I've used Graphhopper quite a lot it's a good and stable piece of software. The principle drawback is that it relies on the correctness of Open StreetMap, although for many cities OSM appears to be good enough. If you look at the GraphHopper documentation you will find that an implementation of Dijkstra comes with the distribution (along with A* etc) and that you can access the data structures created at a lower level (but looking at the documentation they are more complex than a simplistic graph of streets and junctions).

Perhaps you could tell us more about the actual problem that you wish to solve, as I suspect that one of the solutions described above will provide you with the functionality that you're expecting from Dijkstra.

One final point....  Dijkstra is an exhaustive search, if you were to set it loose on the street graph of a major city or continent you might be in for a long wait!

Please see the following paper published by me if you can get it.  I have given an algorithm for Dijkstra method for finding the shortest distance path between two nodes.  At that time  I had implemented in VB 6

Decision support system for optimal scheduling of convoys by road, Operational Research and its Applications, 2004, Vol. II, pp. 319-333. ORSA.

Hi Kholoud,

actually, i don't see a problem here: if you have marked points in the google map, you usually know the geo-coordinates. From these geo-coordinates you can calculate the distance between two points and use this distance for the edge weight connecting the two points. The rest is the plain dijsktra algorithm.

Best,

  Marc