день 2

Запускаємо алгоритм Дейкстри від стартової вершини. Можна за O (N 2). можна за O (Mlog (n)). Для перевірки існування заповнюємо спочатку масив відстаней деякої великий константою = INF.

Відстань між вершинами

Тут вже доведеться чесно писати Дейкстрой з купою або сетом. Також заведемо масив предків для відновлення шляху parent [v]. в якому буде зберігається предок вершини v, з якого ми прийшли в цю вершину. Оновлюємо parent [v] в двох випадку, коли перший раз прийшли в v або ж отримали відстань меншу, ніж distance [v]. Якщо шлях існує, то шлях, як раз, відновимо за допомогою масиву предків, починаючи з кінцевої вершини, піднімаючись по предкам, поки не дійдемо до стартової. Також варто відзначити, що тут обов'язково потрібно писати алгоритм Дейкстри на списках суміжності.

Запустимо алгоритм Форда-Беллмана. Перевірка на неіснування шляху робиться стандартно - якщо після n ітерацій dist [u] = INF (який ви задали спочатку), то шляху з s в u не існує. Зауважимо, що нескінченно-короткий шлях може бути тільки в разі існування циклу негативного ваги, але це ще не все. Крім того, що такий цикл повинен існувати, він ще повинен бути досяжний з стартовою вершини, а також з цього циклу повинна бути досяжна кінцева вершина. За допомогою Форд-Беллмана знаходимо по одній вершини з кожного циклу. Заведемо, наприклад, два булевих масиву path [] і pathrev []. де path [v] = true. якщо ми можемо з стартовою вершини дістатися до v. pathrev [v] = true. якщо ми можемо добрати від вершини v до вершини u. Перший масив заповнюється за допомогою пошуку в глибину на вихідному графі, а pathrev [] на транспоновану. Тепер, якщо існує вершина v. яка належить якому-небудь негативного циклу, а також для неї вірно, що path [v] · pathrev [v] = true. то відповідь буде '-', інакше відстань, знайдене алгоритмом Форда-Беллмана.

Стандартний алгоритм Флойда, розібраний на вчорашній лекції.

Аналогічне завдання завданню "Найкоротший шлях", але тут потрібно зробити трюк, т.к нам потрібно знайти не самий короткі, а найдовший шлях, то потрібно змінити все ваги ребер на протилежні - помножити на -1.

Стандартний bfs на одиничному графі, нічого особливого, розібраний на вчорашній лекції.

Найкоротший шлях коня Уявімо шахові клітини як вершини графа. Дві вершини A. B будуть пов'язані між собою, якщо кінь може перейти з A в B. Кожне таке ребро матиме одиничний вага. Залишилося запустити пошук в ширину, а потім відновити шлях.

Найкоротший шлях двох коней

Граф такий же як і в попередньому завданні. Тепер в черзі (векторі) будемо зберігати не тільки координати одного коня, а відразу координати двох коней, плюс до всього нам потрібно запам'ятовувати, хто з коней зараз робить наступний хід. Спочатку покладемо в чергу стартові координати двох коней, а також деякі прапор, що відповідає тому, що ходить перший кінь (за умовою). Заведемо масив used [], де used [x1] [y1] [x2] [y2] = true. якщо раніше вже існувало положення двох коней, в якому перший кінь стоїть в (x1; y1). а другий в (x2; y2). Черговий крок пошуку в ширину полягатиме в наступному: ми з черги (вектора) дістаємо чергову пару координат, якщо used від даного стану дорівнює true, то справах continue, інакше дивимося на те, який з коней зараз ходить і намагаємося перейти у відповідний стан, тобто ми маємо на увазі, що коні ходять по черзі - дістали пару координат, подивилися на те, чий зараз хід і змінили координату даного коня, якщо used від нового стану false, то поклали в чергу). Якщо в якийсь момент ми виявили, що координати обох коней збігаються з їх кінцевими призначення, то завершуємо bfs і відновлюємо предків.

Зауваження: в даній задачі краще зберігати стану не в черзі, а в векторі, і замість while робити з даного вектору простий for, так як з вектором зручніше відновлювати предків, все що буде потрібно для відновлення предків у випадку з вектором, це в кожному стані також зберігати і індекс батьківського стану в векторі.

Тут вже просто так запустити bfs не вийде, так як у нас присутні ребра, які мають вагу 0, 1, 2. Як шукається найкоротший шлях у випадку з графом 0-1, ми розібрали на лекції, але що робити з ребрами ваги 2. відповідь проста - розбити вершину на дві. Наприклад, у нас є дві вершини a і b. вага ребра мужду якими дорівнює двом. Ми заведемо фіктивну вершину c. і замінимо ребро (a. b) ваги два на два ребра (a. c) і (c. b) ваги один, так для кадого ребра ваги 2. В результаті отримаємо граф, у якого всі ребра мають вагу 0 або 1. а найкоротший шлях для такого завдання ми вже зможемо знайти через bfs. Варто не забути, коли будемо відновлювати шлях, про нашу заміну, і не виводити фіктивні вершини.

Відстань від кореня

Дане завдання є останньою по порядку, але явно не найскладнішою, молодці ті, у кого вистачило сил дочитати умови всіх задач до кінця. Рішення просте - можна запустити bfs, Форд-Беллмана, Дейкстрой, Флойда або навіть звичайний dfs, так як в завданні дано дерево. Потім знайти відстань до всіх вершин від стартової, для dfs відстань теж саме, що висота вершини в дереві.

Схожі статті