|
� WWW.SPYROZONE.TK � |
|
|
[123]. Algoritma Dijkstra
------------------------------------------------------ Author : SPYRO KiD Contact : spyro_zone@Yahoo.COM ==> www.spyrozone.tk CopyLEFT (c) 2006 www.spyrozone.tk All Rights Reserved � 15/01/2006 14:00:50 WIB ------------------------------------------------------
Spyro baru ajah
menambahkan aplikasi untuk mencari Shortest Path berdasarkan Algoritma ini.
Download Programnya di halaman Memeber kategory Just For Fun. Bagi kamu yang
memiliki tugas mata kuliah ini dan membutuhkan Source Codenya, bisa lansung
menghubungi saya lewat Email Tapi.. maaf ajah kalo ngebalesnya agak telat,
soalnya di real life saya juga lagi sibuk mempersiapkan diri untuk UAN. � Jika yang dicari algoritma Kruskal adalah sisi dengan bobot terkecil dari sisi-sisi di atas dalam setiap iterasinya, � dalam algoritma Dijkstra, yang dicari adalah sisi yang menghubungkan ke suatu verteks di (V-W) sehingga jarak dari verteks asal Vs ke verteks tersebut adalah minimal. Dalam implementasinya penghitungan jarak dari verteks asal vs disederhanakan dengan menambahkan field minpath pada setiap verteks; field-field minpath ini diinisialisasi sesuai dengan adjacencynya dengan vs, kemudian dalam setiap iterasi di-update bersamaan masuknya w dalam W. Field minpath ini menunjukkan jarak dari vs ke verteks yang bersangkutan terpendek yang diketahui hingga saat itu. Jadi pada verteks dalam W, minpath sudah menunjukkan jarak terpendek dari Vs untuk mencapai verteks yang bersangkutan, sementara pada (V-W) masih perlu diupdate pada setiap iterasi dalam mendapatkan verteks w seperti diterangkan di atas. Yaitu, setiap mendapatkan w maka update minpath setiap adjacent verteks x dari w di (V-W) sisa dengan: � minimum (minpath dari x , total minpath w + panjang sisi yang bersangkutan), agar dapat berlaku umum maka di awal algoritma seluruh minpath diinisialisasi dengan +� . Demikian halnya pencarian w itu sendiri disederhanakan menjadi pencarian node di (V-W) dengan minpath terkecil. Selengkapnya algoritma Dijkstra adalah sebagai berikut. � Inisialisasi � W berisi mula-mula hanya vs � field minpath tiap verteks v dengan � Weight[vs, v], jika ada sisi tersebut, atau, � +� , jika tidak ada. � Lalu, dalam iterasi lakukan hingga (V-W) tak tersisa (atau dalam versi lain: jika ve ditemukan): � dari field minpath tiap verteks cari verteks w dalam (V-W) yang memiliki minpath terkecil yang bukan tak hingga. � jika ada w maka � masukkan w dalam W � update minpath pada tiap verteks t adjacent dari w dan berada dalam (V-W) dengan: minimum (minpath[t] , minpath[w] + Weight[w, t]) Verteks-verteks dalam W dapat dibedakan dari verteks dalam (V-W) dengan suatu field yang berfungsi sebagai flag atau dengan struktur liked-list. Informasi lintasan dapat diketahui dengan pencatatan predesesor dari setiap verteks yang dilakukan pada saat update harga minpath tersebut (fungsi minimum): jika minpath[t] diupdate dengan (minpath[w]+Weight[w, t]) maka predesesor dari t adalah w. pada tahap inisialisasi predesesor setiap verteks diisi oleh vs. Contoh masalah: Pada weighted graph di atas akan dicari shortest path dari A ke G. Algoritma ini akan bekerja sbb. (Notasi penulisan: X:mvia, dibaca, vertex X dicapai dari A melalui via dengan panjang path m, warna verteks A menunjukkan status visit dari X = true, (update): menunjukkan terjadinya update harga minpath dan via dari verteks ybs.).
�
Pada
tahap inisialisasi:
tabel MinPath
diisi:
�
Iterasi
ke 1:
dari tabel
minpath didapat B (via
A) dan update tabel
MinPath menjadi:
�
Iterasi
ke 2:
dari tabel
minpath didapat F (via
A) dan update tabel
MinPath menjadi:
�
Iterasi
ke 3:
dari tabel
minpath didapat D (via
A) dan update tabel
MinPath menjadi:
�
Iterasi
ke 4:
dari tabel
minpath didapat C (via
B) dan update tabel
MinPath menjadi:
�
Iterasi
ke 5:
dari tabel
minpath didapat E (via
B) dan update tabel
MinPath menjadi:
�
Iterasi
ke 6:
dari tabel
minpath didapat K (via
D) dan update tabel
MinPath menjadi:
�
Iterasi
ke 7:
dari tabel
minpath didapat J (via
K) dan update tabel
MinPath menjadi:
�
Iterasi
ke 8:
dari tabel
minpath didapat I (via
C) dan update tabel
MinPath menjadi:
�
Iterasi
ke 9:
dari tabel
minpath didapat G (via
K) dan update tabel
MinPath menjadi: � Karena G adalah verteks tujuan maka algoritma berhenti dan shortest path dari A ke G diperoleh dengan panjang 59. Route ybs: A-D-K-G.
/* ------------------------------|EOF|------------------------------ */
|
|
| � Back |
� WWW.SPYROZONE.TK � |