Алгоритм найкоротшого шляху Дейкстри - детальний та наочний вступ

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

Ти навчишся:

  • Основні концепції графіків (короткий огляд).
  • Для чого використовується Алгоритм Дейкстри.
  • Як це працює за кадром на покроковому прикладі.

Давайте почнемо. ✨

Вступ до графіків

Почнемо з короткого вступу до графіків.

Основні поняття

Графіки - це структури даних, що використовуються для представлення «зв’язків» між парами елементів.

  • Ці елементи називаються вузлами . Вони представляють реальні об'єкти, людей або сутності.
  • Зв'язки між вузлами називаються ребрами .

Це графічне зображення графіка:

Вузли представлені кольоровими колами, а ребра - лініями, що з’єднують ці кола.

💡 Порада. Два вузли з'єднані, якщо між ними є ребро.

Програми

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

Типи графіків

Графіки можуть бути:

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

💡 Порада: у цій статті ми будемо працювати з неорієнтованими графіками.

Зважені графіки

Ваги графіки являють собою графік, ребро якого має «вагу» або «вартість». Вага ребра може представляти відстань, час або що-небудь, що моделює "зв'язок" між парою вузлів, які він з'єднує.

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

💡 Порада: Ці ваги є важливими для алгоритму Дейкстри. Ви зрозумієте, чому саме за мить.

🔸 Вступ до алгоритму Дейкстри

Тепер, коли ви знаєте основні поняття графіків, давайте почнемо занурюватися в цей дивовижний алгоритм.

  • Призначення та використання справ
  • Історія
  • Основи алгоритму
  • Вимоги

Призначення та використання справ

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

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

Історія

Цей алгоритм був створений та опублікований доктором Едсгером В. Дейкстра, блискучим голландським вченим-інформатиком та інженером-програмістом.

У 1959 році він опублікував 3-сторінкову статтю під назвою "Примітка про дві проблеми у зв'язку з графіками", де він пояснив свій новий алгоритм.

Під час інтерв’ю в 2001 році доктор Дейкстра розповів, як і чому він розробив алгоритм:

Який найкоротший спосіб подорожі з Роттердама до Гронінгена? Це алгоритм найкоротшого шляху, який я розробив приблизно за 20 хвилин. Одного ранку я ходив по магазинах в Амстердамі зі своєю молодою нареченою, і втомившись, ми сіли на терасу кафе випити чашку кави, і я просто думав, чи можу я це зробити, і тоді я розробив алгоритм найкоротшого шляху . Як я вже говорив, це був 20-хвилинний винахід. Насправді він був опублікований у 1959 році, через три роки. Публікація все ще досить приємна. Однією з причин того, що він такий приємний, було те, що я створив його без олівця та паперу. Без олівця та паперу ви майже змушені уникати всіх складних ситуацій, яких можна уникнути. Зрештою цей алгоритм став, на моє велике подив, одним із наріжних каменів моєї слави. - Як цитується у статті Edsger W.Дейкстра з інтерв'ю з Едджером В. Дейкстрою.

Неймовірно, так? Всього за 20 хвилин доктор Дейкстра розробив один із найвідоміших алгоритмів в історії комп’ютерних наук.

Основи алгоритму Дейкстри

  • Алгоритм Дейкстри в основному починається з вибраного вами вузла (вихідний вузол), і він аналізує графік, щоб знайти найкоротший шлях між цим вузлом та всіма іншими вузлами на графіку.
  • Алгоритм відстежує відому в даний час найкоротшу відстань від кожного вузла до вихідного вузла і оновлює ці значення, якщо знаходить коротший шлях.
  • Як тільки алгоритм знайде найкоротший шлях між вузлом-джерелом та іншим вузлом, цей вузол позначається як "відвіданий" та додається до шляху.
  • Процес триває до тих пір, поки всі вузли на графіку не будуть додані до шляху. Таким чином, у нас є шлях, який зв’язує вихідний вузол з усіма іншими вузлами, слідуючи найкоротшому шляху, який можливий для досягнення кожного вузла.

Вимоги

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

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

