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

}

$checked[$min] = true;

return $min;

}

Потом опять же в цикле просматриваем связи найденной точки с остальными точками в графе, и, если сумма цены ребра, соединяющего найденную точку с данной и расстояния от исходной точки до найденной меньше, чем расстояние от исходной точки до данной, то мы выполняем замену. Также при этом сохраняем значение пункта пути – массива $way:

for ($i = 0; $i < MAX_NODES; $i++)

{

$min = minDist($dist);

for ($j = 0; $j < MAX_NODES; $j++)

{

if ($dist[$min] + $matrix[$min][$j] < $dist[$j])

{

$dist[$j] = $dist[$min] + $matrix[$min][$j];

$way[$j] = $way[$min];

$way[$j][] = $j;

}

if ($dist[$min] + $matrix[$j][$min] < $dist[$j])

{

$dist[$j] = $dist[$min] + $matrix[$j][$min];

$way[$j] = $way[$min];

$way[$j][] = $j;

}

}

}

В результате получаем массив минимальных расстояний - $dist и двухмерный массив кратчайших путей - $way.

5.2. Реализация алгоритма Йена

Для нахождения k кратчайших путей в графе используется рекурсивная функция findWays, которая в качестве параметров принимает матрицу данных, номера исходной и конечной вершин. Алгоритм этой функции таков: выполняется поиск одного кратчайшего пути графа, проверяется, есть ли найденный путь в массиве путей $ways и, если нет – сохраняем путь и в цикле убираем по одному ребру в найденном пути и вызываем функцию findWays, передавая ей уже обновленную матрицу данных:

function findWays($matrix, $start, $end)

{