dijkstra algorithm array...

Anon

I am trying to use dijkstra's algorithm to find the shortest path between two points. The algorithm currently uses data in the format of:

$neighbors[A] = array(B => 2, C => 1, D => 4);
$neighbors[B = array(A => 2, C => 1, E => 4);

However, this data is hard-coded in the example I am using. I would like to extract this data from a mysql database to dynamically fill the array using a while or for loop.

How would I extract the data from the database to provide the data in the same format i.e.

$neighbours[node] = array(link, link, link)

the database stores the data in records such as:

Node: A
Links: B => 2, C=> 1, D => 4

I am familiar with extracting data from the database, but I'm not sure how to fill the arrays.

Thanks for your help!

Bert.

Anon

I would have the table set up in such a way that:

Node | Link | Link_num

A | B | 2
A | C | 1
A | D | 4

Then -

while ($row = mysql_fetch_array($results)) {
$neighbors[$row["Node"]][$row["Link"]] = $row["Link_num"];
}

Think that should populate the array your looking for. Then you would have
$neighbors[A] = Array("B"=>2, "C"=>1, "D"=>4);

Hope that helps

Chris King

Anon

Chris,

Thankyou for your reply.

I have changes my database format, as you suggested.

Suppose I perform your fetch via ODBC, where the while loop above would be written as:

while( odbc_fetch_row( $cur ) ) { 

$street = odbc_result($cur, 1);
    $link = odbc_result($cur, 2);
    $link_num = odbc_result($cur, 3);
$neighbors[$street][$links] = $link_num; 
}

This still does not work, but the extraction is working as I have echoed the output.

Can you see a problem here?

Thanks again,

Bert.

Anon

only 1:
you have $link = odbc_result($cur, 2);

and then you do
$neighbors[$street][$linkS<-- get rid of the s] = $link_num;

Maybe there is the problem?

Chris King

Anon

Cool,

everything is working fine now - but got one more small problem...

When returning the final array from the algorithm ($path)...it is returned as one string, so:

$paths = dijkstra($neighbors, "$From");
while(list($vertex, $path) = each($paths))

if ($vertex=="$To") {
	 echo "Going From Point $From to $vertex: <BR>", implode(", ", $path), "<br>";
};

Returns:

Going From Point A to F:
12, E, D

I need to be able to break the array down (as in 12, 3 and D) into seperate strings for presentation purposes. The array may include more items depending on the path taken....

Anybody know how?

Cheers

Bert