зважені графи
зважені графи
У класичних графах все ребра вважаються рівноцінними і довжина шляху відповідає кількості ребер, які він містить. Однак часто в завданню кожному ребру відповідає деякий параметр - довжина ребра або вартість проходження по ньому. У термінології графів такий параметр називається вагою ребра, а граф, що містить зважені ребра, виваженим.
Типова задача для таких графів - пошук найкоротшого шляху. Наприклад, в цьому графі найкоротший шлях між вершинами $ 1 $ і $ 5 $: $ 1 - 4 - 3 - 5 $, так як його вага дорівнює $ 30 + 20 + 10 = 60 $, а вага ребра $ 1 - 5 $ дорівнює $ 100 $.
алгоритм Дейкстри
Принцип роботи алгоритму нагадує принцип роботи BFS: на кожному кроці обробляється найближча ще не оброблена вершина (відстань до неї вже відомо). При її обробці все ще не відвідані сусіди додаються в чергу для відвідування (відстань до кожної з них розраховується як відстань до поточної вершини + довжина ребра). Головна відмінність від BFS полягає в тому, що замість класичної черзі використовується чергу з пріоритетом. Вона дозволяє нам вибирати найближчу вершину за $ O (\ log N) $.
Анімація виконання алгоритму Дейкстри для пошуку найкоротшого шляху з вершини $ a $ в вершину $ b $:
За допомогою псевдокоду алгоритм Дейкстри описується наступним чином:
Як бачите, в черзі з пріоритетом зберігається не тільки номер вершини, а й обчислене відстань до неї, за яким і ведеться сортування. Також можлива ситуація, при якій одна і та ж вершина буде поміщена в чергу кілька разів з різною відстанню (так як вона досяжна за кількома ребрах). У такій ситуації обробляємо її тільки один раз (з мінімальним можливим відстанню).
Реалізація
В нашій черзі з пріоритетом повинні зберігатися пари (вершина, відстань до неї), причому відсортовані вони повинні бути по зменшенню відстані. Для цього потрібно використовувати тип std :: priority_queue
Для зберігання зваженого графа у вигляді списку суміжності для кожної вершини ми зберігаємо вектор пар (сусідня вершина, довжина ребра до неї).
Реалізація на C ++:
Реалізація з відновленням шляху
Відновлення шляху для алгоритму Дейкстри реалізується точно так же, як і для BFS: при успішному поліпшенні шляху в вершину $ u $ через вершину $ v $, ми запам'ятовуємо, що $ prev [v] = u $. Після закінчення роботи алгоритму використовуємо масив $ prev $ для відновлення шляху в зворотному напрямку.
Реалізація на C ++:
Область застосування алгоритму Дейкстри
Алгоритм Дейкстри є оптимальним для пошуку шляху практично в будь-яких графах, але він має одне обмеження. Алгоритм Дейкстри непридатний для графів, що містять ребра з негативним вагою. Для пошуку найкоротшого шляху в таких графах зазвичай використовують алгоритм Форда-Беллмана.