Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах

Спецификация выходных данных.

Выходные данные должны быть записаны в текстовый файл с именем PER.OUT и иметь следующий формат:

- в первой строке находится натуральное число T - время проезда по самому быстрому маршруту;

- в каждой из следующих строк находится одно число - номер очередного перекрестка в маршруте (начиная с перекрестка с номером А и кончая В).

Кратко идея решения может быть изложена следующим образом.

Алгоритм Дейкстры напрямую не применим, поскольку:

а) оптимальное решение в следующей вершине не является суммой оптимального решения для предыдущей вершины и веса текущего ребра

б) вес текущего ребра - непостоянная величина, зависящая от того, каким поворотом мы вышли из вершины.

Поэтому предлагается решение поиском в глубину. При этом разрешается использовать каждую вершину столько раз, сколько у нее есть ребер. Отсекаются решения хуже текущего оптимального.

Можно еще ускорить решение, если обеспечивать перебор, начиная с правых поворотов (отсечения работали бы более эффективно).

Замечание:

В тексте задачи явно не указано, но авторы оригинальных тестов к задаче полагали, что поворот на 180 градусов - это левый поворот (как в армии: поворот на 180 градусов - "через левое плечо").

Рассмотрим решение более подробно:

Ввод исходных данных осуществляется следующим образом:

read(N,M,K);

for i:=1 to N do readln(x[i],y[i]);

for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;

for i:=1 to M do

begin

readln(p,r,t); inc(kG[p]); inc(kG[r]);

G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);

G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);

end;

readln(vA,vB);

Здесь kG[i] - количество дуг из вершины i

G[i,j,1] - вершина, с которой соединена вершина i дугой с номером j в списке всех дуг из вершины i.

G[i,j,2] - время проезда от вершины i до вершины, с которой она соединена дугой j в списке всех дуг из вершины i.

D[i] - количество дорог, пересекающихся на перекрестке i (то есть суммарное количество дуг, исходящих из вершины i и входящик в нее),

vA и vB указывают, откуда и куда нужно добираться.