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