Newsgroup: it.comp.lang.javascript
Titolo: Java+algoritmo di DiJkstra

Salve, chi ha già implementato questo algoritmo in Java?
Mi serve per realizzare un esame in cui è richiesto di pianificare un
viaggio al costo minimo.
Grazie
Rispondetemi a 
mbian...@crema.unimi.it
-- 
Posted from 
ganimede.crema.unimi.it
 [159.149.70.3] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 ha scritto nel messaggio
news:1D450DC91ADCD411B0D...@ganimede.crema.unimi.it...
Salve, chi ha già implementato questo algoritmo in Java?
Mi serve per realizzare un esame in cui è richiesto di pianificare un
viaggio al costo minimo.
Grazie
chiedi su  it.comp.lang.java
--
andreotta fabiano
WebMªster ATI POWER s.n.c.
andr...@atipower.it
http://www.aticommerce.com
  (new)
http://www.atipower.it
http://www.jsdir.com
http://www.dxml.it
  (u.c.)

chiedi su  it.comp.lang.java
meglio it.comp.programmazione, 
e' un algoritmo indipendente dal sistema operativo... se non hai fretta
e vuoi imparare a programmare comprati il Cormen.
Dopotutto e' solo la rielaborazione di una matrice :-(
ciao
-- 
Antonello Pasella 
studente di Ing.Informatica al Politecnico di Torino
Attualmente svolgo attivita' di formazione professionale

 ha scritto nel messaggio
news:1D450DC91ADCD411B0D...@ganimede.crema.unimi.it...
Salve, chi ha già implementato questo algoritmo in Java?
Mi serve per realizzare un esame in cui è richiesto di pianificare un
viaggio al costo minimo.
--------------
Non sono certo dell'attinenza ma non ho trovato sufficienti informazioni
sull'algoritmo.
Comunque di seguito un codice che trova il percorso piu' breve tra x
nodi con il numero minimo (almeno mi pare) di iterazioni.
Saluti, Paolo
<HTML><HEAD><TITLE>Trova percorso</TITLE>
</HEAD>
<script>
function oStrade (loc1,loc2,nome,dist){
 this.loc1=loc1;
 this.loc2=loc2;
 this.nome=nome;
 this.dist=dist;
}
aStrade= new Array;
aStrade[0]= new oStrade('Milano','Rho','S33-1',15.3);
aStrade[1]= new oStrade('Rho','Nerviano','S33-2',6.8);
aStrade[2]= new oStrade('Nerviano','Legnano','S33-3',6.5);
aStrade[3]= new oStrade('Legnano','Castellanza','S33-4',3.2);
aStrade[4]= new oStrade('Castellanza','Busto-Arsizio','S33-5',3.5);
aStrade[5]= new oStrade('Busto-Arsizio','Gallarate','S33-6',7.3);
aStrade[6]= new oStrade('Gallarate','Somma-Lombardo','S33-7',7.3);
aStrade[7]= new oStrade('Somma-Lombardo','Vergiate','S33-8',5.1);
aStrade[8]= new oStrade('Vergiate','Sesto-Calende','S33-9',4.6);
aStrade[9]= new oStrade('Milano','Legnano','A8-1',27.2);
aStrade[10]= new oStrade('Legnano','Castellanza','A8-2',1.7);
aStrade[11]= new oStrade('Castellanza','Busto-Arsizio','A8-3',6.7);
aStrade[12]= new oStrade('Busto-Arsizio','Gallarate','A8-4',6.6);
aStrade[13]= new oStrade('Gallarate','Vergiate','A26-1',13.8);
aStrade[14]= new oStrade('Gallarate','Novara','pippo',40.8);
// aStrade[15]= new oStrade('Rho','Vergiate','MAGARI',13.8);
function oLocalita (nome){
 this.nome=nome;
 this.etichetta=null;
 }
 aLocalita= new Array;
 for (str in aStrade){
  if (!aLocalita[aStrade[str].loc1]) aLocalita[aStrade[str].loc1]= new
oLocalita(aStrade[str].loc1);
  if (!aLocalita[aStrade[str].loc2]) aLocalita[aStrade[str].loc2]= new
oLocalita(aStrade[str].loc2);
 }
