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

array(0, 7, 9, 0, 0, 14),

array(0, 0,10,15, 0, 0),

array(0, 0, 0,11, 0, 2),

array(0, 0, 0, 0, 6, 0),

array(0, 0, 0, 0, 0, 9),

array(0, 0, 0, 0, 0, 0)

);

Таким образом видно, что вес ребра, соединяющего, к примеру, 2-ю и 5-ю точки будет соответствовать значению 2-го ряда и 5-го столбца (или 5-го ряда и 2-го столбца) в матрице.

Продолжаем инициализацию: переменная $start хранит номер исходной точки (начиная с нуля), переменная $end – конечной, одномерный массив $dist – кратчайшие расстояния от исходной точки до всех остальных, а двухмерный массив $way– кратчайшие пути в графе.

Всем элементам массива $dist (кроме $dist[$start]) присваивается значение, которое будет заведомо больше длины любого пути в графе. В программе это число 1000. Элементу $dist[$start] присваивается значение 0. Также присваиваем значение первому шагу в массиве путей: $way[$start][0] = $start. Все это имеет такой вид:

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

{

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];