« Back ::

« www.spyrozone.net »

[123]. Algoritma Dijkstra

---------------------------------------------------------

Author  : SPYRO KiD

Contact : admin[~@~]spyrozone.net || http://spyrozone.net

CopyLEFT (c) 2006 www.spyrozone.net 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.

Algoritma ini mirip dengan algoritma Prim untuk mencari MST, yaitu pada tiap iterasi memeriksa sisi-sisi yang menghubungkan subset verteks W dan subset verteks (V-W) dan memindahkan verteks w dari (V-W) ke W yang memenuhi kriteria tertentu. Perbedaannya terletak pada kriteria itu sendiri.

• 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:m^via, 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:
  {A:0, B: 24^A, C: 43^A, D: 33^A, F: 31^A, yang lain ¥ }

• Iterasi ke 1: dari tabel minpath didapat B (via A) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B(update), D: 33^A, F: 31^A, H: 69^B(update), yang lain ¥}

• Iterasi ke 2: dari tabel minpath didapat F (via A) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B(update), F: 31^A, H: 69^B, yang lain ¥}

• Iterasi ke 3: dari tabel minpath didapat D (via A) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B, F: 31^A, G: 72^D(update), H: 69^B, K: 46^D(update), L: 60^D(update), yang lain ¥}

• Iterasi ke 4: dari tabel minpath didapat C (via B) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B, F: 31^A, G: 64^D, H: 69^B, I: 57^C(update), K: 46^D, L: 60^D, yang lain ¥}

• Iterasi ke 5: dari tabel minpath didapat E (via B) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B, F: 31^A, G: 64^D, H: 69^B, I: 57^C, K: 46^D, L: 60^D, yang lain ¥}

• Iterasi ke 6: dari tabel minpath didapat K (via D) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B, F: 31^A, G: 59^K(update), H: 69^B, I: 57^C, J: 56^K(update), K: 46^D, L: 60^D, yang lain ¥}

• Iterasi ke 7: dari tabel minpath didapat J (via K) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B, F: 31^A, G: 59^K, H: 69^B, I: 57^C, J: 56^K, K: 46^D, L: 60^D, M: 71^J(update), yang lain ¥}

• Iterasi ke 8: dari tabel minpath didapat I (via C) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B, F: 31^A, G: 59^K, H: 69^B, I: 57^C, J: 56^K, K: 46^D, L: 60^D, M: 71^J}

• Iterasi ke 9: dari tabel minpath didapat G (via K) dan update tabel MinPath menjadi:
  A:0, B: 24^A, C: 42^B, D: 33^A, E: 46^B, F: 31^A, G: 59^K, H: 69^B, I: 57^C, J: 56^K, K: 46^D, L: 60^D, M: 71^J}

• 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|------------------------------ */

« www.spyrozone.net »