function fPopLoc(){
 for (lc in aLocalita)aLocalita[lc].etichetta=null;
}
fPopLoc();
function calcola(oForm){
 partenza=oForm.part.options[oForm.part.selectedIndex].value;
 arrivo=oForm.arr.options[oForm.arr.selectedIndex].value;
 if (partenza=="" || arrivo=="") return
 if (partenza==arrivo) return
 num_nodi=0;
 percorsi= new Array;
 num_perc=0;
 for (str in aStrade) {
  var loc_attuale=partenza
  if (aStrade[str].loc1==loc_attuale || aStrade[str].loc2==loc_attuale){
   var locP=(aStrade[str].loc1==loc_attuale)?
aStrade[str].loc1:aStrade[str].loc2;
   var locA=(aStrade[str].loc1!=loc_attuale)?
aStrade[str].loc1:aStrade[str].loc2;
   percorsi[num_perc]= new Array(0,locP);
   percorsi[num_perc][0]=aStrade[str].dist;
percorsi[num_perc][percorsi[num_perc].length]=aStrade[str].nome+'*'+aStr
ade[str].dist+'*';
   percorsi[num_perc][percorsi[num_perc].length]=locA;
   if(!aLocalita[locA].etichetta ||
aLocalita[locA].etichetta>percorsi[num_perc][0]){
    aLocalita[locA].etichetta=percorsi[num_perc][0];
    if (locA!=arrivo) controllaNodi(percorsi[num_perc],num_perc);
   }
// document.form1.textarea1.value +='ctr
'+percorsi[num_perc].toString()+' '+aLocalita[locA].etichetta+'\n'
   num_perc++;
  }
 }
 distMin=100000;
 percorsoMin='manca';
 cont=1;
 document.form1.textarea1.value += "Percorsi completati\n"
 for (i=0; i<percorsi.length;i++){
  km=0;
  if (percorsi[i][percorsi[i].length-1]==arrivo) {
   km=percorsi[i][0];
   document.form1.textarea1.value += "Perc"+cont+'('+i+'): ' +
percorsi[i].toString()+' Distanza km. '+ km+'\n';
   cont++
   if (km<distMin) {distMin=km; percorsoMin="Perc"+cont+'('+i+'): ' +
percorsi[i].toString()+' Distanza km. '+ km;}
  }
 }
 document.form1.textarea1.value += '---------------------------------\n'
 document.form1.textarea1.value +=percorsoMin;
 document.form1.textarea1.value += '---------------------------------\n'
}
function controllaNodi(obj,nPer){
 var obj1= new Array()
 for (i=0; i<obj.length;i++){
  obj1[i]=obj[i]
 }
// document.form1.textarea1.value +='P'+nPer+': '+ obj.toString()+'\n'
 var loc_attuale=obj1[obj1.length-1];
 var nuovoArray=false;
 for (str in aStrade) {
  var locP=(aStrade[str].loc1==loc_attuale)?
aStrade[str].loc1:aStrade[str].loc2;
  var locA=(aStrade[str].loc1!=loc_attuale)?
aStrade[str].loc1:aStrade[str].loc2;
  if (obj1.toString().indexOf(locP)>=0 &&
obj1.toString().indexOf(locA)>=0){ 
   salta=true;
  } else {
    if (locP==loc_attuale || locA==loc_attuale){
     if (nuovoArray) {
      num_perc++;
      percorsi[num_perc]= new Array();
      for (i=0; i<obj1.length;i++){
       percorsi[num_perc][i]=obj1[i]
      }
     }
     nuovoArray=true;
     percorsi[num_perc][0]= (percorsi[num_perc][0]*10+aStrade[str].dist*10)/10;
     percorsi[num_perc][percorsi[num_perc].length]=aStrade[str].nome+'*'+aStrade[str].dist+'*';
     percorsi[num_perc][percorsi[num_perc].length]=locA;
     if(!aLocalita[locA].etichetta || aLocalita[locA].etichetta>percorsi[num_perc][0]){
      aLocalita[locA].etichetta=percorsi[num_perc][0];
      if (locA!=arrivo)  controllaNodi(percorsi[num_perc],num_perc);
     }
    }
  }
 }
}
function init(){
 for (str in aLocalita) {
     var miaOption = new Option(aLocalita[str].nome,aLocalita[str].nome);
     var miaOption1 = new Option(aLocalita[str].nome,aLocalita[str].nome);
 
  document.form2.part.options[document.form2.part.options.length]=miaOption;
  document.form2.arr.options[document.form2.arr.options.length]=miaOption1;
 }
}
// -->
</SCRIPT>
</head>
<body onLoad="init()">
<FORM action="" method=POST name=form2>
Partenza: <SELECT size=5 name=part ><option value="" selected>-----------------</option></SELECT>
Arrivo: <SELECT size=5 name=arr><option value="" selected>-----------------</option></SELECT>
<INPUT type="button" value="Percorso minimo" name=button1 onClick="document.forms['form1'].textarea1.value='';fPopLoc();calcola(this.form)"><br>
</form>
<FORM action
="" method=POST name=form1>
<TEXTAREA rows=20 cols=85 name=textarea1 wrap=off></TEXTAREA>
</FORM>
</BODY>
</HTML>

