Dijkstra
30/11/2015
0
package Dijkstra;
public class A_Dijkistra {
public static void main (String[]args){
Dijkstra d = new Dijkstra();
d.quantosPontos(5);
d.pegaDados(1, 5, 14);
d.pegaDados(1, 2, 2);
d.pegaDados(1, 3, 7);
d.pegaDados(2, 3, 3);
d.pegaDados(2, 5, 10);
d.pegaDados(3, 4, 9);
d.pegaDados(3, 5, 4);
d.pegaDados(5, 4, 2);
d.mostraTabela();
d.percorreCaminho();
d.mostraCaminhoMin();
}
}
2codigo classe.
package Dijkstra;
public class Dijkstra {
private int[][] arrayDikis;
private int minimo;
private int pesoPassado;
private int[] Estimativa;
private int[] Precedente;
private char[] Estado;
private int peso;
private int posicao=1;
public void quantosPontos(int quantidade) {
int[][] arrayDikis = new int[quantidade][quantidade];
this.arrayDikis = arrayDikis;
int[] Estimativa = new int[quantidade];
this.Estimativa = Estimativa;
int[] Precedente = new int[quantidade];
this.Precedente = Precedente;
char[] Estado = new char[quantidade];
this.Estado = Estado;
for (int i = 0; i < Estado.length; i++) {
Estado[i] = 'a';
}
Estimativa[0] = 0;
Precedente[0] = 0;
Estado[0] = 'f';
}
public void pegaDados(int pPonto, int sPonto, int peso) {
arrayDikis[pPonto - 1][sPonto - 1] = peso;
arrayDikis[sPonto - 1][pPonto - 1] = peso;
}
public void percorreCaminho() {
for (int cont = 0; cont < arrayDikis.length; cont++) {
for (int conta = 0; conta < arrayDikis.length; conta++) {
if (arrayDikis[cont][conta] != 0) {
peso = arrayDikis[cont][conta];
if (Estado[conta] == 'a') {
Estimativa[conta] = peso + pesoPassado;
Precedente[conta] = posicao;
}
}
}
for (int i = 0; i < Estimativa.length; i++) {
for (int j = 0; j < Estimativa.length; j++) {
if (Estado[i] == 'a' && Estado[j] == 'a' && Estimativa[i] != 0 && Estimativa[j] != 0) {
if (Estimativa[i] < Estimativa[j]) {
if (Estimativa[i] <minimo || minimo==0) {
minimo=Estimativa[i];
pesoPassado = Estimativa[i];
posicao = i;
}
}
}
}
}
minimo=0;
if (posicao != 0) {
Estado[posicao] = 'f';
}
}
}
public void mostraCaminhoMin() {
System.out.println();
System.out.println();
System.out.println("o caminho minimo é :");
for (int i = 0; i < Estimativa.length; i++) {
System.out.print(Estimativa[i] + " \t ");
}
}
public void mostraTabela() {
for (int i = 0; i < arrayDikis.length; i++) {
System.out.println();
for (int j = 0; j < arrayDikis.length; j++) {
System.out.print(arrayDikis[i][j] + "\t");
}
}
}
}
alguem poderia me ajudar na implementação... desse codigo java..
public class A_Dijkistra {
public static void main (String[]args){
Dijkstra d = new Dijkstra();
d.quantosPontos(5);
d.pegaDados(1, 5, 14);
d.pegaDados(1, 2, 2);
d.pegaDados(1, 3, 7);
d.pegaDados(2, 3, 3);
d.pegaDados(2, 5, 10);
d.pegaDados(3, 4, 9);
d.pegaDados(3, 5, 4);
d.pegaDados(5, 4, 2);
d.mostraTabela();
d.percorreCaminho();
d.mostraCaminhoMin();
}
}
2codigo classe.
package Dijkstra;
public class Dijkstra {
private int[][] arrayDikis;
private int minimo;
private int pesoPassado;
private int[] Estimativa;
private int[] Precedente;
private char[] Estado;
private int peso;
private int posicao=1;
public void quantosPontos(int quantidade) {
int[][] arrayDikis = new int[quantidade][quantidade];
this.arrayDikis = arrayDikis;
int[] Estimativa = new int[quantidade];
this.Estimativa = Estimativa;
int[] Precedente = new int[quantidade];
this.Precedente = Precedente;
char[] Estado = new char[quantidade];
this.Estado = Estado;
for (int i = 0; i < Estado.length; i++) {
Estado[i] = 'a';
}
Estimativa[0] = 0;
Precedente[0] = 0;
Estado[0] = 'f';
}
public void pegaDados(int pPonto, int sPonto, int peso) {
arrayDikis[pPonto - 1][sPonto - 1] = peso;
arrayDikis[sPonto - 1][pPonto - 1] = peso;
}
public void percorreCaminho() {
for (int cont = 0; cont < arrayDikis.length; cont++) {
for (int conta = 0; conta < arrayDikis.length; conta++) {
if (arrayDikis[cont][conta] != 0) {
peso = arrayDikis[cont][conta];
if (Estado[conta] == 'a') {
Estimativa[conta] = peso + pesoPassado;
Precedente[conta] = posicao;
}
}
}
for (int i = 0; i < Estimativa.length; i++) {
for (int j = 0; j < Estimativa.length; j++) {
if (Estado[i] == 'a' && Estado[j] == 'a' && Estimativa[i] != 0 && Estimativa[j] != 0) {
if (Estimativa[i] < Estimativa[j]) {
if (Estimativa[i] <minimo || minimo==0) {
minimo=Estimativa[i];
pesoPassado = Estimativa[i];
posicao = i;
}
}
}
}
}
minimo=0;
if (posicao != 0) {
Estado[posicao] = 'f';
}
}
}
public void mostraCaminhoMin() {
System.out.println();
System.out.println();
System.out.println("o caminho minimo é :");
for (int i = 0; i < Estimativa.length; i++) {
System.out.print(Estimativa[i] + " \t ");
}
}
public void mostraTabela() {
for (int i = 0; i < arrayDikis.length; i++) {
System.out.println();
for (int j = 0; j < arrayDikis.length; j++) {
System.out.print(arrayDikis[i][j] + "\t");
}
}
}
}
alguem poderia me ajudar na implementação... desse codigo java..
Frodo F
Curtir tópico
+ 1
Responder
Clique aqui para fazer login e interagir na Comunidade :)