Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах
end;
Приведенная теоретическая информация иллюстрируется далее примерами решения конкретных задач.
2 Задача "Дороги"
Республиканская олимпиада по информатике 1997г
Дана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении.
Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.
Входные данные задаются в файле с именем PATH.IN следующим образом. В первой строке находится натуральное N(N<=50) - количество городов (города нумеруются от 1 до N). Во второй строке находится натуральное M(M<=100) - количество дорог. Далее в каждой строке находится пара номеров городов, которые связывает дорога. В последней (M+3)-й строке находятся номера городов А, В и С.
Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен быть записан в файл PATH.OUT в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1.
Кратко идея решения может быть изложена следующим образом:
Поиск в глубину.
Если встречаем вершину B, устанавливаем соответствующий флаг.
Если встречаем вершину C и флаг B установлен - выводим результат и завершаем работу.
После завершения поиска (требуемый маршрут не найден) выводим -1.
Изложим решение более подробно.
Ввод исходных данных осуществляется следующим образом:
read(N,M);
for i:=1 to M do
begin
read(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
end;
read(A,B,C);
Здесь, как и прежде,
kG[i] - количество дуг из вершины i
G[i,j] - (для j от 1 до kG[j]) - вершины, с которыми вершина i связана соответствующей дугой
Кроме того, введен цвет дуги FREE - свободна (DONE - занята, FREE/DONE - константы)
Главная программа фактически включает только следующие операторы:
LabC:=0; { Установить метку - вершину C еще не посещали}
DFS(A); { Поиск в глубину от вершины A }
writeln(-1); { Вывод признака отсутствия требуемого пути}