Prodig - Komunitas Proyek Digital
Selamat datang di ProDig!
Di sini adalah tempat untuk berbagi proyek (game, seni, program, dan situs).
Di sini Anda juga bisa mendapatkan hal lainnya seperti permainan, berbagi karya, ilmu pengetahuan, kesenangan, dan sebagainya. :)

Ayo daftar lalu langsung login tanpa perlu konfirmasi email sama sekali :D!
Prodig - Komunitas Proyek Digital

Tempat untuk berbagi proyek digital : Situs, Game, Seni, Program
 
CalendarPortalHomeRulesSearchFAQMemberlistUsergroupsRegisterLog in
Welcome to the ProDig, Guest!

 
 

 [GML] Dijkstra's Algorithm (Beta)

View previous topic View next topic Go down 
AuthorMessage
Alissa
Ngacay Princess


Status : Ngacay :v
Posts : 424
Chips : 4174
Power : 14
Join date : 2010-09-22
Location : Antara ada dan tiada :-
Badge :

PostSubject: [GML] Dijkstra's Algorithm (Beta)   
Sun Oct 24, 2010 11:34 pm


Overview:
 

Script: hapus
Code:
//hapus(ii)
ii=argument0
for(iii=1;iii<=nq;iii+=1){
  if(q[iii]==ii)
  iv=iii;
}
if(iv<=nq){
  if(iv<nq){
  for(iii=iv;iii<=nq-1;iii+=1){
    q[iii]=q[iii+1];
  }
  }
  nq=nq-1;
}

Script: ketemu
Code:
// ketemu(ii)
ii=argument0
ff=false;
for(iii=1;iii<=nq;iii+=1){
  if(q[iii]==ii)
  ff=true;
}
return ff;

Script: dijkstra
Code:
// dijkstra(s)
//where s is index of source vertex.
//
//Required data
//M[i,j]: Distance from vertex i to vertex j

 for(i=1;i<=n;i+=1){
  vertices_dist[i]=99999
  vertices_prev[i]=0
  q[i]=i
  nq=n
 }
 vertices_dist[s]=0;
 while(nq>0){
 
  d=vertices_dist[q[1]]
  u=q[1]
  if(nq>1){
  for(ii=2;ii<=nq;ii+=1){
  if(vertices_dist[q[ii]]<d){
    d=vertices_dist[q[ii]];
    u=q[ii];
  }
  }
  }

  if(vertices_dist[u]==99999) break;
  hapus(u);
  for(i=1;i<=n;i+=1){
  if(M[u,i]<99999 && M[u,i]>0){
    if(ketemu(i)){
    alt=vertices_dist[u]+M[u,i]
    if(alt<vertices_dist[i]){
      vertices_dist[i]=alt;
      vertices_prev[i]=u;
    }
    }
  }
  }
 }

Fungsi: mencari "jalan" terpendek menuju "titik" tujuan dari "titik" asal

Cara pemasangan:
- Buat tiga script baru, kasi nama hapus, ketemu, dan dijkstra
- Copas masing-masing bagian code di atas ke masing2 script tersebut
- Implementasikan script-script tersebut ke action Execute a piece of code. Namun matriks array (M) harus diinisialisasi datanya terlebih dahulu.

Contoh penggunaan script ini ada disini:
http://ifile.it/jnx6fkc/Dijkstra.gmk

Screenshot:
Spoiler:
 

Created by: Bunga Tepi Jalan

Credits
- http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

NB: Lihat konsep dan prinsip Algoritma Dijkstra di: http://ancuracademy.forumotion.net/programming-f13/programming-dijkstra-s-algorithm-t11.htm :kabur:
Script Algoritma Dijkstra versi bahasa Pascal: http://prodig.forumotion.net/pascal-f54/pascal-dijkstra-s-algorithm-t271.htm :kabur:





SIGGY KOSONG
Back to top Go down
View user profile https://bungatepijalan.wordpress.com
Alissa
Ngacay Princess


Status : Ngacay :v
Posts : 424
Chips : 4174
Power : 14
Join date : 2010-09-22
Location : Antara ada dan tiada :-
Badge :

PostSubject: Re: [GML] Dijkstra's Algorithm (Beta)   
Sun Nov 21, 2010 4:23 pm


Tambahan! :kabur:
Contoh penggunaan script ini, Dijkstra Graph Generator:
http://ifile.it/jnx6fkc/Dijkstra.gmk

Screenshot:
Spoiler:
 





SIGGY KOSONG
Back to top Go down
View user profile https://bungatepijalan.wordpress.com
 

[GML] Dijkstra's Algorithm (Beta)

View previous topic View next topic Back to top 
Page 1 of 1

Permissions in this forum:You cannot reply to topics in this forum
Prodig - Komunitas Proyek Digital  :: Education Chamber :: Programming :: GML-
Jump to: