oi pessoal estou com dúvida nas seguintes linha, o meu código não mostra os resultados, não estou conseguindo:
o erro está nas duas linhas selecionadas abaixo:
ao executar ele não mostra a melhor rota pra chegar as cidades
import java.util.ArrayList;
import java.util.Scanner;
public class Mapa {
public static void inicializacao(Grafo g, Caminho c) {
c.predecessores = new int[g.vertices.size()];
c.distancias = new int[g.vertices.size()];
for(int i = 0; i < g.vertices.size(); i++){
g.vertices.get(i).cor = “branco”;
c.distancias[i] = Integer.MAX_VALUE;
c.predecessores[i] = -1;
}
}
public static boolean temBranco(Grafo g) {
for(int i = 0; i < g.vertices.size(); i++){
if(g.vertices.get(i).cor.equals("branco")){
return true;
}
}
return false;
}
public static int obtemMinimo(Grafo g, Caminho c) {
int pos = -1;
int min = Integer.MAX_VALUE;
for(int i = 0; i < c.distancias.length; i++){
if(g.vertices.get(i).cor.equals("branco")){
if(c.distancias[i] < min){
min = c.distancias[i];
pos = i;
}
}
}
return pos;
}
public static void relaxamento(Caminho c, Vertice atual, int i) {
int rotuloVizinho = atual.vizinhos.get(i);
int arestaVizinho = atual.arestas.get(i);
if(c.distancias[rotuloVizinho] > c.distancias[atual.valor] + arestaVizinho){
c.distancias[rotuloVizinho] = c.distancias[atual.valor] + arestaVizinho;
c.predecessores[rotuloVizinho] = atual.valor;
}
}
public static Caminho dijkstra(Grafo g, int valorInicio){
Caminho c = new Caminho();
inicializacao(g, c);
c.distancias[valorInicio] = 0;
while(temBranco(g)){
int pos = obtemMinimo(g, c);
Vertice atual = g.vertices.get(pos);
atual.cor = "cinza";
for(int i = 0; i < atual.vizinhos.size(); i++){
relaxamento(c, atual, i);
}
}
return c;
}
public static String caminho(Caminho c, int inicio, int fim){
String saida = "";
int aux = fim;
while(true){
if(aux == inicio){
saida = aux + " "+ saida;
break;
}
if(c.predecessores[aux] == -1){
saida = "Não existe caminho entre "+inicio+" e "+fim;
break;
}
saida = aux + " " + saida;
aux = c.predecessores[aux];
}
return saida;
}
/**/
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int opcao = 0;
while(opcao != 3){
System.out.println("---------- ESCOLHA UMA DAS OPÇÕES AMOSTRA ----------");
System.out.println(“1 - Abrir Menu Códigos de Cidades”);
System.out.println(“2 - Comparar Distância Mínima”);
System.out.println(“3 - Encerrar Programa”);
opcao = input.nextInt();
if (opcao == 1){
System.out.println("1 - Juazeiro do Norte");
System.out.println("2 - Barbalha");
System.out.println("3 - Crato");
System.out.println("4 - Missão Velha");
System.out.println("5 - Caririaçu");
System.out.println("6 - Jardim");
System.out.println("7 - Aurora");
System.out.println("8 - Milagres");
System.out.println("9 - Mauriti");
System.out.println("10 - Brejo Santo");
System.out.println("11 - Granjeiro");
System.out.println("12 - Farias Brito");
System.out.println("13 - Altaneira");
System.out.println("14 - Santa do Cariri");
System.out.println("15 - Nova Olinda");
System.out.println();
}
if (opcao == 2){
System.out.println("Digite o Código das Duas Cidades:");
input.nextInt();
int valor = input.nextInt();
Vertice x1 = new Vertice();
x1.valor = valor;
Vertice x2 = new Vertice();
x2.valor = valor;
Vertice x3 = new Vertice();
x3.valor = valor;
Vertice x4 = new Vertice();
x4.valor = valor;
Vertice x5 = new Vertice();
x5.valor = valor;
Vertice x6 = new Vertice();
x6.valor = valor;
Vertice x7 = new Vertice();
x7.valor = valor;
Vertice x8 = new Vertice();
x8.valor = valor;
Vertice x9 = new Vertice();
x9.valor = valor;
Vertice x10 = new Vertice();
x10.valor = valor;
Vertice x11 = new Vertice();
x11.valor = valor;
Vertice x12 = new Vertice();
x12.valor = valor;
Vertice x13 = new Vertice();
x13.valor = valor;
Vertice x14 = new Vertice();
x14.valor = valor;
Vertice x15 = new Vertice();
x15.valor = valor;
Grafo g = new Grafo();
g.vertices.add(x1);
g.vertices.add(x2);
g.vertices.add(x3);
g.vertices.add(x4);
g.vertices.add(x5);
g.vertices.add(x6);
g.vertices.add(x7);
g.vertices.add(x8);
g.vertices.add(x9);
g.vertices.add(x10);
g.vertices.add(x11);
g.vertices.add(x12);
g.vertices.add(x13);
g.vertices.add(x14);
g.vertices.add(x15);
x1.nome = "Juazeiro do Norte";
x2.nome = "Barbalha";
x3.nome = "Crato";
x4.nome = "Missão Velha";
x5.nome = "Caririaçu";
x6.nome = "Jardim";
x7.nome = "Aurora";
x8.nome = "Milagres";
x9.nome = "Mauriti";
x10.nome = "Brejo Santo";
x11.nome = "Granjeiro";
x12.nome = "Farias Brito";
x13.nome = "Altaneira";
x14.nome = "Santa do Cariri";
x15.nome = "Nova Olinda";
x1.vizinhos.add(2);
x1.vizinhos.add(3);
x1.vizinhos.add(5);
x1.arestas.add(15);
x1.arestas.add(12);
x1.arestas.add(27);
x2.vizinhos.add(1);
x2.vizinhos.add(3);
x2.vizinhos.add(4);
x2.vizinhos.add(6);
x2.arestas.add(15);
x2.arestas.add(23);
x2.arestas.add(22);
x2.arestas.add(37);
x3.vizinhos.add(1);
x3.vizinhos.add(2);
x3.vizinhos.add(12);
x3.vizinhos.add(15);
x3.arestas.add(12);
x3.arestas.add(21);
x3.arestas.add(45);
x3.arestas.add(38);
x4.vizinhos.add(2);
x4.vizinhos.add(7);
x4.vizinhos.add(8);
x4.arestas.add(22);
x4.arestas.add(41);
x4.arestas.add(32);
x5.vizinhos.add(1);
x5.vizinhos.add(11);
x5.arestas.add(27);
x5.arestas.add(28);
x6.vizinhos.add(2);
x6.vizinhos.add(10);
x6.arestas.add(37);
x6.arestas.add(49);
x7.vizinhos.add(4);
x7.vizinhos.add(8);
x7.vizinhos.add(9);
x7.vizinhos.add(11);
x7.arestas.add(41);
x7.arestas.add(70);
x7.arestas.add(83);
x7.arestas.add(42);
x8.vizinhos.add(4);
x8.vizinhos.add(7);
x8.vizinhos.add(9);
x8.vizinhos.add(10);
x8.arestas.add(32);
x8.arestas.add(70);
x8.arestas.add(28);
x8.arestas.add(22);
x9.vizinhos.add(7);
x9.vizinhos.add(8);
x9.vizinhos.add(10);
x9.arestas.add(83);
x9.arestas.add(28);
x9.arestas.add(27);
x10.vizinhos.add(6);
x10.vizinhos.add(8);
x10.vizinhos.add(9);
x10.arestas.add(22);
x10.arestas.add(49);
x10.arestas.add(27);
x11.vizinhos.add(5);
x11.vizinhos.add(11);
x11.arestas.add(28);
x11.arestas.add(42);
x12.vizinhos.add(3);
x12.vizinhos.add(13);
x12.vizinhos.add(15);
x12.arestas.add(45);
x12.arestas.add(23);
x12.arestas.add(23);
x13.vizinhos.add(12);
x13.vizinhos.add(15);
x13.arestas.add(23);
x13.arestas.add(13);
x14.vizinhos.add(15);
x14.arestas.add(13);
x15.vizinhos.add(3);
x15.vizinhos.add(12);
x15.vizinhos.add(13);
x15.vizinhos.add(14);
x15.arestas.add(38);
x15.arestas.add(23);
x15.arestas.add(13);
x15.arestas.add(13);
System.out.println();
[size=18] System.out.println("Distância Mínima Entre as Cidades:"); [b]//falta código para calcular e mostrar o resultado[/b][u]
System.out.println("A Rota a se Seguir é: "); [b]//falta código para calcular e mostrar e mostrar os resultados[/b][/u][/size]
}
if (opcao == 3){
System.out.println(“Programa Encerrado!”);
}
}
}
}
/**/
class Grafo{
ArrayList vertices = new ArrayList();
}
class Vertice{
int valor;
String cor;
String nome;
ArrayList vizinhos = new ArrayList();
ArrayList arestas = new ArrayList();
}
class Caminho{
int[] predecessores;
int[] distancias;
}