Алгоритм левита - це

формулювання завдання

Варіант 1. Дана мережа автомобільних доріг, що з'єднують міста Московської області. Деякі дороги односторонні. Знайти найкоротші шляхи від міста Москва до кожного міста області (якщо рухатися можна тільки по дорогах).

Варіант 2. Є деяка кількість авіарейсів між містами світу, для кожного відома вартість. Вартість перельоту з A в B може бути не дорівнює вартості перельоту з B в A. Знайти маршрут мінімальної вартості (можливо, з пересадками) від Копенгагена до Барнаула.

формальне визначення

Дан зважений орієнтований [1] граф без петель і дуг негативного ваги [2]. Знайти найкоротші шляхи від деякої вершини графа до всіх інших вершин цього графа.

позначення

  • - безліч вершин графа
  • - безліч ребер графа
  • - вага (довжина) ребра
  • - вершина, відстані від якої шукаються, тобто стартова вершина.
  • - це поточна довжина найкоротшого шляху від вершини до вершини
  • - це вершина, що передує вершині в найкоротшому шляху від вершини до.
  • - вершини, відстань до яких вже обчислено (але, можливо, не остаточно);
  • - вершини, відстань до яких обчислюється;
  • - вершини, відстань до яких ще не обчислено.
  • - зберігає номер безлічі, до якого належить вершина i.

typedef pair rib; typedef vector > Graph;

const int inf = 1000 * 1000 * 1000;

Нехай масив D [1..N] буде містити поточні найкоротші довжини шляхів. Спочатку масив D заповнений значеннями "нескінченність", крім D [s] = 0. Після закінчення роботи алгоритму цей масив буде містити остаточні найкоротші відстані.

Нехай масив P [1..N] містить поточних предків. Так само як і масив D, масив P змінюється поступово по ходу алгоритму і до кінця його приймає остаточні значення.

Спочатку все вершини поміщаються в безліч M2, крім вершини V0, яка поміщається в безліч M1.

На кожному кроці алгоритму ми беремо вершину з безлічі M1 (дістаємо верхній елемент з черги). Нехай V - це обрана вершина. Переводимо цю вершину в безліч M0. Потім переглядаємо всі ребра, що виходять з цієї вершини. Нехай T - це другий кінець поточного ребра (тобто не рівний V), а L - це довжина поточного ребра.

  • Якщо T належить M2, то T переносимо в безліч M1 в кінець черги. DT вважаємо рівним DV + L.
  • Якщо T належить M1, то намагаємося поліпшити значення DT: DT = min (DT, DV + L). Сама вершина T ніяк не пересувається в черзі.
  • Якщо T належить M0, і якщо DT можна поліпшити (DT> DV + L), то покращуємо DT, а вершину T повертаємо в безліч M1, поміщаючи її в початок черги.

Зрозуміло, при кожному оновленні масиву D слід оновлювати і значення в масиві P.

складність алгоритму

Час роботи цього алгоритму. Однак на практиці алгоритму зарекомендував себе дуже добре: час його роботи оцінюється як (експериментальна оцінка).

Порівняння алгоритмів Дейкстри і Левіта

У порівнянні з методом Дейкстри метод Левіта програє на тому, що деякі вершини доводиться обробляти повторно, а виграє на більш простих алгоритмах включення і виключення вершин з безлічі М1. Експерименти показують, що для графів з «геометричним» походженням, тобто для графів, побудованих на основі транспортних мереж і реальних відстаней, метод Левіта виявляється найбільш швидким. Він виграє і за розміром програми.

Метод Левіта має ще й ту перевагу перед методом Дейкстри, що він застосуємо в разі негативних довжин дуг (адже «довжина дуги» - це просто назва, яке дає нам корисні асоціації з реальністю). Якщо вважати, що значення l (u) не обов'язково є позитивними, рішення задачі про найкоротший шлях значно ускладнюється.

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

Друга складність серйозніше: при негативних довжинах в графі можуть знайтися контури з негативною сумою довжин дуг (назвемо такі контури «негативними»). Додаток до шляху негативного контуру зменшує значення цільової функції, і чим більше обходів негативного контуру ми додамо, тим «краще». Позбудеться від нескінченного зменшення мінімуму просто так неможливо, але є два виходи із скрутного становища (звичайно ж, вибір виходу залежить не від нас, а від розв'язуваної практичного завдання).

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

Примітки

  1. ↑ Тут окремим випадком орієнтованого графа є неорієнтований і змішані ( «частково орієнтований») графи.
  2. ↑ Для графа з негативними вагами застосовується більш загальний алгоритм - Алгоритм Дейкстри з потенціалами

література

Схожі статті