The shortest path on the map

Question

I developed a weighted graph using a normalized adjacency list in mysql. Now I need to find the shortest path between the two given nodes.

I tried using Dijkstra in php, but I was not able to implement it (too complicated for me). Another problem that I felt was that if I use Dijkstra, I will need to consider all the nodes, which may be very inefficient on a large chart. Does anyone have any code related to the above problem? It would be great if at least someone showed me a way to solve this problem. I've been stuck here for almost a week. Please, help.

Answer 1

This sounds like a classic case of the A * algorithm, but if you cannot implement Dijkstra, I don’t see you insert A *.

A * on Wikipedia

edit: this suggests that you have a good way to estimate (but it is imperative that you not overestimate) the cost of getting from one node to the target.

edit2: you are having trouble presenting an adjacency list. It occurs to me that if you create an object for each vertex on the map, you can directly link these objects when there is a link. So, you have essentially a list of objects, each of which contains a list of pointers (or links, if you like) to the nodes to which they are adjacent. Now, if you want to access the path for the new node, you just follow the links. Be sure to keep a list of the paths that you followed for this vertex to avoid endless loops.

As for database queries, every time you need to get something, you still have to do it. Your best hope is to only query the database when you DON'T ... it means only querying when you want to get information about a particular edge in the graph or for all edges for one vertex on the graph (the latter is likely to be the best route), so from time to time you choose slow I / O, rather than giant pieces at once.

Answer 2

Here is a literate version of Dijkstra's algorithm in Java that can help you figure out how to implement it in PHP.

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29

Answer 3

Dijkstra's algorithm returns the shortest paths from a given vertex to other vertices. You can find his pseudo-code on the Wiki .

But it seems to me that you need a Floyd algorithm that finds the shortest paths between all the vertices in a DIRECTED grapth.

The mathematical complexity of both is pretty close.

I could find a PHP implementation from the Wiki for them.