Este artigo apresenta o algoritmo Dijkstra baseado em Java na forma de exemplos. Acredito que será útil para os leitores no estudo e aprendizagem de algoritmos de domínio de estrutura de dados.
Dijkstra propôs um algoritmo para gerar o caminho mais curto para cada vértice em ordem crescente do comprimento do caminho entre cada vértice e o ponto de origem v. Ou seja, primeiro encontre o caminho mais curto com o comprimento mais curto e, em seguida, use-o para encontrar o caminho mais curto com o próximo comprimento mais curto e assim por diante, até que todos os caminhos mais curtos do ponto de origem v até outros vértices sejam encontrados.
A implementação do código é a seguinte:
package com.algorithm.impl; public class Dijkstra { private static int M = 10000; //Esta estrada está bloqueada public static void main(String[] args) { int[][] peso1 = {//Matriz de adjacência {0, 3,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] peso2 = {{0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("A distância mais curta de "+start+" a "+i+" é: "+shortPath[i ] ); } public static int[] dijkstra(int[][] peso, int início) { //Aceita uma matriz de pesos de um gráfico direcionado e um número de ponto inicial start (numerado a partir de 0, o vértice é armazenado no array) //Retorna um array int[], indicando o comprimento do caminho mais curto do início até ele int n = peso.length ; //Número de vértices int[] shortPath = new int[n] //Salva o caminho mais curto do início para outros pontos String[] path = new String[n]; caminho do início até outros pontos Representação de string para (int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] visitado = new int[n] //Marca se é o caminho mais curto para o vértice atual; foi Find, 1 significa que foi encontrado //Inicialização, o primeiro vértice foi encontrado shortPath[start] = 0; visitado[start] = 1 for(int count = 1; count < n; count++) { //Para adicionar n-1 vértices int k = -1; //Selecione um vértice não marcado mais próximo do vértice inicial start int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited). [i] == 0 && peso[início][i] <dmin) { dmin = peso[início][i]; //Marca o vértice recém-selecionado como o caminho mais curto encontrado, e o caminho mais curto para começar é dmin shortPath[k] = dmin visitado[k] = 1; start to Distância de pontos não visitados for(int i = 0; i < n; i++) { if(visited[i] == 0 && peso[start][k] + peso[k][i] < peso[start] [eu]) { peso[início][i] = peso[início][k] + peso[k][i]; caminho[i] = caminho[k] + "-->" + i; 0; i < n; i++) { System.out.println("O caminho mais curto de "+start+" para "+i+" é: "+path[i]); System.out.println("==================================="); }}O resultado da execução deste programa é:
O caminho mais curto de 0 a 0 é: 0-->0 O caminho mais curto de 0 a 1 é: 0-->1 O caminho mais curto de 0 a 2 é: 0-->3-->2 de O caminho mais curto de 0 a 3 é: 0-->3 O caminho mais curto de 0 a 4 é: 0-->3-->2-->4==== ================================= A distância mais curta de 0 a 0 é: 0 de 0 a 1 A distância mais curta de 0 a 2 é: 50 A distância mais curta de 0 a 3 é: 30 A distância mais curta de 0 a 4 é: 60