Saltar al contenido

algoritmo de dijkstra en el ejemplo de código de gráfico java

Hemos recabado en diferentes foros y así darte la respuesta para tu dilema, en caso de dudas puedes dejar tu inquietud y contestaremos con mucho gusto, porque estamos para ayudarte.

Ejemplo: algoritmo de java djikstra

importjava.util.*;publicclass DPQ privateint dist[];privateSet<Integer> settled;privatePriorityQueue<Node> pq;privateintV;// Number of vertices List<List<Node>> adj;publicDPQ(intV)this.V=V; 
        dist =newint[V]; 
        settled =newHashSet<Integer>(); 
        pq =newPriorityQueue<Node>(V,newNode());// Function for Dijkstra's Algorithm publicvoiddijkstra(List<List<Node>> adj,int src)this.adj = adj;for(int i =0; i <V; i++) 
            dist[i]=Integer.MAX_VALUE;// Add source node to the priority queue 
        pq.add(newNode(src,0));// Distance to the source is 0 
        dist[src]=0;while(settled.size()!=V)// remove the minimum distance node  // from the priority queue  int u = pq.remove().node;// adding the node whose distance is // finalized 
            settled.add(u);e_Neighbours(u);// Function to process all the neighbours  // of the passed node privatevoide_Neighbours(int u)int edgeDistance =-1;int newDistance =-1;// All the neighbors of v for(int i =0; i < adj.get(u).size(); i++)Node v = adj.get(u).get(i);// If current node hasn't already been processed if(!settled.contains(v.node)) 
                edgeDistance = v.cost; 
                newDistance = dist[u]+ edgeDistance;// If new distance is cheaper in cost if(newDistance < dist[v.node]) 
                    dist[v.node]= newDistance;// Add the current node to the queue 
                pq.add(newNode(v.node, dist[v.node]));// Driver code publicstaticvoidmain(String arg[])intV=5;int source =0;// Adjacency list representation of the  // connected edges List<List<Node>> adj =newArrayList<List<Node>>();// Initialize list for every node for(int i =0; i <V; i++)List<Node> item =newArrayList<Node>(); 
            adj.add(item);// Inputs for the DPQ graph 
        adj.get(0).add(newNode(1,9)); 
        adj.get(0).add(newNode(2,6)); 
        adj.get(0).add(newNode(3,5)); 
        adj.get(0).add(newNode(4,3)); 
  
        adj.get(2).add(newNode(1,2)); 
        adj.get(2).add(newNode(3,4));// Calculate the single source shortest path DPQ dpq =newDPQ(V); 
        dpq.dijkstra(adj, source);// Print the shortest path to all the nodes // from the source node System.out.println("The shorted path from node :");for(int i =0; i < dpq.dist.length; i++)System.out.println(source +" to "+ i +" is "+ dpq.dist[i]);// Class to represent a node in the graph classNodeimplementsComparator<Node>publicint node;publicint cost;publicNode()publicNode(int node,int cost)this.node = node;this.cost = cost;@Overridepublicintcompare(Node node1,Node node2)if(node1.cost < node2.cost)return-1;if(node1.cost > node2.cost)return1;return0;

Si posees alguna indecisión y capacidad de aumentar nuestro enunciado puedes realizar una anotación y con deseo lo estudiaremos.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *