Използване на алгоритъма на Дейкстра за намиране на най-краткия път между два възела.
Здравейте на всички, в последната ми статия обсъдихме Графики, мощна структура от данни, която може да се използва за решаване на проблеми от реалния свят. Както споменахме, графиките се използват за моделиране на проблем под формата на върхове (или възли) и ръбове. След това можем да приложим конкретни алгоритми като Търсене първо в ширина и Търсене първо в дълбочина, за да намерим решение. Днес ще говорим за добре познатия алгоритъм на Дейкстра за намиране на най-краткия път между два възела. По-специално ще говорим за следните теми:
1. Introduction 2. Pseudocode 3. Pen and Paper Example 4. Python implementation 5. Example 6. Conclusion
Както можете да предположите, имаме много неща за покриване, така че нека започваме.
Въведение
Алгоритъмът на Dijkstra е разработен от Edsger W. Dijkstra през 1956 г. и се използва за намиране на най-краткия път между възлите в графика. Тази графика може да представлява пътната карта на град или държава или дори мрежа. Оригиналната версия на алгоритъма намира най-краткия път между два дадени възела (начален и краен възел), използвайки теглата на ръбовете между възлите. По-разпространена версия на алгоритъма се използва за намиране на най-краткия път между начален възел (възел източник) и другите възли на графиката, създавайки дървото на най-краткия път. Алгоритъмът на Дейкстра се характеризира като алчен алгоритъм, тъй като всяка стъпка намира най-доброто локално решение.Бъдете внимателни, както споменахме по-рано, алгоритъмът на Дейкстра работи с тегла, но само с положителни тегла. Графика с отрицателни тегла ще доведе до грешни резултати. Алгоритъмът на Dijkstra се използва в много приложения като протокола Open Shortest Path First (OSPF) в интернет.
Псевдокод
Алгоритъмът на Dijkstra в оригиналната си форма приема като вход графика с неотрицателни тегла, изходен възел (начална точка) и целеви възел (крайна дестинация) и връща най-краткия път и цената на този път. Алгоритъмът използва два етикета за всеки възел, за да дефинира цената от изходния възел до конкретния възел и съответно предходния възел. Псевдокодът на алгоритъма е следният:
1 function Dijkstra(Graph, source, target): 2 3 for each vertex v in Graph: 4 define the visited state FALSE 5 define the cost from the source node to infinity 6 define the previous node to None 7 if v == source: 8 define the cost from the source node to zero 9 10 while target is not visited: 11 selected_node ← vertex in Graph with min distance from 12 the source node 13 14 selected_node is characterized as visited 15 16 for each neighbor v of selected_node not visited: 17 alt ← selected_node distance from source node + 18 length(selected_node, v) 19 if alt < neighbor distance from source node: 20 neighbor distance from source node ← alt 21 neighbor previous node ← selected_node 22 calculate the path 23 return path, target node distance from start
Можем да видим, че алгоритъмът се прекратява, когато се посети целевият възел. В този момент имаме общата цена на пътя от изходния възел до целевия възел. Освен това имаме предишните възли от целевия до изходния възел. Впоследствие можем да създадем най-краткия път, следващ тези възли от край до начало, докато предишният възел на възел стане None, което се случва в изходния възел. Накрая алгоритъмът връща най-краткия път и общата цена на този път.
Пример за писалка и хартия
Преди да продължим с внедряването с помощта на Python, нека видим пример, за да разберем по-добре цялата алгоритмична процедура. Да предположим, че имаме графика, която представлява пътна карта на държава. Има шест града (върхове) в графиката и ръбове, свързващи тези градове. Графиката има следния вид:
Искаме да отидем от града V1 до V6 по най-краткия път. За да намерим този път, ще използваме алгоритъма на Дейкстра.
Стъпка 1: Инициализация
За всеки връх ние инициализираме посетения статус като False, разстоянието от изходния възел като безкрайност и предишния възел като Няма. За изходния възел разстоянието от себе си е 0.
Стъпка 2: Избран е V1
Възелът с минимално разстояние от възела източник е самият възел източник, така че избраният възел е възел V1. Ние актуализираме етикетите за съседните възли на V1 (V2 и V3). Сега графиката има следния вид:
Стъпка 3: Избран е V3 възел
Възел V3 е избран, тъй като има минималното разстояние от изходния възел. Ние актуализираме етикетите на V2, V4, V5, тъй като те са съседи на V3 и намираме по-добър път през V3. Графиката има следния вид:
Стъпка 4: Избран е възел V4
Възел V4 е избран, тъй като има минимално разстояние от изходния възел. След това актуализираме етикетите на V5 и V6. Забележете, че етикетите на V2 не са променени, защото нямаме по-добър път през V4. Впоследствие графиката има следния вид:
Стъпка 5: Избран е възел V2
Възел V2 е следващият избран възел. В този случай нито един възел не се актуализира, тъй като съседите на V2 вече са посетени. Така че графиката има следната форма:
Стъпка 6: Избран е възел V5
Възелът V5 е избран, тъй като има минимално разстояние от възела източник. След това актуализираме етикетите на възел V6 и графиката има следната форма:
Стъпка 7: Избран е възел V6
Накрая се избира възелът V6. Забележете, че V6 е целевият възел, така че алгоритъмът се прекратява и връща крайния път от V1 до V6, както и общата цена на пътя, както следва:
Както можем да видим, алгоритъмът не само изчислява най-краткия път от V1 до V6, но и най-краткия път от V1 до всеки друг възел в графиката. С малки модификации в алгоритъма можем да получим и тези стойности.
Внедряване на Python
Сега сме готови да се потопим дълбоко в кода и да се опитаме да внедрим алгоритъма на Dijkstra в Python, използвайки кода от статията за Graphs. Можете да прочетете тази статия тук или можете да видите целия код в моя акаунт в Github.
Първо, трябва да разширим класа Node, за да съдържа информация за разстоянието от изходния код, предишния възел и състоянието (посетен или не). Впоследствие създаваме нов клас, наречен Vertex, който разширява класа Node.
След това създаваме нов клас, който представлява алгоритъма на Дейкстра. За да създадем екземпляр на този клас, трябва да дефинираме графиката, източника и целевия възел. Класът има подходящи методи за намиране на следващия възел въз основа на разстоянието му от изходния възел и изпълнение на повтарящата се процедура, връщаща най-краткия път и неговата обща цена. Кодът за този клас е следният:
Пример
Сега сме готови да изпълним пример, за да проверим нашия алгоритъм. Ще проверим дали намираме правилния най-кратък път в горния пример. Така че ще моделираме предишната графика и ще изпълним алгоритъма.
Както можем да проверим, алгоритъмът връща същите резултати. Сега можем да стартираме този код, за да намерим най-краткия път между два възела във всяка графика с неотрицателни тегла.
Можете да видите и изтеглите целия код тук.
Заключение
Днес имахме възможност да говорим за добре познатия алгоритъм на Дейкстра, за намиране на най-краткия път между всеки два възела в графика. Не забравяйте, че този алгоритъм връща правилните резултати само ако графиката има неотрицателни тегла. Това е друг инструмент в нашата кутия с инструменти и можем да го използваме винаги, когато е необходимо. В бъдеще ще имаме възможност да говорим за други графични алгоритми като алгоритъма на Prim и алгоритъма на Kruskal. Дотогава продължавайте да учите и да кодирате. Благодаря за четенето.
Ако обичате да четете статиите ми, последвайте ме в LinkedIn и Twitter. Освен това можете да се регистрирате, за да станете член на Medium. Като член имате неограничен достъп до хиляди статии. Членството струва 5$ на месец. Можете да използвате следната връзка, за да станете среден член.
Повече съдържание за алгоритмите
Повече съдържание в plainenglish.io. Регистрирайте се за нашия „безплатен седмичен бюлетин“. Получете изключителен достъп до възможности за писане и съвети в нашата общност Discord.
