El algoritmo de Dijkstra es uno de los algoritmos destacados para encontrar la ruta más corta desde el nodo de origen hasta un nodo de destino. Utiliza el enfoque codicioso para encontrar el camino más corto. El concepto del algoritmo de Dijkstra es encontrar la distancia (ruta) más corta a partir del punto de origen e ignorar las distancias más largas mientras se realiza una actualización.
pitón __dict__
En esta sección implementaremos la Algoritmo de Dijkstra en programa Java . Además, discutiremos su uso y limitaciones.
Pasos del algoritmo de Dijkstra
Paso 1: Todos los nodos deben marcarse como no visitados.
Paso 2: Todos los nodos deben inicializarse con la distancia 'infinita' (un número grande). El nodo inicial debe inicializarse con cero.
Paso 3: Marque el nodo inicial como el nodo actual.
Etapa 4: Desde el nodo actual, analice todos sus vecinos que aún no han sido visitados y calcule sus distancias sumando el peso del borde, que establece la conexión entre el nodo actual y el nodo vecino a la distancia actual del nodo actual.
Paso 5: Ahora, compare la distancia calculada recientemente con la distancia asignada al nodo vecino y trátela como la distancia actual del nodo vecino.
Paso 6: Después de eso, se consideran los vecinos circundantes del nodo actual, que no ha sido visitado, y los nodos actuales se marcan como visitados.
Paso 7: Cuando el nodo final se marca como visitado, entonces el algoritmo ha hecho su trabajo; de lo contrario,
Paso 8: Elija el nodo no visitado al que se le ha asignado la distancia mínima y trátelo como el nuevo nodo actual. Después de eso, comience nuevamente desde el paso 4.
Pseudocódigo del algoritmo de Dijkstra
Method Dijkstra(G, s): // G is graph, s is source distance[s] -> 0 // Distance from the source to source is always 0 for every vertex vx in the Graph G: // doing the initialization work { if vx ? s { // Unknown distance function from source to each node set to infinity distance[vx] -> infinity } add vx to Queue Q // Initially, all the nodes are in Q } // The while loop Untill the Q is not empty: { // During the first run, this vertex is the source or starting node vx = vertex in Q with the minimum distance[vx] delete vx from Q } // where the neighbor ux has not been deleted yet from Q. for each neighbor ux of vx: alt = distance[vx] + length(vx, ux) // A path with lesser weight (shorter path), to ux is found if alt <distance[ux]: distance[ux]="alt" updating the distance of ux return dist[] end method < pre> <h2>Implementation of Dijkstra Algorithm</h2> <p>The following code implements the Dijkstra Algorithm using the diagram mentioned below.</p> <img src="//techcodeview.com/img/java-tutorial/65/dijkstra-algorithm-java.webp" alt="Dijkstra Algorithm Java"> <p> <strong>FileName:</strong> DijkstraExample.java</p> <pre> // A Java program that finds the shortest path using Dijkstra's algorithm. // The program uses the adjacency matrix for the representation of a graph // import statements import java.util.*; import java.io.*; import java.lang.*; public class DijkstraExample { // A utility method to compute the vertex with the distance value, which is minimum // from the group of vertices that has not been included yet static final int totalVertex = 9; int minimumDistance(int distance[], Boolean spSet[]) { // Initialize min value int m = Integer.MAX_VALUE, m_index = -1; for (int vx = 0; vx <totalvertex; 0 1 3 4 5 6 9 vx++) { if (spset[vx]="=" false && distance[vx] <="m)" m="distance[vx];" m_index="vx;" } return m_index; a utility method to display the built distance array void printsolution(int distance[], int n) system.out.println('the shortest from source 0th node all other nodes are: '); for (int j="0;" n; j++) system.out.println('to ' + is: distance[j]); that does implementation of dijkstra's path algorithm graph is being represented using adjacency matrix representation dijkstra(int graph[][], s) distance[]="new" int[totalvertex]; output distance[i] holds s spset[j] will be true vertex included in tree or finalized boolean spset[]="new" boolean[totalvertex]; initializing distances as infinite and totalvertex; distance[j]="Integer.MAX_VALUE;" itself always distance[s]="0;" compute given vertices cnt="0;" totalvertex - 1; cnt++) choose minimum set not yet processed. ux equal first iteration. spset); choosed marked it means processed spset[ux]="true;" updating value neighboring vertex. vx="0;" update only spset, there an edge vx, total weight through lesser than current (!spset[vx] graph[ux][vx] !="-1" distance[ux] distance[vx]) graph[ux][vx]; build printsolution(distance, totalvertex); main public static main(string argvs[]) * created. arr[x][y]="-" means, no any connects x y directly grph[][]="new" int[][] -1, 3, 7, -1 }, 10, 6, 2, 8, 13, 9, 4, 1, 5, }; creating object class dijkstraexample obj="new" dijkstraexample(); obj.dijkstra(grph, 0); pre> <p> <strong>Output:</strong> </p> <pre> The shortest Distance from source 0th node to all other nodes are: To 0 the shortest distance is: 0 To 1 the shortest distance is: 3 To 2 the shortest distance is: 8 To 3 the shortest distance is: 10 To 4 the shortest distance is: 18 To 5 the shortest distance is: 10 To 6 the shortest distance is: 9 To 7 the shortest distance is: 7 To 8 the shortest distance is: 7 </pre> <p>The time complexity of the above code is O(V<sup>2</sup>), where V is the total number of vertices present in the graph. Such time complexity does not bother much when the graph is smaller but troubles a lot when the graph is of larger size. Therefore, we have to do the optimization to reduce this complexity. With the help of the priority queue, we can decrease the time complexity. Observe the following code that is written for the graph depicted above.</p> <p> <strong>FileName:</strong> DijkstraExample1.java</p> <pre> // Java Program shows the implementation Dijkstra's Algorithm // Using the Priority Queue // import statement import java.util.*; // Main class DijkstraExample1 public class DijkstraExample1 { // Member variables of the class private int distance[]; private Set settld; private PriorityQueue pQue; // Total count of the vertices private int totalNodes; List<list> adjacent; // Constructor of the class public DijkstraExample1(int totalNodes) { this.totalNodes = totalNodes; distance = new int[totalNodes]; settld = new HashSet(); pQue = new PriorityQueue(totalNodes, new Node()); } public void dijkstra(List<list> adjacent, int s) { this.adjacent = adjacent; for (int j = 0; j <totalnodes; j++) { initializing the distance of every node to infinity (a large number) distance[j]="Integer.MAX_VALUE;" } adding source pque pque.add(new node(s, 0)); is always zero distance[s]="0;" while (settld.size() !="totalNodes)" terminating condition check when priority queue contains elements, return if (pque.isempty()) return; deleting that has minimum from int ux="pQue.remove().n;" whose confirmed (settld.contains(ux)) continue; we don't have call eneighbors(ux) already present in settled set. settld.add(ux); eneighbours(ux); private void eneighbours(int ux) edgedist="-1;" newdist="-1;" all neighbors vx for (int j="0;" < adjacent.get(ux).size(); current hasn't been processed (!settld.contains(vx.n)) + edgedist; new lesser cost (newdist distance[vx.n]) distance[vx.n]="newDist;" node(vx.n, distance[vx.n])); main method public static main(string argvs[]) totalnodes="9;" s="0;" representation connected edges using adjacency list by declaration class object declaring and type list<list> adjacent = new ArrayList<list>(); // Initialize list for every node for (int i = 0; i <totalnodes; 0 1 2 3 i++) { list itm="new" arraylist(); adjacent.add(itm); } adding the edges statement adjacent.get(0).add(new node(1, 3)); means to travel from node 1, one has cover units of distance it does not mean 0, we have add adjacent.get(1).add(new node(0, note that is same i.e., in both cases. similarly, added other too. node(7, 7)); node(2, 10)); node(8, 4)); adjacent.get(2).add(new node(3, 6)); node(5, 2)); 1)); adjacent.get(3).add(new node(4, 8)); 13)); adjacent.get(4).add(new 9)); adjacent.get(5).add(new node(6, 5)); adjacent.get(6).add(new adjacent.get(7).add(new adjacent.get(8).add(new creating an object class dijkstraexample1 obj="new" dijkstraexample1(totalnodes); obj.dijkstra(adjacent, s); printing shortest path all nodes source system.out.println('the :'); for (int j="0;" < obj.distance.length; j++) system.out.println(s + ' obj.distance[j]); implementing comparator interface this represents a graph implements member variables public int n; price; constructors constructor node() node(int n, price) this.n="n;" this.price="price;" @override compare(node n1, n2) if (n1.price n2.price) return 1; 0; pre> <p> <strong>Output:</strong> </p> <pre> The shortest path from the node: 0 to 0 is 0 0 to 1 is 3 0 to 2 is 8 0 to 3 is 10 0 to 4 is 18 0 to 5 is 10 0 to 6 is 9 0 to 7 is 7 0 to 8 is 7 </pre> <p>The time complexity of the above implementation is O(V + E*log(V)), where V is the total number of vertices, and E is the number of Edges present in the graph.</p> <h2>Limitations of Dijkstra Algorithm</h2> <p>The following are some limitations of the Dijkstra Algorithm:</p> <ol class="points"> <li>The Dijkstra algorithm does not work when an edge has negative values.</li> <li>For cyclic graphs, the algorithm does not evaluate the shortest path. Hence, for the cyclic graphs, it is not recommended to use the Dijkstra Algorithm.</li> </ol> <h2>Usages of Dijkstra Algorithm</h2> <p>A few prominent usages of the Dijkstra algorithm are:</p> <ol class="points"> <li>The algorithm is used by Google maps.</li> <li>The algorithm is used to find the distance between two locations.</li> <li>In IP routing also, this algorithm is used to discover the shortest path.</li> </ol> <hr></totalnodes;></list></totalnodes;></list></list></pre></totalvertex;></pre></distance[ux]:> La complejidad temporal del código anterior es O (V2), donde V es el número total de vértices presentes en el gráfico. Esta complejidad temporal no molesta mucho cuando el gráfico es más pequeño, pero sí cuando el gráfico es de mayor tamaño. Por lo tanto, tenemos que hacer la optimización para reducir esta complejidad. Con la ayuda de la cola de prioridad, podemos disminuir la complejidad del tiempo. Observe el siguiente código que está escrito para el gráfico que se muestra arriba.
Nombre del archivo: DijkstraExample1.java
// Java Program shows the implementation Dijkstra's Algorithm // Using the Priority Queue // import statement import java.util.*; // Main class DijkstraExample1 public class DijkstraExample1 { // Member variables of the class private int distance[]; private Set settld; private PriorityQueue pQue; // Total count of the vertices private int totalNodes; List<list> adjacent; // Constructor of the class public DijkstraExample1(int totalNodes) { this.totalNodes = totalNodes; distance = new int[totalNodes]; settld = new HashSet(); pQue = new PriorityQueue(totalNodes, new Node()); } public void dijkstra(List<list> adjacent, int s) { this.adjacent = adjacent; for (int j = 0; j <totalnodes; j++) { initializing the distance of every node to infinity (a large number) distance[j]="Integer.MAX_VALUE;" } adding source pque pque.add(new node(s, 0)); is always zero distance[s]="0;" while (settld.size() !="totalNodes)" terminating condition check when priority queue contains elements, return if (pque.isempty()) return; deleting that has minimum from int ux="pQue.remove().n;" whose confirmed (settld.contains(ux)) continue; we don\'t have call eneighbors(ux) already present in settled set. settld.add(ux); eneighbours(ux); private void eneighbours(int ux) edgedist="-1;" newdist="-1;" all neighbors vx for (int j="0;" < adjacent.get(ux).size(); current hasn\'t been processed (!settld.contains(vx.n)) + edgedist; new lesser cost (newdist distance[vx.n]) distance[vx.n]="newDist;" node(vx.n, distance[vx.n])); main method public static main(string argvs[]) totalnodes="9;" s="0;" representation connected edges using adjacency list by declaration class object declaring and type list<list> adjacent = new ArrayList<list>(); // Initialize list for every node for (int i = 0; i <totalnodes; 0 1 2 3 i++) { list itm="new" arraylist(); adjacent.add(itm); } adding the edges statement adjacent.get(0).add(new node(1, 3)); means to travel from node 1, one has cover units of distance it does not mean 0, we have add adjacent.get(1).add(new node(0, note that is same i.e., in both cases. similarly, added other too. node(7, 7)); node(2, 10)); node(8, 4)); adjacent.get(2).add(new node(3, 6)); node(5, 2)); 1)); adjacent.get(3).add(new node(4, 8)); 13)); adjacent.get(4).add(new 9)); adjacent.get(5).add(new node(6, 5)); adjacent.get(6).add(new adjacent.get(7).add(new adjacent.get(8).add(new creating an object class dijkstraexample1 obj="new" dijkstraexample1(totalnodes); obj.dijkstra(adjacent, s); printing shortest path all nodes source system.out.println(\'the :\'); for (int j="0;" < obj.distance.length; j++) system.out.println(s + \' obj.distance[j]); implementing comparator interface this represents a graph implements member variables public int n; price; constructors constructor node() node(int n, price) this.n="n;" this.price="price;" @override compare(node n1, n2) if (n1.price n2.price) return 1; 0; pre> <p> <strong>Output:</strong> </p> <pre> The shortest path from the node: 0 to 0 is 0 0 to 1 is 3 0 to 2 is 8 0 to 3 is 10 0 to 4 is 18 0 to 5 is 10 0 to 6 is 9 0 to 7 is 7 0 to 8 is 7 </pre> <p>The time complexity of the above implementation is O(V + E*log(V)), where V is the total number of vertices, and E is the number of Edges present in the graph.</p> <h2>Limitations of Dijkstra Algorithm</h2> <p>The following are some limitations of the Dijkstra Algorithm:</p> <ol class="points"> <li>The Dijkstra algorithm does not work when an edge has negative values.</li> <li>For cyclic graphs, the algorithm does not evaluate the shortest path. Hence, for the cyclic graphs, it is not recommended to use the Dijkstra Algorithm.</li> </ol> <h2>Usages of Dijkstra Algorithm</h2> <p>A few prominent usages of the Dijkstra algorithm are:</p> <ol class="points"> <li>The algorithm is used by Google maps.</li> <li>The algorithm is used to find the distance between two locations.</li> <li>In IP routing also, this algorithm is used to discover the shortest path.</li> </ol> <hr></totalnodes;></list></totalnodes;></list></list> La complejidad temporal de la implementación anterior es O (V + E*log(V)), donde V es el número total de vértices y E es el número de aristas presentes en el gráfico.
Limitaciones del algoritmo de Dijkstra
Las siguientes son algunas limitaciones del algoritmo de Dijkstra:
- El algoritmo de Dijkstra no funciona cuando una arista tiene valores negativos.
- Para gráficos cíclicos, el algoritmo no evalúa el camino más corto. Por tanto, para los gráficos cíclicos, no se recomienda utilizar el algoritmo de Dijkstra.
Usos del algoritmo de Dijkstra
Algunos usos destacados del algoritmo de Dijkstra son:
- El algoritmo es utilizado por Google Maps.
- El algoritmo se utiliza para encontrar la distancia entre dos ubicaciones.
- También en el enrutamiento IP, este algoritmo se utiliza para descubrir el camino más corto.