how implement dijkstra s algorithm java
Aquest tutorial explica com implementar l'algorisme de Dijkstra a Java per trobar les rutes més curtes en un gràfic o un arbre amb l'ajuda d'exemples:
Al nostre anterior tutorial sobre Gràfics a Java, vam veure que els gràfics s’utilitzen per trobar el camí més curt entre els nodes a part d’altres aplicacions.
Per trobar el camí més curt entre dos nodes d'un gràfic, utilitzem principalment un algorisme conegut com ' L’algorisme de Dijkstra ”. Aquest algorisme continua sent l'algorisme àmpliament utilitzat per trobar les rutes més curtes en un gràfic o un arbre.
=> Consulteu TOTS els tutorials de Java aquí
Què aprendreu:
L’algorisme de Java de Dijkstra
Donat un gràfic ponderat i un vèrtex inicial (font) al gràfic, s’utilitza l’algorisme de Dijkstra per trobar la distància més curta des del node font fins a la resta de nodes del gràfic.
Com a resultat de l’algoritme de Dijkstra que s’executa en un gràfic, obtenim l’arbre de camí més curt (SPT) amb el vèrtex font com a arrel.
A l’algorisme de Dijkstra, mantenim dos conjunts o llistes. Un conté els vèrtexs que formen part de l’arbre del camí més curt (SPT) i l’altre conté els vèrtexs que s’estan avaluant per incloure’s a SPT. Per tant, per a cada iteració, trobem un vèrtex de la segona llista que té el camí més curt.
A continuació es dóna el pseudocodi de l’algorisme de trajectòria més curt de Dijkstra.
python selenium troba element per text
Pseudocodi
A continuació es mostra el pseudocodi d’aquest algorisme.
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 Prenem ara un exemple de gràfic i il·lustrem l’algoritme de camí més curt de Dijkstra .
Inicialment, el conjunt SPT (Shortest Path Tree) es defineix a infinit.
Comencem pel vèrtex 0. Així, per començar, posem el vèrtex 0 a sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
A continuació, amb el vèrtex 0 a sptSet, explorarem els seus veïns. Els vèrtexs 1 i 2 són dos nodes adjacents de 0 amb distància 2 i 1 respectivament.
A la figura anterior, també hem actualitzat cada vèrtex adjacent (1 i 2) amb la seva respectiva distància del vèrtex font 0. Ara veiem que el vèrtex 2 té una distància mínima. A continuació, afegim el vèrtex 2 a l'sptSet. També explorem els veïns del vèrtex 2.
Ara busquem el vèrtex amb una distància mínima i aquells que no hi són a spt. Escollim el vèrtex 1 amb la distància 2.
Com veiem a la figura anterior, de tots els nodes adjacents de 2, 0 i 1 ja estan a sptSet, de manera que els ignorem. Dels nodes adjacents 5 i 3, 5 tenen el menor cost. Per tant, l’afegim a l’sptSet i explorem els seus nodes adjacents.
A la figura anterior, veiem que, excepte els nodes 3 i 4, tots els altres nodes es troben a sptSet. De 3 i 4, el node 3 té el menor cost. Per tant, el posem a sptSet.
Com es mostra més amunt, ara només ens queda un vèrtex, és a dir, 4 i la seva distància al node arrel és 16. Finalment, el posem a sptSet per obtenir el sptSet final = {0, 2, 1, 5, 3, 4} que ens dóna la distància de cada vèrtex del node font 0.
Implementació de l’algorisme de Dijkstra a Java
La implementació de l’algoritme de camí més curt de Dijkstra a Java es pot aconseguir de dues maneres. Podem utilitzar cues de prioritat i llista d’adjacències o podem utilitzar matrius d’adjacència i matrius.
En aquesta secció, veurem les dues implementacions.
Ús d’una cua de prioritat
En aquesta implementació, fem servir la cua de prioritat per emmagatzemar els vèrtexs amb la distància més curta. El gràfic es defineix mitjançant la llista d’adjacències. A continuació es mostra un programa de mostra.
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 Sortida:
Utilitzant Adjacency Matrix
En aquest enfocament, utilitzem la matriu d'adjacència per representar el gràfic. Per al conjunt de SPT utilitzem matrius.
El programa següent mostra aquesta implementació.
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 Sortida:
Preguntes freqüents
P # 1) Funciona Dijkstra per a gràfics no dirigits?
Resposta: Si el gràfic està dirigit o no dirigit, no importa en el cas de l'algorisme de Dijkstra. Aquest algorisme només es preocupa pels vèrtexs del gràfic i els pesos.
Q # 2) Quina és la complexitat temporal de l'algorisme de Dijkstra?
Resposta: La complexitat temporal de l’algorisme de Dijkstra és O (V 2). Quan s’implementa amb la cua de prioritat mínima, la complexitat temporal d’aquest algorisme es redueix a O (V + E l o g V).
Q # 3) Dijkstra és un algoritme llaminer?
Resposta: Sí, Dijkstra és un algoritme llaminer. De manera similar a l’algorisme de Prim per trobar l’arbre d’extensió mínim (MST), aquests algoritmes també parteixen d’un vèrtex arrel i sempre trien el vèrtex més òptim amb el camí mínim.
Q # 4) És Dijkstra DFS o BFS?
Resposta: No és cap dels dos. Però com que l'algorisme de Dijkstra utilitza una cua de prioritat per a la seva implementació, es pot veure com a prop de BFS.
P # 5) On s'utilitza l'algorisme de Dijkstra?
Resposta: S’utilitza sobretot en protocols d’encaminament, ja que ajuda a trobar el camí més curt d’un node a un altre.
Conclusió
En aquest tutorial, hem parlat de l'algorisme de Dijkstra. Utilitzem aquest algorisme per trobar el camí més curt des del node arrel cap als altres nodes del gràfic o un arbre.
Normalment implementem l’algorisme de Dijkstra mitjançant una cua de prioritat ja que hem de trobar el camí mínim. També podem implementar aquest algorisme mitjançant la matriu d’adjacència. Hem comentat aquests dos enfocaments en aquest tutorial.
Esperem que aquest tutorial us sigui útil.
=> Visiteu aquí per veure la sèrie d'entrenaments de Java per a tothom
Lectura recomanada
- Algorisme de cerca binària a Java: implementació i exemples
- Bubble Sort In Java - Algoritmes d'ordenació de Java i exemples de codi
- Classificació per inserció a Java: algorisme i exemples d'ordenació per inserció
- Selecció d'ordenació a Java - Algorisme de selecció i exemples
- QuickSort a Java: algorisme, il·lustració i implementació
- Tutorial JAVA per a principiants: més de 100 tutorials pràctics de vídeo Java
- Tutorial de reflexió de Java amb exemples
- Matriu dentada a Java: tutorial amb exemples
