Click here to Skip to main content
15,921,837 members
Please Sign up or sign in to vote.
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

1 solution

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;
	}
}

$adjacency_list = array(
	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();

print_r( $pa->shortest_path( $adjacency_list ) );

?>
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900