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!

 
 

 [Programming] Dijkstra's Algorithm - Find Your Shortest Way

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


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

PostSubject: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 2:31 pm




Algoritma Dijkstra
Algoritma Dijkstra, yang ditemukan oleh ilmuwan komputer asal Belanda Edsger Dijkstra pada tahun 1956 dan dipublikasikan tahun 1959, adalah sebuah algoritma pencarian graf yang menyelesaikan persoalan jalan terpendek untuk suatu graf dengan jarak nonnegatif, menghasilkan suatu pohon jalan terpendek. Algoritma ini sering digunakan untuk mencari rute.

Untuk verteks (titik) sumber yang diberikan dalam graf, algoritma mencari jalan dengan jarak terpendek di antara verteks itu dan tiap verteks lain. Ini dapat pula digunakan untuk mencari jarak jalan terpendek dari verteks tunggal ke verteks tujuan tunggal dengan menghentikan algoritma sekali jalan terpendek ke tujuan telah ditentukan. Algoritma ini adalah sebagai berikut.
Algoritma RSA:
 

Pseudocode (Pseudopascal)
Dalam pseucode algoritma berikut ini, kode u := vertex in Q with smallest dist[] mencari verteks u dalam set verteks Q yang mempunyai nilai dist[u] terkecil.
Code:
 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:          // Initializations
 3          dist[v] := infinity ;              // Unknown distance function from source to v
 4          previous[v] := undefined ;        // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                    // Distance from source to source
 7      Q := the set of all nodes in Graph ;
        // All nodes in the graph are unoptimized - thus are in Q
 8      while Q is not empty:                // The main loop
 9          u := vertex in Q with smallest dist[] ;
10          if dist[u] = infinity:
11              break ;                        // all remaining vertices are inaccessible from source
12          fi ;
13          remove u from Q ;
14          for each neighbor v of u:        // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:            // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19              fi  ;
20          end for ;
21      end while ;
22      return dist[] ;
23  end Dijkstra.
Jika kita hanya tertuju pada alur jalan terpendek antara verteks sumber dan tujuan, kita dapat menghentikan pencarian pada pseudocode baris 11 jika u = tujuan. Sekarang kita dapat membaca jalan terpendek dari sumber ke tujuan dengan iterasi:
Code:
1  S := empty sequence
2  u := target
3  while previous[u] is defined:
4      insert u at the beginning of S
5      u := previous[u]

Beberapa keterangan dan penjelasan mengenai Algoritma Dijkstra yang perlu diperhatikan
- "Tetangga" verteks di sini maksudnya adalah verteks-verteks yang dituju oleh koneksi dari verteks current.
- Koneksi antarverteks tidak selalu dua arah, untuk koneksi satu arah (misalnya yang menghubungkan verteks A ke B), B adalah tetangga A, namun B bukan tetangga A.

Contoh Soal (EDIT: sudah dijawab XD)
Tentukan jarak terpendek dari titik A ke titik H pada gambar berikut ini:

NB:
* Silahkan jawab pertanyaan ini dengan me-reply post ini.. ;)
* Sori yaa gambarnya ga jelas kelihatan kalo di sini.. :sembah:
coba klik kanan -> View Image..

Contoh Soal 2
Tentukan jarak terpendek dari titik C ke titik F pada gambar berikut ini:


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





SIGGY KOSONG


Last edited by BungaTepiJalan on Fri Oct 01, 2010 2:57 pm; edited 1 time in total
Back to top Go down
View user profile https://bungatepijalan.wordpress.com
polo12
Global Moderator


Posts : 151
Chips : 2507
Power : 4
Join date : 2010-09-25
Location : Under your Underwear
Quote : ga ada

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 2:32 pm


pusing aku bang :o





Visit my Forum click here :sembah:





warsword:
 


Audi r10 in san andreas:
 
Back to top Go down
View user profile http://golden-world.forumotion.com
Prodixon
Head Administrator, ProDig Founder


Status : Akhirnya kembali...
Posts : 648
Chips : 4386
Power : 8
Join date : 2010-08-08
Location : ProDig
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 2:36 pm


Waduh... algoritma ini lagi O.O

Aku pernah lihat ini sblmnya di kamu juga pas lagi osjur XD

Tujuannya sih ngerti tp algoritmanya :swt:



Back to top Go down
View user profile http://prodig.forumotion.net
DrDhoom
Global Moderator


Posts : 217
Chips : 2614
Power : 7
Join date : 2010-09-25
Age : 23
Location : Martapura
Quote : I'm Zombie...
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 2:39 pm


jawaban nya 9...
bener ga? XD





Spoiler:
 

Back to top Go down
View user profile http://www.doomsgamesrpg.blogspot.com
Alissa
Ngacay Princess


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

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 2:50 pm


@DrDhoom:
Selamat, Anda benar!!! XD :hebat:
Dan.. hadiahnya.. aku akan bantu km dlm proyek game baka2bon-mu kalo kesulitan XD





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


Posts : 217
Chips : 2614
Power : 7
Join date : 2010-09-25
Age : 23
Location : Martapura
Quote : I'm Zombie...
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 2:56 pm


horey!!! :cheers:
prtma liat q kira susah... XD
check grammar ny az dlu :D





Spoiler:
 

