Shortest path in a map

Question

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

I have tried to use Dijkstra in php but I couldnt manage to implement it (too difficult for me). Another problem I felt was that if I use Dijkstra I would need to consider all the nodes, that may be perhaps very inefficient in a large graph. So does anybody has a code relating to the above problem? It would be great if somebody atleast shows me a way of solving this problem. I have been stuck here for almost a week now. Please help.

Answer 1

Here is a literate version of the Dijkstra algorithm, in Java, that may help you to figure out how to implement it in PHP.

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

Answer 2

This sounds like a classic case of the A* algorithm, but if you can't implement Dijkstra, I can't see you implenting A*.

http://en.wikipedia.org/wiki/A*

edit: this assumes that you have a good way to estimate (but it is crucial you don't over-estimate) the cost of getting from one node to the goal.

edit2: you are having trouble with the adjacency list representation. It occurs to me that if you create an object for each vertex in the map then you can link directly to these objects when there is a link. So what you'd have essentially is a list of objects that each contain a list of pointers (or references, if you will) to the nodes they are adjacent to. Now, if you want to access the path for a new node, you just follow the links. Be sure to maintain a list of the paths you've followed for a given vertex to avoid infinite cycles.

As far as querying the DB each time you need to access something, you're going to need to do this anyway. Your best hope is to only query the DB when you NEED to... this means only querying it when you want to get info on a specific edge in the graph, or for all edges for one vertext in the graph (the latter would likely be the better route) so you only hit the slow I/O once in a while rather than gigantic chunks all at once.

Answer 3

Dijkstra algorithm returns shortest paths from given vertex to other vertexes.
You can find its pseudo-code in Wiki.

But I think you need Floyd algorithm which finds shortest paths between all vertexes in a DIRECTED grapth.

The mathematical complexity of both are pretty close.

I could find PHP implementation from the Wiki for both of them.