Работа с графами

     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. Заключение

    Хотя  поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков.

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