Selasa, 03 April 2012

Algoritma Dijkstra


Algoritma Dijkstra menemukan jalan terpendek dari satu vertex v0 sama simpul lain dalam
digraf. Ketika selesai, panjang jarak terpendek dari v0 ke v disimpan dalam vertex v, dan jalan terpendek dari v0 ke v dicatat dalam pointer belakang v dan yang lainnya simpul di sepanjang jalan itu.
Algoritma ini menggunakan antrian prioritas, menginisialisasi itu dengan semua simpul dan kemudian dequeueing satu simpul pada setiap iterasi.


ALGORITMA
(Prekondisi: G = (V, w) adalah graf berbobot dengan simpul awal v0.)
(Postcondition: Setiap simpul v di V menyimpan jarak terpendek dari v0 ke v dan referensi kembali ke
simpul sebelumnya bersama bahwa jalan terpendek.)
1. Menginisialisasi field jarak ke 0 untuk v0 dan untuk untuk masing-masing simpul lainnya.
2. Mengantrekan semua simpul ke antrian prioritas Q dengan prioritas tertinggi yang nilai terendah field jarak.
3. Ulangi langkah 4-10 sampai dengan Q adalah kosong.
4. (Invarian: Bidang referensi jarak dan belakang setiap simpul yang tidak dalam Q adalah benar.)
5. Dequeue simpul prioritas tertinggi ke x.
6. Lakukan langkah-langkah 7-10 untuk setiap y simpul yang berbatasan dengan x dan pada prioritas antrian.
7. Biarkan s menjadi jumlah dari field jarak x’s ditambah berat tepi dari x untuk y.
8. Jika kurang dari field jarak y’s, lakukan langkah 9-10; jika tidak pergi kembali ke Langkah 3.
9. Tetapkan s untuk field jarak y’s.
10.   Tetapkan x untuk referensi kembali simpul y’s fieldne setiap kali iterasi.

see my web at www.iaincirebon.ac.id

1 komentar:

andry yudha prawira mengatakan...

berdasarkan artikel tersebut, bisa menjadi rujukan link penelitian dibawah ini

http://repository.gunadarma.ac.id/bitstream/123456789/1044/1/50406021.pdf

terima kasih