15,921,837 members
1.00/5 (1 vote)
See more:
I have created a adjacency list in mysql which is as follows

----------------------------------
|node | adjacentnode | distance |
|---------------------------------
| 1    | 2            | 5 |
| 2    | 3            | 4 |
| 4    | 1            | 2 |
| 2    | 1            | 5 |
| 3    | 4            | 3 |
| 1    | 4            | 2 |
| 4    | 2            | 1 |
----------------------------------

I need to find the shortest path between two nodes in php using any preferable algorithm. How am I actually supposed to code that??

I am finding it difficult to actually implement Dijkstra using an adjacency list made in a database. Also this code will be accessed a number of times having a considerably large amount of nodes, so it should be efficient too.
Posted
Updated 8-Dec-09 15:55pm
v3

## Solution 1

I wrote this last year. I hope it helps.
```<?php
class KruskalsAlgorithm
{
public function shortest_path( \$path_list )
{
\$points = array();
\$shortest_path = array();
foreach ( \$this->sort_2d( \$path_list , 2 ) as \$path )
{
if ( !in_array( \$path[ 0 ] , \$points ) || !in_array( \$path[ 1 ] , \$points ) )
{
\$shortest_path[] = \$path;
if ( !in_array( \$path[ 0 ] , \$points ) )
\$points[] = \$path[ 0 ];
if ( !in_array( \$path[ 1 ] , \$points ) )
\$points[] = \$path[ 1 ];
}
}
return \$shortest_path;
}

private function sort_2d( \$records , \$field , \$reverse = false )
{
\$hash = array();
foreach ( \$records as \$record )
{
\$hash[ \$record[ \$field ] ] = \$record;
}
( \$reverse ) ? krsort( \$hash ) : ksort( \$hash );
\$records = array();
foreach ( \$hash as \$record )
{
\$records []= \$record;
}
return \$records;
}
}

array(1,2,5),
array(2,3,4),
array(4,1,2),
array(2,1,5),
array(3,4,3),
array(1,4,2),
array(4,2,1)
);

\$pa = new KruskalsAlgorithm();

?>```

v2