viaggio al costo minimo.
Se ancora ti serve.
Nell'implementazione ho utilizzato una proprieta' del nodo per definire
lo stato di Visitato o Frontiera; non e' complicato, eventualmente, fare
la modifica e popolare 2 vettori.
Saluti, Paolo
--------------
<script language="javascript">
 // vettore distanze
 function oStrade (loc1,loc2,nome,dist){
  this.loc1=loc1;
  this.loc2=loc2;
  this.nome=nome;
  this.dist=dist;
 }
 aStrade= new Array;
 cc=0;
 aStrade[cc++]  = new oStrade('Milano','Rho','S33-1',15.3);
 aStrade[cc++]= new oStrade('Rho','Nerviano','S33-2',6.8);
 aStrade[cc++]= new oStrade('Nerviano','Legnano','S33-3',6.5);
// aStrade[cc++]= new oStrade('Legnano','Castellanza','S33-4',3.2);
 aStrade[cc++]= new oStrade('Castellanza','Busto-Arsizio','S33-5',3.5);
 aStrade[cc++]= new oStrade('Busto-Arsizio','Gallarate','S33-6',7.3);
 aStrade[cc++]= new oStrade('Gallarate','Somma-Lombardo','S33-7',7.3);
 aStrade[cc++]= new oStrade('Somma-Lombardo','Vergiate','S33-8',5.1);
 aStrade[cc++]= new oStrade('Vergiate','Sesto-Calende','S33-9',4.6);
 aStrade[cc++]= new oStrade('Milano','Legnano','A8-1',27.2);
// aStrade[cc++]= new oStrade('Legnano','Castellanza','A8-2',1.7);
 aStrade[cc++]= new oStrade('Castellanza','Busto-Arsizio','A8-3',6.7);
 aStrade[cc++]= new oStrade('Busto-Arsizio','Gallarate','A8-4',6.6);
 aStrade[cc++]= new oStrade('Gallarate','Vergiate','A26-1',13.8);
 aStrade[cc++]= new oStrade('Gallarate','Novara','pippo',40.8);