🔹 Приклад алгоритму Дейкстри

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

У нас є такий графік:

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

Порада. Для цього графіка ми будемо вважати, що вага ребер представляє відстань між двома вузлами.

У нас буде найкоротший шлях від вузла 0до вузла 1, від вузла 0до вузла 2, від вузла 0до вузла 3і так далі для кожного вузла на графіку.

Спочатку у нас є цей список відстаней (див. Список нижче):

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

У нас також є цей список (див. Нижче) для відстеження вузлів, які ще не були відвідані (вузли, які не були включені в шлях):

💡 Порада. Пам’ятайте, що алгоритм завершено, як тільки всі вузли будуть додані до шляху.

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

Тепер нам потрібно розпочати перевірку відстані від вузла 0до сусідніх вузлів. Як бачите, це вузли 1та 2(див. Червоні краї):

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

Нам потрібно оновити відстані від вузла 0до вузла 1та вузла 2з вагами ребер, які з’єднують їх із вузлом 0(вихідним вузлом). Ці ваги складають відповідно 2 та 6:

Після оновлення відстаней сусідніх вузлів нам потрібно:

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

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

На діаграмі ми можемо представити це червоним краєм:

Ми позначаємо це червоним квадратиком у списку, щоб показати, що його "відвідали" і що ми знайшли найкоротший шлях до цього вузла:

Ми викреслюємо це зі списку невідвіданих вузлів:

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

Вузол 3та вузол 2сусідять із вузлами, які вже є у шляху, оскільки вони безпосередньо підключені до вузла 0та вузла 1, як ви можете бачити нижче. Це вузли, які ми проаналізуємо на наступному кроці.

Оскільки 2в нашому списку вже записана відстань від вихідного вузла до вузла, цього разу нам не потрібно оновлювати відстань. Нам потрібно лише оновити відстань від вихідного вузла до нового сусіднього вузла (вузла 3):

Ця відстань 7 . Подивимось чому.

Щоб знайти відстань від вихідного вузла до іншого вузла (у цьому випадку - вузла 3), ми додаємо ваги всіх ребер, які утворюють найкоротший шлях до цього вузла:

  • Для вузла 3: загальна відстань 7, оскільки ми додаємо ваги ребер, що утворюють контур 0 -> 1 -> 3(2 для ребра 0 -> 1і 5 для ребра 1 -> 3).

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

Зі списку відстаней ми можемо відразу виявити, що це вузол 2з відстанню 6 :

Ми додаємо його до шляху графічно з червоною рамкою навколо вузла та червоним краєм:

Ми також відзначаємо його як відвідане, додаючи невеликий червоний квадрат у список відстаней і викреслюючи його зі списку невідвіданих вузлів:

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

Ви бачите, що у нас є два можливі шляхи 0 -> 1 -> 3або 0 -> 2 -> 3. Давайте подивимося, як ми можемо вирішити, який із них є найкоротшим шляхом.

Вузол 3вже має відстань у списку, який був записаний раніше ( 7, див. Список нижче). Ця відстань була результатом попереднього кроку, де ми додали ваги 5 і 2 двох ребер, які нам потрібно було перетнути, щоб пройти шлях 0 -> 1 -> 3.

Але зараз у нас є інша альтернатива. Якщо ми вирішили йти шляхом 0 -> 2 -> 3, ми повинні слідувати два ребра 0 -> 2і 2 -> 3з вагами 6 і 8 ,відповідно,що представляє загальну відстань 14 .

Очевидно, що перша (існуюча) відстань коротша (7 проти 14), тому ми вирішимо зберегти початковий шлях 0 -> 1 -> 3. Ми оновлюємо відстань, лише якщо новий шлях коротший.

Таким чином, ми додамо цей вузол до шляху , використовуючи перший варіант: 0 -> 1 -> 3.

Ми позначаємо цей вузол як відвіданий і викреслюємо його зі списку невідвіданих вузлів:

Тепер ми повторюємо процес знову.

Нам потрібно перевірити нові сусідні вузли, які ми досі не відвідували. Цього разу ці вузли є вузлом 4і вузлом, 5оскільки вони сусідять з вузлом 3.

Ми оновлюємо відстані цих вузлів до вихідного вузла, завжди намагаючись знайти коротший шлях, якщо це можливо:

  • Для вузла 4: відстань становить 17 від шляху   0 -> 1 -> 3 -> 4.
  • Для вузла 5: відстань становить 22 від шляху 0 -> 1 -> 3 -> 5.

Порада. Зверніть увагу, що ми можемо розглянути лише можливість продовження найкоротшого шляху (позначеного червоним). Ми не можемо розглянути шляхи, які проведуть нас через ребра, які не були додані до найкоротшого шляху (наприклад, ми не можемо сформувати шлях, який проходить через край 2 -> 3).

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

Ми також позначаємо його як "відвіданий", додавши в список невеликий червоний квадрат:

І ми викреслюємо це зі списку невідвіданих вузлів:

І ми повторюємо процес знову. Перевіряємо сусідні вузли: вузол 5і вузол 6. Нам потрібно проаналізувати кожен можливий шлях, яким ми можемо пройти, щоб дістатися до них із вузлів, які вже були позначені як відвідані та додані до шляху.

Для вузла 5:

  • Перший варіант - пройти шлях 0 -> 1 -> 3 -> 5, який має відстань 22 від вихідного вузла (2 + 5 + 15). Ця відстань вже була записана у списку відстаней на попередньому кроці.
  • Другим варіантом було б пройти шлях 0 -> 1 -> 3 -> 4 -> 5, який має відстань 23 від вихідного вузла (2 + 5 + 10 + 6).

Очевидно, що перший шлях коротший, тому ми вибираємо його для вузла 5.

Для вузла 6:

  • Доступний шлях 0 -> 1 -> 3 -> 4 -> 6, який має відстань 19 від вихідного вузла (2 + 5 + 10 + 2).

Ми позначаємо вузол найкоротшою (відомою на даний момент) відстанню як відвідану. У цьому випадку вузол 6.

І ми викреслюємо це зі списку невідвіданих вузлів:

Тепер у нас є такий шлях (позначений червоним):

Лише один вузол ще не відвідано, вузол 5. Давайте подивимося, як ми можемо включити його в шлях.

Існує три різні шляхи, якими ми можемо пройти до вузла 5з вузлів, які були додані до шляху:

  • Варіант 1:0 -> 1 -> 3 -> 5 з відстанню 22 (2 + 5 + 15).
  • Варіант 2:0 -> 1 -> 3 -> 4 -> 5 з відстанню 23 (2 + 5 + 10 + 6).
  • Варіант 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 з відстанню 25 (2 + 5 + 10 + 2 + 6).

Вибираємо найкоротший шлях: 0 -> 1 -> 3 -> 5з відстанню 22 .

Ми позначаємо вузол як відвіданий і викреслюємо його зі списку невідвіданих вузлів:

І вуаля! Ми маємо остаточний результат із найкоротшим шляхом від вузла 0до кожного вузла на графіку.

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

Наприклад, якщо ви хочете дістатися до вузла, 6починаючи з вузла 0, вам просто потрібно слідувати червоним краям, і ви 0 -> 1 -> 3 -> 4 - > 6автоматично пройдете найкоротший шлях .

Коротко

  • Графіки використовуються для моделювання зв’язків між об’єктами, людьми чи сутностями. Вони мають два основних елементи: вузли та ребра. Вузли представляють об'єкти, а ребра - зв'язки між цими об'єктами.
  • Алгоритм Дейкстри знаходить найкоротший шлях між даним вузлом (який називається "вузлом джерела") та всіма іншими вузлами в графі.
  • Цей алгоритм використовує ваги ребер, щоб знайти шлях, який мінімізує загальну відстань (вагу) між вихідним вузлом та всіма іншими вузлами.

Дуже сподіваюся, вам сподобалась моя стаття і вона вам допомогла. Тепер ви знаєте, як працює Алгоритм Дейкстри за лаштунками. Слідуйте за мною у Twitter @EstefaniaCassN та переглядайте мої онлайн-курси.