Algoritma Dijkstra

ditemukan oleh seorang ilmuan computer yang bernama EDSGER DIJKSTRA.  Oleh karena itu, nama yang diberikanpun sesuai dengan nama penemunya yaitu, Algoritma DIJKSTRA, algoritma dijkstra adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tidak-negatif.

Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

ex :

(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.