Задача пошуку найкоротшого маршруту в мережі. Алгоритм Дійкстри

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

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

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

Алгоритм Дійкстри.

Крок 1. Початкові присвоювання. Присвоїмо та для всіх . Позначимо вершину та присвоїмо , де — остання з переглянутих вершин.

Крок 2. Для кожної з непереглянутих вершин перераховуємо значення за формулою , де —довжина дуги . Якщо для всіх непереглянутих вершин , то стоп: в графі відсутні шляхи з в непереглянуті вершини, тобто шлях з в відсутній.

Крок 3. Позначаємо як переглянуту ту з непереглянутих вершин , для якої . Позначаємо дугу, що веде до обраної вершини, та присвоюємо .

Крок 4. Якщо , то стоп: найкоротший шлях з в знайдений. Перехід до кроку 2.

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

Приклад.

Для заданого графу знайти найкоротший шлях з вершини 0 до вершини 6.

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

2. Для кожної з непереглянутих вершин перераховуємо значення .

d(1) = min{d(1), d(0)+c(0,1)}= min{0+4}=4,

d(2) = min{d(2), d(0)+c(0,2)}= min{0+3}=3,

d(3) = min{d(3), d(0)+c(0,3)}= min{0+1}=1,

d(4) = min{d(4), d(0)+c(0,4)}= min{} = ,

d(5) = min{d(5), d(0)+c(0,5)}= min{} = ,

d(6) = min{d(6), d(0)+c(0,6)}= min{} = .

Визначаємо min{d(1), d(2),…, d(6)}=d(3)=1. Позначимо вершину 3, y=3, та дугу (0,3):

3. Оскільки умови завершення роботи алгоритму не виконані, переходимо до наступної ітерації.

d(1) = min{d(1), d(3)+c(3,1)}= min{+}=4,

d(2) = min{d(2), d(3)+c(3,2)}= min{ 3+1}=2,

d(4) = min{d(4), d(4)+c(3,4)}= min{}=,

d(5) = min{d(5), d(3)+c(3,5)}= min{1+7}=8,

d(6) = min{d(6), d(3)+c(3,6)}= min{}=.

min{d(1), d(2), d(4), d(5), d(6)}=d(2)=2. Позначаємо вершину 2, у=2 та дугу (3, 2).

4. Виконуємо наступну ітерацію.

d(1) = min{d(1), d(2)+c(2,1)}= min{2+2}=4 — залишається попереднє значення,

d(4) = min{d(4), d(2)+c(2,4)}= min{2+5}=7,

d(5) = min{d(5), d(2)+c(2,5)}= min{82+}=,

d(6) = min{d(6), d(2)+c(2,6)}= min{}=.

min{d(1), d(4), d(5), d(6)}=d(1)=4. Позначаємо вершину 1, у=1, та дугу (2,1).

5. В результаті наступної ітерації отримуємо:

d(4) = min{d(4), d(1)+c(1,4)}= min{7,4+2}=6,

d(5) = min{d(5), d(1)+c(1,5)}= min{84+4}=— залишається попереднє,

d(6) = min{d(6), d(1)+c(1,6)}= min{}=.

min{d(4), d(5), d(6)}=d(4)=6. Позначаємо вершину 4, у=4, та дугу (1,4).

6. Результат наступної ітерації:

d(5) = min{d(5),d(4)+c(4,5)}= min{86+}=,

d(6) = min{d(6), d(4)+c(4,6)}= min{6+4}=10.

min{d(5), d(6)}=d(5)=8. Позначаємо вершину 5, у=5, та дугу (3,5).

І нарешті, d(6) = min{d(6), d(5)+c(5,6)}= min{108+1}=9.

min{d(6)}=d(6)=9. Позначаємо вершину 6, у=6, та дугу (5,6).

Так як ми позначили вершину 6, то стоп. Окрім цього, більше непозначених вершин в мережі немає, тобто одночасно побудоване дерево найкоротших шляхів з вершини 0 у всі інші.

Дерево найкоротших шляхів з вершини 0:

Розглянемо приклад застосування задачі про найкоротший шлях.

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

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

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

• початок кожного року восьмирічного періоду зображатимемо вузлом мережі;

• якщо купівля комп’ютера відбувається на початку і-го року, а на початку j-го року він замінюється новим, то такому варіанту заміни відповідатиме дуга (і,j), довжина якої с_іj відображатиме загальні затрати;

• загальні затрати розраховуються за допомогою наступного співвідношення — , де — початкова вартість комп’ютера на початку і-го року; — залишкова вартість комп’ютера на початку j-го року; — експлуатаційні витрати на протязі k-го року.

Відповідна мережа зображена нижче.