ю станції між лініями з номерами i і j . Уявімо цей граф з допомогу масиву множин (змінна ss в програмі), в i -м елементі цього масиву міститься безліч всіх ліній, на які можна потрапити з лінії i за одну пересадку. Результат будемо отримувати за допомогою безлічі s, на кожному кроці алгоритму містить номери всіх ліній, на які можна потрапити з вихідної лінії m за k пересадок. Зауважимо, що якщо вершина n нашого графа досяжна з вершини m (кажуть, що вони знаходяться в одній компоненті зв'язності ), то шукане число пересадок менше загальної кількості ліній nn . Бо навіть якщо після кожної з перших nn - 1 пересадок ми потрапляли на нову лінію, то після наступного пересадки ми обов'язково опинимося на якийсь з ліній повторно, адже їх всього nn . Тому, якщо наш алгоритм не завершився за nn - 1 крок, то граф НЕ пов'язаний і подальший пошук шляху марний (зауважимо, що наявність шляху між двома конкретними вершини не доводить його зв'язність, а досліджувати всі пари вершин за допомогою запропонованого алгоритму для аналізу зв'язності неефективно).
Програма для вирішення завдання представлена ​​нижче.
const nn = 200; {число ліній}
type myset = set of 0 .. nn; var i, m, n, k: byte; ss: array [1 .. nn] of myset; s, s1: myset; begin
... {зчитуємо вхідні дані}
s: = [m]; k: = 0; while not (n in s) and (k
s1: = s; s: = []; for i: = 1 to nn do if i in s1 then
{додаємо до s вершини,
досяжні з i} s: = s + ss [i] end; if n in s then writeln (k) else
writeln ('it is impossible')
end.
Зауважимо, що запропонований при вирішенні задачі 12 алгоритм можна модифікувати так, щоб він знаходив довжину найкоротшого шляху від вихідної вершини до всіх інших вершин графа, причому асимптотическое час його роботи не зміниться. Незважаючи на гарні тимчасові характеристики, область застосування алгоритму обмежена розміром типу "безліч" в Паскалі. Уникнути цього обмеження можна, використовуючи такий спосіб представлення графа як масив списків вершин, суміжних з даною. Про способи реалізації динамічних структур даних, і зокрема списків, див., наприклад, [8].
Нехай тепер потрібно визначити наявність шляху відразу для всіх пар вершин графа. Таке завдання для незваженого графа називається транзитивним замиканням . Розглянемо її рішення на прикладі наступної проблеми. h6> Задача 13. Нехай для деяких пар змінних відомо, що значення однієї з них не більше значення іншої. Виписати інші пари зі згаданих змінних, для яких, використовуючи транзитивність операції "ВЈ", можна також сказати, значення однієї з них не перевершує значення іншої.
Рішення . Позначимо даними змінними вершини графа, а знання про наявність між двома змінними відносини "ВЈ" - орієнтованими ребрами. Для деякої пари вершин справедливо, що значення однієї ВЈ значення інше, якщо в побудованому орієнтованому графі існує шлях з першої зі згаданих вершин в другу. Тоді для вирішення завдання можна скористатися наступним алгоритмом Уоршолла [5, 6]. Нехай A - матриця, спочатку рівна матриці суміжності графа, записаної за допомогою логічних констант true і false . На k -му кроці алгоритму значення true в елементі матриці A [ i , j ] означатиме, що з вершини i у вершину j Cуществует шлях, який проходить через деякі вершини з номерами, що не переважаючими k - 1. Якщо ж через згадані вершини шляху немає ( A [ i , j ] = false ), але існує шлях з вершини i у вершину k і шлях з вершини k у вершину j то значення даного елемента матриці стає true . Покажемо як написати фрагмент програми, реалізує цей алгоритм без використання умовних операторів:
c: = a; {запам'ятовуємо матрицю суміжності}
for k: = 1 to nn do
for i: = 1 to nn do
for j: = 1 to nn do
a [i, j]: = a [i, j] or a [i, k] and a [k, j];
Стислість говорить тут сама за себе. В результаті виконання трьох вкладених циклів (то Тобто ми маємо алгоритм, що працює за N 3 операцій), порядок яких дуже важливий, в матриці a ми фактично отримаємо відповідь на питання завдання. Роздрукувати його можна так:
for i: = 1 to nn do
for j: = 1 to nn do
if a [i, j] xor c [i, j] then writeln (i, '', j);
Якщо ж потрібно знайти довжини найкоротших шляхів для всіх пар вершин, то, якщо кожному ребру графа приписати вага, рівний одиниці, вирішення завдання буде повністю збігатися з рішенням тієї ж задачі для виваженого графа (див. далі). Тому окремо ми розглядати його не будемо.
В
4. Шляхи мінімальної д...
