Задача 23.
Задано N городов c номерами от 1 до N и сеть из M дорог с односторонним движением между ними. Каждая дорога задается тройкой (i, j, k), где i - номер города, в котором дорога начинается, j -
номер города, в котором дорога заканчивается, а k - ее длина (число k - натуральное). Дороги друг с другом могут пересекаться только в концевых городах.
Все пути между двумя указанными городами A и B можно упорядочить в список по неубыванию их длин (если есть несколько путей одинаковой длины, то выбираем один из них). Необходимо найти один из путей, который может быть вторым в списке.
Вывести его длину L и города, через которые он проходит.
ВВОД:
<Количество городов N:> N <Количество дорог M:> M
<Начало, конец и длина дороги 1:> i1, j1, k1
......
<Начало, конец и длина дороги M:> iM, jM, kM
<Города A и B, между которыми надо найти путь:> A, B
ВЫВОД:
<Пути нет>
или
<Путь проходит по городам> A, i1, i2, ..., B
<Длина пути> L
|
Решение задачи 23.
Алгоритм нахождения второго минимального расстояния между двумя вершинами:
По алгоритму Дейкстры находим кратчайший путь между начальной вершиной N и конечной K, состоящий из дуг a1, ..., as. Во втором по длине кратчайшем пути из N в K не будет по крайней мере одного из ребер ai. Поэтому алгоритм нахождения этого второго пути будет следующим:
Для i от 1 до s повторять
удалить из графа ребро (дорогу) ai;
найти кратчайший путь из N в K в новом графе;
если его длина меньше рекордной минимальной длины, полученной ранее,
то запомнить текущий путь и его длину как рекорд;
восстановить в графе ребро (дорогу) ai;
конец_для;
Этот алгоритм можно найти в книге Кристофидеса "Теория графов. Алгоритмический подход". Но в нем не рассматривается следующий случай:
Кратчайший путь -- ABC, второй -- ABDEBC.
Для того, чтобы его обработать, достаточно найти кратчайший нетривиальный путь из каждой вершины в нее же. Для этого в алгоритме Дейкстры достаточно на нулевом шаге не выставлять пометку "Просмотрено" на начальной вершине.
|