// aStrade[cc++]= new oStrade('Rho','Vergiate','MAGARI',13.8);
 // totalita' nodi
 function oLocalita (nome){
  this.nome=nome;
  this.etichetta=100000;  // somma archi da partenza
  this.id_loc=null;  // localita' adiacente chiamante
  this.etichetta_stato=null; // posizione della localita' nell'insieme
         // vis= sottoinsieme Visitato
         // fro= sottoinsieme frontiera (adiacenti)
  this.stra_prec=null; // in questa situazione per la sdrada utilizzata
 }
 aLocalita= new Array;
 for (str in aStrade){
  if (!aLocalita[aStrade[str].loc1]) aLocalita[aStrade[str].loc1]= new
oLocalita(aStrade[str].loc1);
  if (!aLocalita[aStrade[str].loc2]) aLocalita[aStrade[str].loc2]= new
oLocalita(aStrade[str].loc2);
 }
 aLocalita=aLocalita.sort();
 // definizione nodi partenza e arrivo
 function calcola(oForm){
  partenza=oForm.part.options[oForm.part.selectedIndex].value;
  arrivo=oForm.arr.options[oForm.arr.selectedIndex].value;
  if (partenza=="" || arrivo=="" || partenza==arrivo) return
  aLocalita[partenza].etichetta_stato='fro';
  aLocalita[partenza].etichetta=0;
  vTrovato=calcola1();
  // nel caso di un nodo 'arrivo' non collegato
  if (!vTrovato) {document.form1.textarea1.value +='nodo non
raggiungibile-percorso inesistente';return;}
  vDistPrec=aLocalita[arrivo].etichetta;
  vPercorso=arrivo+' Dist: '+vDistPrec;
  fPercorso(arrivo);
  document.form1.textarea1.value +=vPercorso+'\n'
  return
 }
 // implementazione algoritmo di Dijkstra
 function calcola1(){
  dMin=100000;
  var loc_attuale=''
  for (loc in aLocalita){
   if (aLocalita[loc].etichetta_stato=='fro' &&
aLocalita[loc].etichetta<dMin){
    dMin=aLocalita[loc].etichetta;
    loc_attuale=loc;
   }
  }
  if (loc_attuale=='') {return false};
  aLocalita[loc_attuale].etichetta_stato='vis';
  if (aLocalita[loc_attuale].nome==arrivo) return true;
  for (str=0; str<aStrade.length;str++){
   if (aStrade[str].loc1==loc_attuale ||
aStrade[str].loc2==loc_attuale){
    var locA=(aStrade[str].loc1!=loc_attuale)?
aStrade[str].loc1:aStrade[str].loc2;
//    if (!aLocalita[locA].etichetta_stato){  // non controlla se archi
multipli
    if (aLocalita[locA].etichetta_stato!='vis'){ file://con controllo
archi multipli
     aLocalita[locA].etichetta_stato='fro';
     ctrEti=aLocalita[locA].etichetta;
     aLocalita[locA].etichetta=
Math.min(ctrEti,(aLocalita[loc_attuale].etichetta*10+aStrade[str].dist*1
0)/10);
     if (aLocalita[locA].etichetta!=ctrEti){
      aLocalita[locA].id_loc= loc_attuale;
      aLocalita[locA].stra_prec=aStrade[str].nome;
     }
    }
   }
  }
  var vTrovata=calcola1()
  return vTrovata;
 }
 // visualizza il percorso nella area di testo
 function fPercorso(perc){
  if (perc==partenza) return
  var
vDist=(vDistPrec*10-aLocalita[aLocalita[perc].id_loc].etichetta*10)/10;
  vDistPrec=aLocalita[aLocalita[perc].id_loc].etichetta;
  vPercorso=aLocalita[perc].id_loc+'-('+aLocalita[perc].stra_prec+'
km.'+vDist+')->'+vPercorso;;
document.form1.textarea1.value +=aLocalita[perc].nome+' '+vDist+'
'+aLocalita[perc].id_loc+' '+aLocalita[perc].etichetta+'\n'
  fPercorso(aLocalita[perc].id_loc)
 }
 // riporto allo stato iniziale degli oggetti localita' per nuovo ciclo
 function fPopLoc(){
  for (lc in aLocalita){
   aLocalita[lc].etichetta=100000;
   aLocalita[lc].etichetta=100000;
   aLocalita[lc].id_loc=null;
   aLocalita[lc].etichetta_stato=null;
   aLocalita[lc].stra_prec=null;
  }
 }
 fPopLoc();
 // popolamento opzioni form
 function init(){
  for (str in aLocalita) {
      var miaOption = new
Option(aLocalita[str].nome,aLocalita[str].nome);
      var miaOption1 = new
Option(aLocalita[str].nome,aLocalita[str].nome);
document.form2.part.options[document.form2.part.options.length]=miaOptio
n;
document.form2.arr.options[document.form2.arr.options.length]=miaOption1
;
  }
 }
</script>
</head>
<body onLoad="init()">
<FORM action="" method=POST name=form2>
Partenza: <SELECT size=5 name=part ><option value=""
selected>-----------------</option></SELECT>
Arrivo: <SELECT size=5 name=arr><option value=""
selected>-----------------</option></SELECT>
<INPUT type="button" value="Percorso minimo" name=button1
onClick="document.forms['form1'].textarea1.value='';fPopLoc();calcola(th
is.form)"><br>
</form>
<FORM action="" method=POST name=form1>
<TEXTAREA rows=15 cols=85 name=textarea1 wrap=off></TEXTAREA>
</FORM>
-----------------------