Меню

Как да приложим алгоритъма на Dijkstra в Java

how implement dijkstra s algorithm java

Опитайте Нашия Инструмент За Премахване На Проблемите

Този урок обяснява как да внедрите алгоритъма на Dijkstra в Java, за да намерите най-кратките маршрути в графика или дърво с помощта на примери:

В по-ранния ни урок за Графи в Java видяхме, че графиките се използват за намиране на най-краткия път между възлите, освен другите приложения.

За да намерим най-краткия път между два възела на графика, ние най-често използваме алгоритъм, известен като „ Алгоритъм на Дейкстра ”. Този алгоритъм остава широко използваният алгоритъм за намиране на най-кратките маршрути в графика или дърво.

=> Проверете ВСИЧКИ уроци по Java тук

Алгоритъмът на Дейкстра в Java

Какво ще научите:

Алгоритъмът на Дейкстра в Java

Като се има предвид претеглена графика и начален (изходен) връх в графиката, алгоритъмът на Dijkstra се използва за намиране на най-краткото разстояние от възела източник до всички останали възли в графиката.

В резултат на работещия алгоритъм на Dijkstra на графика получаваме дървото с най-краткия път (SPT) с изходния връх като корен.

В алгоритъма на Dijkstra ние поддържаме два набора или списъка. Единият съдържа върховете, които са част от дървото с най-кратък път (SPT), а другият съдържа върхове, които се оценяват за включване в SPT. Следователно за всяка итерация намираме връх от втория списък, който има най-краткия път.

Псевдокодът за алгоритъма за най-краткия път на Dijkstra е даден по-долу.

файл вход и изход c ++

Псевдокод

По-долу е даден псевдокодът за този алгоритъм.

procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue PQueue path (S) <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path (U) + edge_weight(U, V) if tempDistance < path (V) path (V) <- tempDistance previous(V) <- U return path(), previous() end

Нека сега вземем примерна графика и илюстрираме алгоритъма за най-краткия път на Dijkstra .

алгоритъм с най-кратък път

Първоначално комплектът SPT (Shortest Path Tree) е настроен на безкрайност.

Нека започнем с връх 0. Така че за начало поставяме върха 0 в sptSet.

sptSet = {0, INF, INF, INF, INF, INF}.

След това с върх 0 в sptSet ще изследваме съседите му. Върховете 1 и 2 са два съседни възела с 0 с разстояние 2 и 1 съответно.

съседни възли

На горната фигура ние също актуализирахме всеки съседен връх (1 и 2) със съответното им разстояние от изходния връх 0. Сега виждаме, че връх 2 има минимално разстояние. След това добавяме връх 2 към sptSet. Също така изследваме съседите на връх 2.

съседен връх

Сега търсим върха с минимално разстояние и тези, които не са там в spt. Избираме връх 1 с разстояние 2.

връх с минимално разстояние

Както виждаме на горната фигура, от всички съседни възли на 2, 0 и 1 вече са в sptSet, така че ние ги игнорираме. От съседните възли 5 и 3, 5 имат най-ниска цена. Затова го добавяме към sptSet и изследваме съседните му възли.

съседни възли от 2, 0

На горната фигура виждаме, че с изключение на възли 3 и 4, всички останали възли са в sptSet. От 3 и 4 възел 3 има най-малко разходи. Затова го поставихме в sptSet.

възли 3 и 4

Както е показано по-горе, сега ни остава само един връх, т.е. 4 и разстоянието му от основния възел е 16. Накрая го поставяме в sptSet, за да получим окончателния sptSet = {0, 2, 1, 5, 3, 4}, че ни дава разстоянието на всеки връх от изходния възел 0.

Прилагане на алгоритъма на Dijkstra в Java

Внедряването на алгоритъма на най-краткия път на Dijkstra в Java може да бъде постигнато по два начина. Можем да използваме приоритетни опашки и списък на съседство, или да използваме матрица и масиви на съседство.

В този раздел ще видим и двете изпълнения.

Използване на приоритетна опашка

В това изпълнение използваме приоритетната опашка, за да съхраняваме върховете с най-краткото разстояние. Графиката се дефинира с помощта на списъка за съседство. Примерна програма е показана по-долу.

import java.util.*; class Graph_pq { int dist(); Set visited; PriorityQueue pqueue; int V; // Number of vertices List adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int(V); visited = new HashSet(); pqueue = new PriorityQueue(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i adj_list = new ArrayList(); // Initialize adjacency list for every node in the graph for (int i = 0; i

Изход:

приоритетна опашка - изход

Използване на матрица за съседство

При този подход използваме матрицата на съседство, за да представим графиката. За spt set използваме масиви.

Следващата програма показва това изпълнение.

import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array(), Boolean sptSet()) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v

Изход:

Матрица на съседство - изход

често задавани въпроси

В # 1) Действа ли Dijkstra за неориентирани графики?

Отговор: Ако графиката е насочена или насочена, няма значение в случая на алгоритъма на Дейкстра. Този алгоритъм се занимава само с върховете в графиката и тежестите.

В # 2) Каква е сложността във времето на алгоритъма на Дейкстра?

Отговор: Сложността във времето на алгоритъма на Дейкстра е O (V 2). Когато се изпълнява с опашката с минимален приоритет, сложността във времето на този алгоритъм се свежда до O (V + E l o g V).

В # 3) Дали Dikkstra е алчен алгоритъм?

Отговор: Да, Dijkstra е алчен алгоритъм. Подобно на алгоритъма на Prim за намиране на минималното обхващащо дърво (MST), тези алгоритми също започват от корен връх и винаги избира най-оптималния връх с минималния път.

В # 4) Дали Dikkstra DFS или BFS?

Отговор: Не е нито едното, нито другото. Но тъй като алгоритъмът на Dijkstra използва приоритетна опашка за изпълнението си, той може да се разглежда като близък до BFS.

В # 5) Къде се използва алгоритъмът на Dijkstra?

Отговор: Използва се предимно в протоколи за маршрутизиране, тъй като помага да се намери най-краткият път от един възел до друг възел.

Заключение

В този урок обсъдихме алгоритъма на Dijkstra. Използваме този алгоритъм, за да намерим най-краткия път от основния възел до другите възли в графиката или дърво.

Обикновено прилагаме алгоритъма на Dijkstra, използвайки приоритетна опашка, тъй като трябва да намерим минималния път. Също така можем да приложим този алгоритъм, като използваме матрицата на съседство. Ние разгледахме и двата подхода в този урок.

Надяваме се, че този урок ще ви бъде полезен.

=> Посетете тук, за да видите серията за обучение за Java за всички

Препоръчително четене

^