O Java não possui uma estrutura de dados de heap embutida, mas você pode usar o `priorityQueue`, que implementa um min-heap (ou você pode criar sua própria pilha). O algoritmo mais comum que aproveita uma pilha para cálculos de caminho mais curto é o algoritmo de Dijkstra. Veja como você pode implementar o algoritmo de Dijkstra em Java usando um `priorityQueue`:
`` `Java
importar java.util.*;
classe pública Dijkstra {
mapa estático público
Dijkstra (gráfico do gráfico, fonte do nó) {
Mapa distances =new hashmap <> ();
PriorityQueue mineap =new priorityQueue <> (comparador.comparingInt (Distances ::get)); // min-heap com base na distância
// inicializa as distâncias ao infinito, exceto pela fonte
para (nó nó:graph.getnodes ()) {
Distances.put (nó, Integer.max_value);
}
distances.put (fonte, 0);
mineap.add (fonte);
while (! minhap.isempty ()) {
Nó corrente =mineap.poll ();
para (Edge Edge:Current.getEdges ()) {
Nó vizinho =edge.getto ();
int a distância =distances.get (atual) + edge.getweight ();
if (distância MINNHEAP.REMOVE (vizinho); // Remova para atualizar a prioridade
distances.put (vizinho, distância);
MINNHEAP.Add (vizinho);
}
}
}
distâncias de retorno;
}
// Classes auxiliares para representação gráfica
Gráfico de classe estática {
Conjunto privado nós =novo hashset <> ();
public void addNode (nó nó) {
modes.add (nó);
}
Public Set getNodes () {
nós de retorno;
}
}
Nó da classe estática {
nome de string privado;
Lista privada arestas =new ArrayList <> ();
public node (nome da string) {
this.name =nome;
}
public String getName () {Return Name;}
public void Addedge (borda de borda) {
Edges.add (Edge);
}
Lista pública getedges () {
bordas de retorno;
}
@Override
public boolean é igual a (objeto obj) {
if (this ==obj) retorna true;
if (obj ==null || getClass ()! =obj.getclass ()) retorna false;
Nó nó =(nó) obj;
retornar objetos.equals (nome, node.name);
}
@Override
public int hashcode () {
retornar objetos.hash (nome);
}
}
classe estática Edge {
nó privado para;
peso privado int;
public Edge (nó para, int peso) {
this.to =para;
this.weight =peso;
}
public node getto () {
retornar a;
}
public int getWeight () {
peso de retorno;
}
}
public static void main (string [] args) {
Gráfico gráfico =new Graph ();
Nó a =novo nó ("a");
Nó b =novo nó ("b");
Nó c =novo nó ("c");
Nó d =novo nó ("d");
A.Addedge (New Edge (B, 4));
a.Addedge (nova borda (c, 2));
b.addedge (nova borda (c, 1));
b.addedge (nova borda (d, 5));
c.Addedge (New Edge (D, 8));
Graph.AddNode (A);
Graph.AddNode (B);
Graph.AddNode (C);
Graph.AddNode (D);
Mapa distances =dijkstra (gráfico, a);
para (map.entry entrada:distances.entryset ()) {
System.out.println ("Distância de A a" + Entry.getKey (). GetName () + ":" + Entry.getValue ());
}
}
}
`` `
Explicação:
1. `graph`,` node`, `Edge` Classes: Estes representam a estrutura do gráfico. A classe `node` inclui uma lista de seus objetos` Edge ".
2. `Dijkstra` Função: Isso implementa o algoritmo de Dijkstra.
- Ele inicializa um `hashmap` (` distances`) para armazenar as distâncias mais curtas do nó de origem para todos os outros nós. Inicialmente, todas as distâncias são definidas para o infinito, exceto a fonte, que é 0.
- Um `priorityQueue` é usado como um min-heap para selecionar com eficiência o nó com a menor distância. O comparador garante que os nós sejam ordenados por suas distâncias.
- O algoritmo remove iterativamente o nó com a menor distância da pilha. Para cada um de seus vizinhos, ele verifica se um caminho mais curto é encontrado e atualiza a distância e a pilha de acordo. As operações `remover` e` add` no `priorityQueue 'mantêm a propriedade Heap com eficiência (tempo logarítmico).
3. `main` função: Isso cria um gráfico de amostra e chama a função `dijkstra`. O resultado mostra a menor distância do nó "A" para todos os outros nós.
Lembre-se de lidar com problemas em potencial, como pesos de borda negativos (o algoritmo de Dijkstra não funciona corretamente com eles; você precisaria do algoritmo Bellman-Ford) e gráficos desconectados. Este exemplo aprimorado lida com `equals` e` hashcode` na classe `node` para gerenciar corretamente o manuseio` priorityQueue` e o manuseio -chave do Hashmap.