Сайт про олімпіадному програмуванні

Графи: пошук найкоротших шляхів

У цьому розділі розглядаються зважені орієнтовані графи. Неорієнтовані графи можна розглядати як окремий випадок орієнтованих, а мультиграфом замінювати звичайними, причому мультіребра замінюються їх найдешевшим ребром.

Найкоротшим шляхом між парою вершин називається такий шлях між ними, що сума ваг ребер, що входять в даний шлях мінімальна.

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

Якщо ж найкоротший шлях існує, то існує і простий найкоротший шлях, що з'єднує дані вершини (наприклад, якщо з вихідного викинути все цикли нульової довжини).

Багато олімпіадні задачі зводяться до пошуку найкоротших шляхів. Зазвичай розглядається наступна завдання: дано граф, у якого ваги ребер - невід'ємні числа, потрібно знайти найкоротший шлях між парою вершин. Вона вирішується за допомогою алгоритму Дейкстри. Якщо граф може містити ребра негативного ваги, то застосовується алгоритм Форда-Беллмана. Він так само дозволяє визначити, чи існує в графі негативний цикл. Якщо потрібно знайти найкоротші шляхи між усіма парами вершин, то застосовується алгоритм Флойда-Уоршелла.

В даному розділі будемо вважати що якщо відстань між (u, v) = INF (нескінченність), то в графі немає шляху між (u, v). Значення константи INF має бути досить великим, але бажано вибрати її так, що, наприклад, вираз INF + INF не викликало б переповнення.

Матриця суміжності матиме такий вигляд: a_uv = 0, якщо u = v, інакше довжині ребра (u, v), якщо воно є, інакше INF.

алгоритм Дейкстри

Алгоритм Дейкстри дозволяє знайти найкоротші шляхи від даної вершини до всіх інших вершин в графі. Алгоритм складається з наступних кроків:

  1. Покласти для всіх вершин (крім вихідної) відстань dist (v) = INF, для вихідної dist (start) = 0.
  2. Вибрати Непомічені вершину v, з мінімальним відстанню. Якщо такої вершини немає, то завершити роботу.
  3. Помітити v.
  4. Для всіх непомічених вершин, суміжних з v, спробувати поліпшити оцінку відстані.
  5. Повернутися до кроку 2.

Реалізація на Java:

0000: int INF = Integer. MAX_VALUE / 2; // "Нескінченність"
0001: int vNum; // кількість вершин
0002: int [] [] graph; // матриця суміжності
0003:
0004: / * Алгоритм Дейкстри за O (V ^ 2) * /
0005: void dijkstra (int start) <
0006: boolean [] used = new boolean [vNum]; // масив позначок
0007: int [] dist = new int [vNum]; // масив відстані. dist [v] = мінімальное_расстояніе (start, v)
0008:
0009: fill (dist. INF); // устанаавліваем відстань до всіх вершин INF
0010: dist [start] = 0; // для початкової вершини покладемо 0
0011:
0012: for (;;) <
0013: int v = - 1;
0014: for (int nv = 0; nv dist [nv])) // вибираємо найближчу Непомічені вершину
0016: v = nv;
0017: if (v == - 1) break; // найближча вершина не знайдено
0018: used [v] = true; // помічаємо її
0019: for (int nv = 0; nv

Зауважимо, що наш алгоритм знайшов тільки вартості найкоротших шляхів, а не сам шлях між важливими нас вершинами. Насправді, цього часто достатньо, але якщо потрібно знайти шлях, то алгоритм Дейкстри слід модифікувати. Введемо ще одну характеристику - prev (v) = p - вершина з якої було покращено відстань до v на кроці 4 вихідного алгоритму. Фактично, якщо об'єднати всі найкоротші шляхи з вихідної вершини, то вони утворюють дерево. У будь-якої вершини дерева, крім кореня є рівно один предок. В кінці роботи алгоритму, prev (v) - і буде цим предком. Знаючи предків, можна легко відновити і сам шлях.

Нехай V - число вершин, E - число ребер графа. Зауважимо, що асимптотика нашого алгоритму O (V ^ 2). Але для виряджених графів можна модифікувати алгоритм Дейкстри. По-перше, якщо відмовитися від матриці суміжності, і перейти до списків, то релаксація зажадає тільки O (E) операцій. Для прискорення отримання найближчій вершини необхідно застосувати спеціальні структури даних (наприклад, RMQ або купу). Тоді отримаємо асимптотику O (ElogV).

Реалізація алгоритму Дейкстри з RMQ на Java:

0000: int INF = Integer. MAX_VALUE / 2; // "Нескінченність"
0001: int vNum; // кількість вершин
0002: MultiList graph; // опис графа
0003:
0004: / * Алгоритм Дейкстри за O (E log V) * /
0005: void dijkstraRMQ (int start. Int end) <
0006: boolean [] used = new boolean [vNum]; // масив позначок
0007: int [] prev = new int [vNum]; // масив предків
0008: int [] dist = new int [vNum]; // масив відстаней
0009: RMQ rmq = new RMQ (vNum); // RMQ
0010:
0011: / * Ініціалізація * /
0012: fill (prev. - 1);
0013: fill (dist. INF);
0014: rmq. set (start. dist [start] = 0);
0015:
0016: for (;;) <
0017: int v = rmq. minIndex (); // вибираємо найближчу вершину
0018: if (v == - 1 || v == end) break; // якщо вона не знайдена, або є кінцевою, то виходимо
0019:
0020: used [v] = true; // помічаємо обрану вершину
0021: rmq. set (v. INF); // і скидаємо її значення в RMQ
0022:
0023: for (int i = graph. Head [v]; i. = 0; i = graph. Next [i]) 0024: int nv = graph. vert [i];
0025: int cost = graph. cost [i];
0026: if (. Used [nv] dist [nv]> dist [v] + cost) 0027: rmq. set (nv. dist [nv] = dist [v] + cost); // покращуємо її
0028: prev [nv] = v; // помічаємо предка
0029:>
0030:>
0031:>
0032:
0033: / * Відновлення шляху * /
0034: Stack stack = new Stack ();
0035: for (int v = end; v. = - 1; v = prev [v]) <
0036: stack. push (v);
0037:>
0038: int [] sp = new int [stack. size ()];
0039: for (int i = 0; i 0; v / = 2) <
0088: int l = 2 * v;
0089: int r = l + 1;
0090: if (val [l]

Алгоритм Форда-Беллмана

Алгоритм Форда-Беллмана не надто швидкий (O (VE)), але працює і на графах з негативними ребрами. Алгоритм досить простий: покласти відстані до вихідної вершини - 0, для решти INF, а потім V - 1 раз зробити всілякі релаксації (їх буде рівно E). Можна зробити оптимізацію: якщо на поточному кроці не вдалося зробити жодної релаксації - зупинитися. Якщо після (V - 1) -ої ітерації можна виконати релаксацію, то в графі є цикл негативного ваги (його можна знайти явно, якщо зберігати предків).

0000: int INF = Integer. MAX_VALUE / 2; // "Нескінченність"
0001: int vNum; // кількість вершин
0002: MultiList graph; // опис графа
0003:
0004: / * Алгоритм Форда-Беллмана за O (VE) * /
0005: void fordBellman (int start) <
0006: int [] dist = new int [vNum]; // масив відстаней
0007: fill (dist. INF); //
0008: dist [start] = 0; // Ініціалізація
0009: for (int it = 1; it

Алгоритм Флойда-Уоршелла

Даний алгоритм знаходить кратайшіе відстані між усіма парами вершин за O (V ^ 3). Опис алгоритму: фіксуємо вершину k, потім перебираємо всілякі пари вершин (i, j) і якщо a_ij> a_ik + a_kj, то робимо a_ij = a_ik + a_kj.

0000: int INF = Integer. MAX_VALUE / 2; // "Нескінченність"
0001: int vNum; // кількість вершин
0002: int [] [] graph; // матриця суміжності
0003:
0004: / * Алгоритм Флойда-Уоршелла за O (V ^ 3) * /
0005: void floydWarshall () <
0006: int [] [] dist = new int [vNum] [vNum]; // dist [i] [j] = мінімальное_расстояніе (i, j)
0007: for (int i = 0; i