Постановка задачи. Вывод пути

Дан ориентированный граф G=< V, E>,

веса дуг — A[i, j] (i, j=l..N, где N — количество вершин графа), начальная и ко­нечная вершины — s, t V. Веса дуг записаны в матрице смеж­ности А, если вершины i и j не связаны дугой, то A[i,, j]= . Путь между s и t оценивается Необходимо найти путь с минима­льной оценкой.

Пример. Кратчайший путь из 1 в 4 проходит через 3-ю и 2-ю вершины и имеет оценку 6 (см. рис 4.23)

Особый случай — контуры с отри­цательной оценкой.

Пример. При s=l и t=5, обходя контур 3" 4" 2" 3 (см. рис. 4.) достаточное число раз, можно сделать так, что оценка пути между вершинами 1 и 5 будет меньше любого целого числа. Оценку пути на­зовем его весом или длиной. Будем рассматривать только графы без кон­туров отрицательного веса.

 

рис.4

Необходимо найти кратчайший путь, т. е. путь с мини­мальным весом, между двумя вершинами графа. Эта задача разбивается на две подзадачи: сам путь и значение минималь­ного веса.

Обозначим ее через D[s, t]. Неизвестны алгоритмы, определяющие только D[s, t], все они определяют оценки от вершины s до всех остальных вершин графа. Определим D как Array[1..N] Of Integer. Предположим, что мы определили зна­чения элементов массива D — решили вторую подзадачу. Опре­делим сам кратчайший путь. Для s и t существует такая вер­шина v, что D[t]=D[v]+A[v, t]. Запомним v (например, в стеке). Повторим процесс поиска вершины и, такой, что D[v]=D[u]+А[u, v], и так до тех пор, пока не дойдем до верши­ны с номером s. Последовательность t, v, u,...., s дает кратчай­ший путь.

 

Procedure Way(s, t: Integer);

{*D, A - глобальные

структуры данных. St - локальная структура данных для хранения номеров вершин. *)

Var v, u: Integer;

Procedure Print; {*Выводит содержимое St.*}

Begin

…

End

Begin

< почистить St>;

< Занести вершину с номером t в St>; v: =t;

While v< > s Do

Begin u: =< номер вершины, для которой

D[v] =D[u] +A[u, v]>;

< занести вершину с номером v в St>;

V: =u;

End;

End;

 

Итак, путь при известном D находить мы умеем. Осталось научиться определять значения кратчайших путей, т. е. эле­менты массива D. Идея всех известных алгоритмов заключает­ся в следующем. По данной матрице весов А вычисляются пер­воначальные верхние оценки. А затем пытаются их улучшить до тех пор, пока это возможно. Поиск улучшения, например для D[v], заключается в нахождении вершин и, таких, что D[u]+A[u, v]< D[v]. Если такая вершина u есть, то значение D[v] можно заменить на D[u]+A[u, v].