El algoritmo de Dijkstra es muy similar al algoritmo de Prim para el árbol de expansión mínimo . Al igual que el MST de Prim, generamos un SPT (árbol de ruta más corta) con una fuente determinada como raíz. Mantenemos dos conjuntos, un conjunto contiene vértices incluidos en el árbol de ruta más corta, otro conjunto incluye vértices que aún no están incluidos en el árbol de ruta más corta. En cada paso del algoritmo, encontramos un vértice que está en el otro conjunto (conjunto de aún no incluido) y tiene una distancia mínima de la fuente.
Aquí, el único inconveniente con los algoritmos de Dijkstra es que, al encontrar la ruta más corta como se indica a continuación, necesitamos encontrar la ruta de menor costo recorriendo toda la array de costos. No es un gran problema para los gráficos pequeños y, al mismo tiempo, se convierte en un problema de eficiencia para los gráficos grandes porque cada vez que necesitamos recorrer una array mientras la recorremos. Ahora que sabemos que las colas pueden funcionar para nosotros, aplicamos el concepto de colas prioritarias con este algoritmo para eliminar algunas de las desventajas y hacer que la complejidad sea mucho mejor.
Analicemos ahora la declaración del problema, mientras que, de acuerdo con el título, parece la pura implementación de una de las estructuras de datos conocida como cola de prioridad con la participación del análisis de algoritmos. Entonces, comencemos con la declaración del problema que se enumera a continuación antes de enfatizar la nota, ya que todo el concepto gira en torno a la representación de la array de adyacencia.
Nota: las implementaciones de ruta más corta de Dijkstra como el algoritmo de Dijkstra para la representación de array de adyacencia (con complejidad de tiempo O (v 2 )
Planteamiento del problema
Dado un gráfico con representación de lista de adyacencia de los bordes entre los Nodes, la tarea es implementar el Algoritmo de Dijkstra para la ruta más corta de fuente única utilizando Priority Queue en Java. Dado un gráfico y un vértice fuente en el gráfico, encuentra los caminos más cortos desde la fuente hasta todos los vértices en el gráfico dado.
Ilustración:
Input : Source = 0
Output :
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
Implementación:
Java
// Java Program to Implement Dijkstra's Algorithm
// Using Priority Queue
// Importing utility classes
import java.util.*;
// Main class DPQ
public class GFG {
// Member variables of this class
private int dist[];
private Set<Integer> settled;
private PriorityQueue<Node> pq;
// Number of vertices
private int V;
List<List<Node> > adj;
// Constructor of this class
public GFG(int V)
{
// This keyword refers to current object itself
this.V = V;
dist = new int[V];
settled = new HashSet<Integer>();
pq = new PriorityQueue<Node>(V, new Node());
}
// Method 1
// Dijkstra's Algorithm
public void dijkstra(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(new Node(src, 0));
// Distance to the source is 0
dist[src] = 0;
while (settled.size() != V) {
// Terminating condition check when
// the priority queue is empty, return
if (pq.isEmpty())
return;
// Removing the minimum distance node
// from the priority queue
int u = pq.remove().node;
// Adding the node whose distance is
// finalized
if (settled.contains(u))
// Continue keyword skips execution for
// following check
continue;
// We don't have to call e_Neighbors(u)
// if u is already present in the settled set.
settled.add(u);
e_Neighbours(u);
}
}
// Method 2
// To process all the neighbours
// of the passed node
private void e_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(new Node(v.node, dist[v.node]));
}
}
}
// Main driver method
public static void main(String arg[])
{
int V = 5;
int source = 0;
// Adjacency list representation of the
// connected edges by declaring List class object
// Declaring object of type List<Node>
List<List<Node> > adj
= new ArrayList<List<Node> >();
// Initialize list for every node
for (int i = 0; i < V; i++) {
List<Node> item = new ArrayList<Node>();
adj.add(item);
}
// Inputs for the GFG(dpq) graph
adj.get(0).add(new Node(1, 9));
adj.get(0).add(new Node(2, 6));
adj.get(0).add(new Node(3, 5));
adj.get(0).add(new Node(4, 3));
adj.get(2).add(new Node(1, 2));
adj.get(2).add(new Node(3, 4));
// Calculating the single source shortest path
GFG dpq = new GFG(V);
dpq.dijkstra(adj, source);
// Printing 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 2
// Helper class implementing Comparator interface
// Representing a node in the graph
class Node implements Comparator<Node> {
// Member variables of this class
public int node;
public int cost;
// Constructors of this class
// Constructor 1
public Node() {}
// Constructor 2
public Node(int node, int cost)
{
// This keyword refers to current instance itself
this.node = node;
this.cost = cost;
}
// Method 1
@Override public int compare(Node node1, Node node2)
{
if (node1.cost < node2.cost)
return -1;
if (node1.cost > node2.cost)
return 1;
return 0;
}
}
The shorted path from node : 0 to 0 is 0 0 to 1 is 8 0 to 2 is 6 0 to 3 is 5 0 to 4 is 3
Publicación traducida automáticamente
Artículo escrito por Akashkumar17 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA