Мени

Како применити Дијкстрин алгоритам у Јави

how implement dijkstra s algorithm java

Испробајте Наш Инструмент За Елиминисање Проблема

Овај водич објашњава како применити Дијкстрин алгоритам у Јави за проналажење најкраћих рута у графикону или дрвету уз помоћ примера:

У нашем ранијем водичу о Графовима на Јави видели смо да се графикони користе за проналажење најкраће путање између чворова, осим осталих апликација.

Да бисмо пронашли најкраћи пут између два чвора графа, углавном користимо алгоритам познат као „ Дијкстрин алгоритам ”. Овај алгоритам остаје широко коришћен алгоритам за проналажење најкраћих рута у графикону или стаблу.

=> Овде проверите СВЕ Јава туторијале

Дијкстрин алгоритам у Јави

Шта ћете научити:

Дијкстрин алгоритам у Јави

С обзиром на пондерисани граф и почетни (изворни) врх у графикону, Дијкстрин алгоритам се користи за проналажење најкраће удаљености од изворног чвора до свих осталих чворова на графикону.

Као резултат покретања Дијкстриног алгоритма на графу добијамо дрво најкраће путање (СПТ) са изворним теменом као кореном.

У Дијкстрином алгоритму одржавамо два скупа или листе. Један садржи врхове који су део стабла најкраће путање (СПТ), а други садржи врхове који се процењују да ли су укључени у СПТ. Отуда за сваку итерацију налазимо врх са друге листе који има најкраћи пут.

Псеудокод за Дијкстрин алгоритам најкраће путање је дат у наставку.

.нет питања и одговори за искусне

Псеудоцоде

Доље је дат псеудокод за овај алгоритам.

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

Узмимо сада узорак графикона и илуструјмо Дијкстрин најкраћи алгоритам .

алгоритам најкраћег пута

У почетку је СПТ (Схортест Патх Трее) постављен на бесконачност.

Почнимо са теменом 0. Дакле, за почетак стављамо врх 0 у сптСет.

сптСет = {0, ИНФ, ИНФ, ИНФ, ИНФ, ИНФ}.

Даље са вертексом 0 у сптСет-у истражићемо његове суседе. Врхови 1 и 2 су два суседна чвора од 0 са растојањем 2, односно 1.

суседни чворови

На горњој слици такође смо ажурирали сваки суседни врх (1 и 2) са одговарајућом удаљеностом од изворног темена 0. Сада видимо да врх 2 има минималну удаљеност. Дакле, следеће додајемо врх 2 у сптСет. Такође, истражујемо суседе темена 2.

суседни врх

Сада тражимо темену са минималним растојањем и оне који нису тамо у спт. Врх 1 бирамо на удаљености 2.

темена са минималним растојањем

Као што видимо на горњој слици, од свих суседних чворова 2, 0 и 1 већ су у сптСету, па их игноришемо. Од суседних чворова 5 и 3, 5 имају најмање трошкова. Дакле, додајемо га у сптСет и истражујемо суседне чворове.

суседни чворови од 2, 0

На горњој слици видимо да су, осим чворова 3 и 4, сви остали чворови у сптСет-у. Од 3 и 4, чвор 3 има најмање трошкова. Па смо га ставили у сптСет.

чворови 3 и 4

Као што је приказано горе, сада нам је остао само један врх, тј. 4, а његова удаљеност од коренског чвора је 16. Коначно, стављамо га у сптСет да бисмо добили коначни сптСет = {0, 2, 1, 5, 3, 4} који даје нам удаљеност сваког темена од изворног чвора 0.

Имплементација Дијкстриног алгоритма у Јави

Примена Дијкстриног алгоритма најкраћег пута у Јави може се постићи на два начина. Можемо користити редове приоритета и листу суседности или можемо користити матрицу и низове суседства.

У овом одељку ћемо видети обе примене.

Коришћење реда приоритета

У овој имплементацији користимо приоритетни ред за чување темена са најкраћом удаљеностом. Графикон је дефинисан помоћу листе суседности. Пример програма је приказан у наставку.

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

Излаз:

ред приоритета - излаз

Коришћење матрице суседства

У овом приступу користимо матрицу суседства за представљање графа. За спт сет користимо низове.

Следећи програм приказује ову примену.

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) Да ли Дијкстра ради за неусмерене графиконе?

Одговор: Ако је граф усмерен или усмерен, није битно у случају Дијкстриног алгоритма. Овај алгоритам се тиче само темена на графикону и пондера.

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

Одговор: Сложеност времена Дијкстриног алгоритма је О (В 2). Када се имплементира са редом мин-приоритета, временска сложеност овог алгоритма своди се на О (В + Е л о г В).

П # 3) Да ли је Дијкстра похлепни алгоритам?

Одговор: Да, Дијкстра је похлепни алгоритам. Слично Примовом алгоритму за проналажење минималног распона стабла (МСТ), ови алгоритми такође почињу од коренског темена и увек бирају најоптималнији врх са минималном путањом.

П # 4) Да ли је Дијкстра ДФС или БФС?

Одговор: Није ни једно ни друго. Али како Дијкстрин алгоритам користи приоритетни ред за своју примену, може се сматрати блиским БФС-у.

П # 5) Где се користи Дијкстра алгоритам?

Одговор: Углавном се користи у протоколима за усмеравање, јер помаже да се пронађе најкраћи пут од једног до другог чвора.

Закључак

У овом упутству смо разговарали о Дијкстрином алгоритму. Користимо овај алгоритам за проналажење најкраће путање од коренског чвора до осталих чворова на графикону или стаблу.

Обично имплементирамо Дијкстрин алгоритам користећи приоритетни ред јер морамо пронаћи минималну путању. Овај алгоритам такође можемо применити помоћу матрице суседности. У овом упутству смо разговарали о оба ова приступа.

Надамо се да ће вам овај водич бити од помоћи.

=> Посетите овде да бисте видели серију Јава обуке за све

Препоручено читање

^