Hi guys
i'm trying to find all the paths from a starting node to an ending node in a network (refer to the attached pic)
what im doing is that i'm populating an array ($arr) with the connections that each node has with its neighbours.
then in the function pathx, i'm trying to recursively find all paths that lead from a given starting node to a given ending node.
now 3 essential assumptions should be made in the algorithm that guarantee a right output:
1- don't forward to an incoming node (that is, if the path is 1 - 0 - 2, i cannot go back to 0 from 2)
2- dont forward to a node already in the sequence (that is, 1 - 0 - 2, i cannot go from 2 back to 1 because it's already there)
3- if u get to a node where the only next possible node is already in the sequence, dismiss that path (example: 0 - 1 - 3 - 4 - 5 - 2 ==> then from 2 u can only go to 0 or 1, which are already in the sequence... then the mistake was 5- 2, then from 5 u gotta find another path)
the code i've written so far returns promissing results, but i couldnt figure out how to implement the previous 3 essential points... my main problem is how to store and process the sequence during recursion (dynamically append new nodes or dismiss the entire sequence, or compare the new node to previous nodes in the sequence)
to see the results, comment the echo"arr[".$start."][".$i."]"; line (which shows how the recursion proceeds) and uncomment the other echos...
any help would be highly appreciated...
thanx
<?
$arr = array(0 => array(0=>1,1=>2));
$arr[1] = array(0=>0,1=>2,2=>3,3=>7);
$arr[2] = array(0=>0,1=>1,2=>5);
$arr[3] = array(0=>1,1=>4);
$arr[4] = array(0=>3,1=>5);
$arr[5] = array(0=>2,1=>6);
$arr[6] = array(0=>5,1=>7);
$arr[7] = array(0=>1,1=>6);
function pathx($arr, $prev, $start, $end)
{
foreach ($arr[$start] as $i => $value)
{
echo"arr[".$start."][".$i."]";
// echo $start.' - ';
if ($arr[$start][$i] == $end)
{
echo $end;
// echo"<br>";
}
else
if ($arr[$start][$i] == $prev){echo" | ";}
else
{
pathx($arr, $start, $arr[$start][$i], $end);
// echo $arr[$start][$i].' - ';
}
}
}
?>
[attachment deleted by admin]