Реферат: Нахождение кратчайших путей в графе Алгоритм Йена

$res = findShortestWay($matrix, $start, $end);

if ($res != null && !in_array($res, $ways))

{

$ways[] = array();

$ways[count($ways)-1][1] = $res[1];

$ways[count($ways)-1][0] = $res[0];

for ($i = 0; $i < count($res[1])-1; $i++)

{

$invalid_matrix = $matrix;

$invalid_matrix[$res[1][$i]][$res[1][$i+1]] = INFINITY;

$invalid_matrix[$res[1][$i+1]][$res[1][$i]] = INFINITY;

findWays($invalid_matrix, $start, $end);

}

}

}

Стоит заметить, что массив $ways является трехмерным – первый ключ соответствует номеру пути, второй указывает на а) длину пути б) массив вершин пути

После этого выполняется сортировка полученного массива $ways по возрастанию по длине пути.

for ($i = 0; $i < count($ways)-1; $i++)

{

for ($j = $i+1; $j < count($ways); $j++)

{

if ($ways[$i][0] > $ways[$j][0])

{

$buf = $ways[$i];

$ways[$i] = $ways[$j];

$ways[$j] =$buf;

}

}

}