4

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.

5lackp1x3l0x17
  • 349
  • 2
  • 7
  • 14
  • Do you want to do this in the database, or do it all in memory? – James Black Dec 09 '09 at 01:31
  • What do you suggest? I am ok with both, but memory is preferable. – 5lackp1x3l0x17 Dec 09 '09 at 01:34
  • What exactly are you stuck on? Also, you are correct that Dijkstra will seem slow for large data sets. – San Jacinto Dec 09 '09 at 01:35
  • See I can implement Dijkstra if a weighted adjacent matrix is given, but when it comes to the adjacency list I have difficulty. Another aspect if I use Dijkstra every time I have to find the shortest path, I will have to query in mysql via php every node in the map, that may prove to be too much time consuming. – 5lackp1x3l0x17 Dec 09 '09 at 01:41
  • Will i find it easier if I retrieve the entire adjacency list and distance from my database and convert it into an adjacency matrix in my program in php? – 5lackp1x3l0x17 Dec 09 '09 at 01:47
  • Honestly, and I don't mean to sound like a jerk, that will depend on your personal programming abilities. It might help and it might not. But either way, it's a penalty in both memory consumption and run-time to load your entire dataset at once. Please see my edited answer. – San Jacinto Dec 09 '09 at 01:54
  • You dont sound like a jerk. I am very beginner programmer and these views you people here present help me improve myself. I dont have anyone to solve my doubts and you all are my only helpers. – 5lackp1x3l0x17 Dec 09 '09 at 02:02

3 Answers3

5

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

A* on Wikipedia

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.

Thunder Rabbit
  • 5,405
  • 8
  • 44
  • 82
San Jacinto
  • 8,774
  • 5
  • 43
  • 58
  • Ok now thats something.. But that would mean importing all the nodes from the DB, creating a map, everytime I run my program? – 5lackp1x3l0x17 Dec 09 '09 at 01:59
  • Actually, I just understood something after reading your question again. The list is already built in the DB. In this case, you should be able to do the same thing except following the links in your database. Depending on how you have the tables structured, this is either simple or very difficult. Ideally, you'd have one table for the vertices and one for the edges. In this case, you have the same exact structure I mention above, just in DB form. – San Jacinto Dec 09 '09 at 02:03
2

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

James Black
  • 41,583
  • 10
  • 86
  • 166
2

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.

Dmytrii Nagirniak
  • 23,696
  • 13
  • 75
  • 130
  • If the OP is worried about large datasets like it sounds, these algorithms aren't going to do the trick for obvious run-time reasons, let alone polynomial memory consumption. I have seen some implementations that will do clustering of the sets to reduce this, and then you run another algorithm inside each cluster you visit... but i forget if you have up the proof of a shortest path by doing that. – San Jacinto Dec 09 '09 at 01:45