Friday, March 25, 2011

Suratku Untukmu (Djikstra Algorithm)

Posted by in
<html> <head> <title>Dijkstra Algorithms</title> </head> <body> <script language = "javascript"> <!-- var nilaiacuan = 10000; var takterdefinisi = -1; var namaverteks = new Array("A","B","C","D","E","F"); var matriks = new Array(6); function bobot(a,b) { return matriks[a][b]; } function dijkstra(jumlahverteks,awal,d) { var posisi = new Array(jumlahverteks); var i; var kunjungan = new Array(jumlahverteks); var sebelum = new Array(jumlahverteks); for(i=0;i<jumlahverteks;i++) { posisi[i] = nilaiacuan; sebelum[i] = takterdefinisi; kunjungan[i] = false; } posisi[awal]=0; var verteks; for(verteks=0;verteks<jumlahverteks;verteks++) { var jarakterpendek = nilaiacuan, berhenti = -1; for(i=0;i<jumlahverteks;i++) { if(!kunjungan[i]) { if(posisi[i] <= jarakterpendek) { jarakterpendek = posisi[i]; berhenti = i; } } } kunjungan[berhenti] = true; for(i=0;i<jumlahverteks;i++) { if(!kunjungan[i]) { var w = bobot(berhenti,i); if(posisi[berhenti]+w < posisi[i]) { posisi[i] = posisi[berhenti] + w; sebelum[i] = berhenti; } } } } i=d; if(posisi[i] < nilaiacuan) { var lintasan = namaverteks[i]; var verteks = i; while(verteks>0) { verteks = sebelum[verteks]; if(verteks>=0) lintasan = namaverteks[verteks] + '->' + lintasan; } alert("Jarak : "+posisi[i]+' ('+lintasan+')'+'<br>'); } else { alert("Tidak ada jalur"); } } function init() { var x = nilaiacuan; document.write('<pre>'); document.write('<br>'); document.write(matriks[0] = new Array(0,2,3,x,x,x)); document.write('<br>'); document.write(matriks[1] = new Array(2,0,3,6,x,x)); document.write('<br>'); document.write(matriks[2] = new Array(3,3,0,3,5,x)); document.write('<br>'); document.write(matriks[3] = new Array(x,6,3,0,1,3)); document.write('<br>'); document.write(matriks[4] = new Array(x,x,5,1,0,1)); document.write('<br>'); document.write(matriks[5] = new Array(x,x,x,3,1,0)); document.write('<br>'); document.write('</pre>'); var awal='<pre>'; document.write(awal+'A--2-B--6--D--3-F'+'<br>'); document.write(' \\ | / | / '+'<br>'); document.write(' 3 3 3 1 1 '+'<br>'); document.write(' \\ | / | / '+'<br>'); document.write(' \\|/ |/'+'<br>'); document.write(' C--5--E'+'<br>'); document.write('</pre>'); } init(); var dari=0; var ke=5; dijkstra(matriks.length,dari,ke); //--> </script> </body> </html> <head>Dijkstra Algorithms </title> </head> <body> <script language = "javascript"> var NilaiAcuan = 10000; var TakTerdefinisi = -1; var NamaVerteks = new Array ('A','B','C','D','E','F'); var Matriks = new Array (6); function bobot (a,b) { return matriks[a][b]; } function Dijkstra (JumlahVerteks,awal,d) { var posisi = new Array(JumlahVerteks); var i; var Kunjungan = new Array(JumlahVerteks); var Sebelum = new Array(JumlahVerteks); for (i = 0; i < JumlahVerteks; i++) { posisi[i] = NilaiAcuan; Sebelum[i] = TakTerdefinisi; Kunjungan[i] = false; } posisi [awal] = 0; var Verteks; for (Verteks=0; Verteks < JumlahVerteks; Verteks++) { var JarakTerpendek = NilaiAcuan;, Berhenti = -1; for (i=0; i < JumlahVerteks; i++) { if(!Kunjungan[i]) { if (Posisi[i] <= JarakTerpendek) { JarakTerpendek = Posisi[i]; Berhenti = i; } } Kunjungan[Berhenti] = true; for (i=0; i < JumlahVerteks; i++) { if (!Kunjungan[i]) { var w = Bobot(Berhenti, i); if (Posisi[Berhenti] + w < Posisi [i]) { Posisi[i] = Posisi[Berhenti] + w; Sebelum[i] = Berhenti; } } } } i=d; if (Posisi[i] < NilaiAcuan) { var Lintasan = NamaVerteks[i]; var Verteks = i; while (Verteks>0) { Verteks = Sebelum[Verteks]; if (Verteks >= 0) Lintasan = NamaVerteks [Verteks] + '->' + Lintasan; { message("Jarak :" + Posisi[i]+ (+Lintasan+) + <br>); }else { message("Tidak Ada Jalur"); } } function init () { var x = NilaiAcuan; Matriks[0]=new Array (0,2,3,x,x,x) Matriks[0]=new Array (2,0,3,6,x,x) Matriks[0]=new Array (3,3,0,3,5,x) Matriks[0]=new Array (x,6,3,0,1,3) Matriks[0]=new Array (x,x,5,1,0,1) Matriks[0]=new Array (0,2,3,x,x,x) Matriks[0]=new Array (x,x,x,3,1,0) var Awal = '<pre>' Awal = Awal +'A--2-B-6--D--3-F'+("<br>") Awal = Awal +'\ | /| /'+("<br>") Awal = Awal +' 3 3 31 1'+("<br>") Awal = Awal +' \ | / | / '+("<br>") Awal = Awal +' \ | / | / '+"(<br>") Awal = Awal +' \ | / | / '+("<br>") Awal = Awal +' C--5-E '+("<br>") Awal = Awal +'</pre>' message (Awal.replace (/(\d)+/g, '<font color="red">$1</font>')); } init() var Dari = 0; // A var Ke =5; // F Dijkstra (Matriks.length,Dari,Ke); //--> </script> </body> </html>

2 comments:

Tinggalkan Komentar Disini

© Copyright Dirtyfoo