{
if ($i == $start)
$dist[$i] = 0;
else
$dist[$i] = INFINITY;
}
$way[$start][] = $start;
Далее начинается основная часть алгоритма. Проходим в цикле по каждой точке графа: находим точку с минимальным значением расстояния. Дляэтогоиспользуемфункцию minDist:
function minDist($dist)
{
global $checked;
$min_v = INFINITY;
for ($i = 0; $i < MAX_NODES; $i++)
{
if (!isset($checked[$i]) && $dist[$i] < $min_v)
{
$min = $i;
$min_v = $dist[$i];
}
}
$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)
{
global $ways;
$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;
}
}
}
После возврата первых k элементов массива $ways наш алгоритм можно считать реализованным.
6. Заключение
Хотя поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков.
Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы.