how implement dijkstra s algorithm java
Este tutorial explica como implementar o algoritmo de Dijkstra em Java para encontrar as rotas mais curtas em um gráfico ou uma árvore com a ajuda de exemplos:
Em nosso tutorial anterior sobre Gráficos em Java, vimos que os gráficos são usados para encontrar o caminho mais curto entre os nós além de outros aplicativos.
Para encontrar o caminho mais curto entre dois nós de um gráfico, usamos principalmente um algoritmo conhecido como “ Algoritmo de Dijkstra ”. Esse algoritmo continua sendo o algoritmo amplamente usado para encontrar as rotas mais curtas em um gráfico ou árvore.
=> Verifique TODOS os tutoriais Java aqui
O que você aprenderá:
Algoritmo de Dijkstra em Java
Dado um gráfico ponderado e um vértice inicial (fonte) no gráfico, o algoritmo de Dijkstra é usado para encontrar a distância mais curta do nó de origem a todos os outros nós no gráfico.
Como resultado da execução do algoritmo de Dijkstra em um gráfico, obtemos a árvore de caminho mais curto (SPT) com o vértice de origem como raiz.
No algoritmo de Dijkstra, mantemos dois conjuntos ou listas. Um contém os vértices que fazem parte da árvore de caminho mais curto (SPT) e o outro contém os vértices que estão sendo avaliados para serem incluídos no SPT. Portanto, para cada iteração, encontramos um vértice da segunda lista que possui o caminho mais curto.
O pseudocódigo para o algoritmo de caminho mais curto de Dijkstra é fornecido abaixo.
como abrir arquivo .dat no mac
Pseudo-código
A seguir está o pseudocódigo para este algoritmo.
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 Vamos agora pegar um gráfico de amostra e ilustrar o algoritmo de caminho mais curto de Dijkstra .
Inicialmente, o conjunto SPT (Shortest Path Tree) é definido como infinito.
Vamos começar com o vértice 0. Então, para começar, colocamos o vértice 0 em sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
A seguir, com o vértice 0 em sptSet, exploraremos seus vizinhos. Os vértices 1 e 2 são dois nós adjacentes de 0 com distância 2 e 1, respectivamente.
Na figura acima, também atualizamos cada vértice adjacente (1 e 2) com suas respectivas distâncias do vértice de origem 0. Agora vemos que o vértice 2 tem uma distância mínima. A seguir, adicionamos o vértice 2 ao sptSet. Além disso, exploramos os vizinhos do vértice 2.
Agora procuramos os vértices com distância mínima e aqueles que não existem em spt. Escolhemos o vértice 1 com a distância 2.
Como vemos na figura acima, de todos os nós adjacentes de 2, 0 e 1 já estão em sptSet, portanto, os ignoramos. Dos nós adjacentes 5 e 3, 5 têm o menor custo. Então, nós o adicionamos ao sptSet e exploramos seus nós adjacentes.
Na figura acima, vemos que, exceto para os nós 3 e 4, todos os outros nós estão em sptSet. De 3 e 4, o nó 3 tem o menor custo. Então, colocamos em sptSet.
Como mostrado acima, agora temos apenas um vértice restante, ou seja, 4 e sua distância do nó raiz é 16. Finalmente, colocamos em sptSet para obter o sptSet final = {0, 2, 1, 5, 3, 4} que nos dá a distância de cada vértice do nó de origem 0.
Implementação do algoritmo de Dijkstra em Java
A implementação do algoritmo de caminho mais curto de Dijkstra em Java pode ser realizada de duas maneiras. Podemos usar filas de prioridade e lista de adjacência ou podemos usar matrizes e matrizes de adjacência.
Nesta seção, veremos ambas as implementações.
Usando uma fila prioritária
Nesta implementação, usamos a fila de prioridade para armazenar os vértices com a distância mais curta. O gráfico é definido usando a lista de adjacências. Um programa de amostra é mostrado abaixo.
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 Resultado:
Usando Matriz de Adjacência
Nesta abordagem, usamos a matriz de adjacência para representar o grafo. Para o conjunto de spt, usamos arrays.
O programa a seguir mostra essa implementação.
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 Resultado:
perguntas frequentes
P # 1) Dijkstra funciona para gráficos não direcionados?
Responda: Se o gráfico é direcionado ou não direcionado, não importa no caso do algoritmo de Dijkstra. Este algoritmo se preocupa apenas com os vértices do gráfico e os pesos.
Q # 2) Qual é a complexidade de tempo do algoritmo de Dijkstra?
Responda: A complexidade de tempo do algoritmo de Dijkstra é O (V 2). Quando implementado com a fila de prioridade mínima, a complexidade de tempo desse algoritmo se reduz a O (V + E l o g V).
P # 3) Dijkstra é um algoritmo ganancioso?
Responda: Sim, Dijkstra é um algoritmo ganancioso. Semelhante ao algoritmo de Prim para encontrar a árvore geradora mínima (MST), esses algoritmos também começam a partir de um vértice raiz e sempre escolhe o vértice mais ideal com o caminho mínimo.
P # 4) O Dijkstra é DFS ou BFS?
Responda: Não é nenhum. Mas, como o algoritmo de Dijkstra usa uma fila de prioridade para sua implementação, ele pode ser visto como próximo ao BFS.
Q # 5) Onde o algoritmo de Dijkstra é usado?
Responda: É usado principalmente em protocolos de roteamento, pois ajuda a encontrar o caminho mais curto de um nó para outro.
Conclusão
Neste tutorial, discutimos o algoritmo de Dijkstra. Usamos esse algoritmo para encontrar o caminho mais curto do nó raiz para os outros nós no gráfico ou árvore.
Normalmente implementamos o algoritmo de Dijkstra usando uma fila de prioridade, pois temos que encontrar o caminho mínimo. Também podemos implementar este algoritmo usando a matriz de adjacência. Discutimos essas duas abordagens neste tutorial.
Esperamos que você considere este tutorial útil.
=> Visite aqui para ver a série de treinamento Java para todos
Leitura recomendada
- Algoritmo de pesquisa binária em Java - implementação e exemplos
- Bubble Sort In Java - Algoritmos de classificação Java e exemplos de código
- Insertion Sort In Java - Insertion Sort Algorithm & Exemplos
- Classificação de seleção em Java - Algoritmo de classificação de seleção e exemplos
- QuickSort em Java - Algoritmo, ilustração e implementação
- Tutorial JAVA para iniciantes: mais de 100 tutoriais práticos em vídeo Java
- Tutorial de reflexão Java com exemplos
- Jagged Array In Java - Tutorial com exemplos
