В тази публикация в блога ще обясним принципите, примерите и реалните приложения на алгоритъма на Дейкстра по лесен за разбиране начин.

Въведение

Спомнете си приказката „Хензел и Гретел“. Когато мащехата им изоставя децата в гората, първият им опит – пускане на камъчета, за да маркират пътя им – се проваля, а вторият им опит – оставяне на галета – не завършва с неуспех, защото птиците ги изяждат. Ако тогава са съществували приложения за навигация или картографиране за смартфони, братята и сестрите нямаше да се изгубят и планът на мащехата им щеше да се провали. Както показва този пример, проблемът с „намирането на най-бързия маршрут от начална точка до дестинация“ остава ключова тема през цялата история, от древните приказки до днешните технологии.

Графики и основни понятия

За да разберем алгоритъма на Дейкстра, първо трябва да дефинираме какво означава „граф“ в контекста на компютърните науки. Тук графът не е функционален график, нарисуван върху равнина, а по-скоро структура от данни, състояща се от набор от върхове и свързващите ги ръбове. Например, ако си представим върховете като метростанции или автобусни спирки, ръбовете стават железопътни линии или пътища, свързващи тези върхове.
Ръбовете могат да имат присвоени тегла; тези стойности представляват измерими разходи, като например разстоянието или времето, необходимо за пътуване между два върха. Освен това, ако ръбовете имат посоки, графът става „насочен граф“, където движението е разрешено само по посока на стрелката. Алгоритъмът на Дейкстра изчислява най-късото разстояние и път от определена начална точка до всеки друг връх в такъв граф.

Как работи алгоритъмът на Дейкстра

Нека обясним алгоритъма, използвайки общ пример. Началната стойност на началния връх е зададена на 0, докато началните стойности на всички останали върхове са зададени на безкрайност (∞), което означава, че все още няма информация за връзката. Тези стойности представляват „най-краткото известно досега разстояние (или време) за достигане на този връх от началната точка“.
В първата стъпка (Стъпка 1), започваме с начален връх, зададен на 0. Във втората стъпка (Стъпка 2), за всички съседни върхове, директно достижими от началния връх, записваме временна стойност за всеки от тях, като добавяме стойността на началния връх (0) към теглото на съответното ребро. В примера тези стойности са записани като 8, 9 и 11. В този момент обработката на началния връх е завършена.
„Обработен връх“ се отнася до връх, за който не може да се намери по-къс път, което означава, че е определено окончателното му най-късо разстояние. В алгоритъма на Дейкстра, след като най-късото разстояние до даден връх бъде определено по този начин, този връх се маркира като обработен и стойността му никога повече не се променя.
В третата стъпка (Стъпка 3) избираме върха с най-малката стойност сред временните стойности, записани досега. В примера е избран върхът със стойност 8. Започвайки от този връх, разстоянията от началната точка до този връх се използват за актуализиране на стойностите на околните върхове. Чрез този процес се извършват актуализации – например, новите кандидат-разстояния за някои съседни върхове се изчисляват като 18. След като обработката на този връх приключи, той също се маркира като обработен.
В четвъртата стъпка (Стъпка 4) обработваме върха със следващата най-малка стойност – в този пример, този със стойност 9. И за този връх изчисляваме разстоянията между кандидатите за съседните му върхове по същия начин. По време на този процес могат да се появят нови стойности на кандидатите (напр. 15, 10, 12) за върхове, на които вече са зададени стойности. Ако нова стойност е по-малка от съществуващата, тя презаписва съществуващата стойност; в противен случай се запазва оригиналната стойност. Тази операция се нарича „релаксация на ръба“ и е необходима процедура, защото винаги търсим най-краткия път.
Започвайки от петата стъпка (Стъпка 5), същият метод се повтаря. Всеки път се избира върхът с най-малката временна стойност сред тези, които все още не са обработени, и временните стойности на съседните му върхове се актуализират чрез релаксацията им през съседните ръбове. Чрез повтаряне на този процес, докато всички върхове бъдат обработени, можем да определим най-късите разстояния от началната точка до всеки връх, както и най-късите пътища.

Примерно приложение: Мрежи и рутери

Компютърните мрежи са отличен пример за област, в която алгоритъмът на Дейкстра се използва широко на практика. Тъй като би било неефективно милиарди устройства да бъдат директно свързани към една мрежа – както е в случая с интернет – устройствата в непосредствена близост едно до друго образуват локални мрежи, които след това се свързват с мрежи от по-високо ниво в йерархична структура. В такава сложна структура на свързване има безброй пътища от едно устройство до друго.
В една мрежа всеки възел (като рутер) трябва да оцени пътищата въз основа на определени разходи (честотна лента, латентност и др.) и да намери „най-бързия“ или „най-евтиния“ път до дестинацията. Рутерите използват алгоритми за определяне на най-краткия път, като например алгоритъма на Дейкстра, за да определят оптималния път – т.е. следващия хоп – към който трябва да пренасочат трафика. Тъй като обаче условията на трафика в реално време постоянно се променят, е по-практично всеки рутер да предоставя само информация за непосредствено следващия мрежов сегмент – вместо рутер да обявява фиксиран, пълен път – и всеки рутер да актуализира тази информация в движение, докато пътят се изгражда.

Заключение: Поуки от търсенето на път

Дотук разгледахме основните концепции на алгоритъма на Дейкстра, неговото действие стъпка по стъпка и как се прилага в мрежи. Ако Хензел и Гретел искаха да избегнат загубата в гората, щяха да се нуждаят от по-надежден метод за навигация от прости маркери. Всъщност, алгоритми като този на Дейкстра играят подобна роля, когато навигираме или предаваме данни. Надявам се, че ще запомните идеите, залегнали в алгоритъма на Дейкстра, за да не се обърквате, когато пътувате по непознат път, и да можете да намирате ефективни маршрути дори в сложни мрежи.