﻿ Nicklas Gavelin - Longest path search algorithm

# Longest path search algorithm

Published on Friday, April 6, 2012

The code tries to find a path that gives profit, for example. If we got a tree with three nodes that are all connected we want to find a path that leads to that we have to pay less each time we walk it.

``````\$start = 1;
\$end = array();

// Longest path algorithm
\$array_vertices =
array(
array(1,7,3),
array(7,6,4),
array(6,1,1/5),
array(8,6,100),
array(7,5,5),
array(5,4,3),
array(4,2,1),
array(2,5,1/4),
array(2,1,1/7)
);

\$start_connected = array();
foreach(\$array_vertices as \$v)
{
if(\$v == \$end && \$v != \$origin)
{
echo \$v . " ";
\$vinst *= (double)\$v;
\$step[] = \$v;
if(\$v == \$start)
{
if(\$vinst > 1) {
\$ended = true;
break;
}
else
{
\$endedWithoutProfit = true;
break;
}
}
\$end = \$v;
}
unset(\$temp_connected[\$v][\$v]);
}

if(count(\$temp_connected) <= 0 || \$endedWithoutProfit)
{
\$ended = false;
\$start_connected = array();

if(!\$endedWithoutProfit)
{
foreach(\$array_vertices as \$v)
{
if(\$v == \$start && \$v != \$end)
\$start_connected[\$v][\$v] = true;
}
}

\$temp_connected = \$start_connected;

if(count(\$start_connected) == 0 || \$endedWithoutProfit)
{
if(\$endedWithoutProfit || \$vinst <= 1)
{
findEnd(&\$array_vertices, &\$start, &\$end, &\$origin);

if(count(\$end) == 0)
{
\$ended = true;
if(\$vinst <= 1)
{
\$error['noprofit'] = "Ended without profit";
}
else
{
\$error['notfound'] = "Could not find a path";
}

break;
}

\$vinst = 1;
\$start_connected = array();

foreach(\$array_vertices as \$v)
{
if(\$v == \$start && \$v != \$end)
{
\$start_connected[\$v][\$v] = true;
}
}

if(count(\$start_connected) == 0)
{
\$error['noconn'] = "There is no path";
break;
}

\$connected = array();
foreach(\$array_vertices as \$v)
{
if(\$v == \$end)
\$connected[\$v][\$v] = true;
}

if(count(\$connected) == 0)
{
\$error['noconn'] = "There is no path";
break;
}

\$temp_connected = \$start_connected;
\$step = array();
\$step[] = \$end;
\$endedWithoutProfit = false;
\$vinst *= \$end;
}
else
{
\$ended = true;
\$error['notfound'] = "Could not find a path";
break;
}
}
}

foreach(\$step as \$s)
echo "FROM: \$s TO \$s, Weight: \$s";

echo "Vinst: \$vinst";

if(\$error)
foreach(\$error as \$e)
echo "\$e";

function findEnd(\$array_vertices, /*\$array_nodes,*/ \$start, \$end, \$prev)
{
\$max = NULL; \$i = 0; \$unset = -1; \$end = null;
foreach(\$array_vertices as \$v)
{
if(\$v == \$start && \$prev != \$v && (\$max == NULL || \$v > \$max))
{
\$end = \$v;
\$max = \$v;
}

if(\$prev == \$v)
\$unset = \$i;
\$i++;
}

if(\$unset > -1)
{
\$prev = \$end;
unset(\$array_vertices[\$unset]);
}
}
``````
comments powered by Disqus