Back to top Go down
View user profile http://www.doomsgamesrpg.blogspot.com
Alissa
Ngacay Princess


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

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 3:01 pm


Aduh.. kalo aq musti cek satupersatu teksnya lama.. :swt:
Mendingan kasi aja semua teks naskahnya aja lewat PM XD





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


Posts : 217
Chips : 2614
Power : 7
Join date : 2010-09-25
Age : 23
Location : Martapura
Quote : I'm Zombie...
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 3:05 pm


Wogh... okelah kalau begitu... :kabur:
btw... g da soal lagi? XD





Spoiler:
 

Back to top Go down
View user profile http://www.doomsgamesrpg.blogspot.com
Alissa
Ngacay Princess


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

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 3:12 pm


Ada soal kedua lho.. :- cekidot aja.. :kabur:





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


Posts : 217
Chips : 2614
Power : 7
Join date : 2010-09-25
Age : 23
Location : Martapura
Quote : I'm Zombie...
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 4:38 pm


The answer is... 20! CMIIW :D





Spoiler:
 

Back to top Go down
View user profile http://www.doomsgamesrpg.blogspot.com
Alissa
Ngacay Princess


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

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 4:46 pm


@DrDhoom:
Selamat, Anda benar lagi!!! XD :hebat:
Dan.. selanjutnya cobalah pake algoritma ini di GM.. XD





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


Posts : 217
Chips : 2614
Power : 7
Join date : 2010-09-25
Age : 23
Location : Martapura
Quote : I'm Zombie...
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 4:52 pm


Gmna mengaplikasikannya? :hmm:
q msih blum trllu ngrti sama GML XD





Spoiler:
 

Back to top Go down
View user profile http://www.doomsgamesrpg.blogspot.com
Alissa
Ngacay Princess


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

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 5:06 pm


Yaudah deh.. yg ini gausalah..
Soalnya ini butuh yg udah master.. :-
BTW, nanti aq buatin script GMLnya deh.. :kabur:





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


Posts : 349
Chips : 3426
Power : 3
Join date : 2010-09-24
Quote : Now. My job is &quot;Visual Effect Desainer
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Fri Oct 01, 2010 6:50 pm


Wah, fungsinya sih OK. tapi wa kurang mengerti dalam mengaplikasikannya
padaal menarik kalo bisa, ide jadi bejimbun. . . .. . . :D





Guest visit n' join on IGMID



Hai Guest :wave:
Jangan ragu-ragu untuk memberiku Cendol, dengan cara mengklik logo dibawah ini :D
daku akan sangat berterimakasih
Back to top Go down
View user profile
psychotammo
Unus


Posts : 3
Chips : 2263
Power : 0
Join date : 2010-09-27

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Sat Oct 02, 2010 7:05 am


haaah? apaan ini? rumit banget...but nice share bro~



Back to top Go down
View user profile
DrDhoom
Global Moderator


Posts : 217
Chips : 2614
Power : 7
Join date : 2010-09-25
Age : 23
Location : Martapura
Quote : I'm Zombie...
Badge :

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Sat Oct 02, 2010 8:22 am


@bunga: wogh...
tak tunggu deh script nya XD





Spoiler:
 

Back to top Go down
View user profile http://www.doomsgamesrpg.blogspot.com
Burger Loncat
Decem


Posts : 34
Chips : 2295
Power : 0
Join date : 2010-10-02
Location : in the world

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Thu Oct 07, 2010 2:25 pm


haaahhh aku gk ngerti apa apa :hmm: ini di uasbn gk keluar :D
:damai: good share om



Back to top Go down
View user profile
polo12
Global Moderator


Posts : 151
Chips : 2507
Power : 4
Join date : 2010-09-25
Location : Under your Underwear
Quote : ga ada

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Thu Oct 07, 2010 4:10 pm


Burger Loncat wrote:
haaahhh aku gk ngerti apa apa :hmm: ini di uasbn gk keluar :D
:damai: good share om

sama saya jga ga ngerti!
8) mantab oom bunga!





Visit my Forum click here :sembah:





warsword:
 


Audi r10 in san andreas:
 
Back to top Go down
View user profile http://golden-world.forumotion.com
Alissa
Ngacay Princess


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

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Thu Oct 07, 2010 5:42 pm


@Burger Loncat
Konsep2 algoritma yang ane post di forum ini emang nantinya dipelajari di mata kuliah algoritma lho.. :-
Tapi kalo qm mo memanfaatkan ini buat bikin game, nanti ane kasi script algoritmanya koq.. :D





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


Posts : 86
Chips : 2358
Power : 1
Join date : 2010-10-06

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Thu Oct 07, 2010 6:53 pm


- -a ini apakah bahasa pemrograman? Baru tau kalo algoritma seperti ini.






http://ekographartsign.deviantart.com

Bantu pedangku agar level dia tinggi plz






:hebat: Coba nge rule's topic :hebat:
Spoiler:
 
Back to top Go down
View user profile
Alissa
Ngacay Princess


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

PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Thu Oct 07, 2010 7:01 pm


Itu bukan bahasa pemrograman, gan! Itu algoritma deskriptif :-





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




PostSubject: Re: [Programming] Dijkstra's Algorithm - Find Your Shortest Way   
Today at 5:16 am





Back to top Go down
 

[Programming] Dijkstra's Algorithm - Find Your Shortest Way

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-
Jump to: