Algortima ini ditemukan oleh Edsger W. Dikstra dan di publikasi pada tahun 1959 pada sebuah jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs“. Algoritma ini sering digambarkan sebagai algoritma greedy (tamak). Djikstra merupakan salah satu varian bentuk algoritma popular dalam pemecahan persoalan terkait masalah optimasi pencarian lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute listasan terpendek.
CONTOH
Flowchart Algoritma Djikstra:
Implementasi Djikstra
Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot
terkecil dari satu titik ke titk lainnya. Misalnya titik mengambarkan gedung
dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi
terhadap semua kemungkinan bobot terkecil dari setiap titik.
Pertama-tama tentukan titik mana yang akan menjadikan node awal, lalu beri
bobot jarak pada node pertama ke node terdekat satu persatu, Dijkstra akan
melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik
selanjutnya tahap demi tahap inilah urutan logika dari algoritma Dijkstra :
- Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi)
- Set semua node “Belum Terjamah” dan set node awal sebagai “Node keberangkatan”
- Dari no keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru.
- Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
- Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selajutnya dan lanjutkan dengan kembali ke step 3
Tujuan Algoritma Dijkstra
- Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.
- Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.
- Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.
Urutan Logika Algoritma Dijkstra
- Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).
- Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.
- Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.
- Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
- Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.
contoh jaringan
Misalnya kita akan menggunakan algoritma Dijkstra untuk mencari path
terpendek dari node 1.
Untuk mempermudah, buatlah tabel seperti berikut ini:
(Notasi dalam tabel algoritma Dijkstra memiliki format (s-j,D), dimana s-j
menunjukkan rute dari node s menuju node j, sementara D menunjukkan jarak total
antara kedua node tersebut)
Baris pertama masih berupa inisialisasi, yaitu Dj akan memiliki nilai jika
tersambung langsung dan tidak memiliki nilai jika tidak tersambung langsung.
Karena node 1 kebetulan hanya memiliki 1 tetangga yaitu node 2, maka i = 2
dimasukkan pada himpunan N.
Node 2 sudah berperan sebagai "perpanjangan" node sumber (node
1), sehingga sekarang node-node yang terhubung dengan node 2 sudah bisa
"dijangkau" oleh node 1 via node 2. Diketahui node 3 dan node 4
terhubung langsung dengan node 2, sehingga rutenya ditulis (1-2-3) dan (1-2-4).
Untuk langkah selanjutnya dipilih node i yang telah tersambung dengan node
s namun belum masuk dalam himpunan N. Diketahui yaitu node 3 dan node 4. Node
yang dipilih adalah yang memiliki jumlah jarak yang paling minimum, yaitu node
4. Sehingga didapat baris tabel berikutnya seperti berikut.
Seperti langkah yang sebelumnya, sekarang node 4 ikut berperan sebagai
"perpanjangan" dari node 1 sehingga node 5 dan node 7 yang terhubung
langsung dengan node 4 sudah bisa "dijangkau" oleh node 1 dengan rute
yang tertampil.
Sebenarnya disini mulai terjadi perbandingan nilai jarak. Dengan
dimasukkannya node 4 dalam himpunan N, maka node 4 berlaku sebagai
"penembak sementara" (maafkan saya kalau istilahnya alay -_-).
Maksudnya adalah node 4 dapat melakukan perhitungan minimum menuju node
tertentu meskipun node tersebut telah diketahui rute dan jaraknya.
Dalam kasus ini dapat diambil node 3. Node 3 sudah diketahui rute dan
jaraknya pada baris ke-2. Dengan masuknya node 4 pada himpunan N, maka node 4
akan menghitung jarak minimum antara entry D3 yang terdahulu dengan
yang baru. (Perbandingan via node 2 dengan via node 4):
Via node 2 --> D2 + C23 = 2 + 3 = 5
Via node 4 --> D4 + C43 = 3 + 7 = 10
Maka entry yang dipertahankan adalah via node 2 dengan jarak 5.
Sebelumnya telah dipilih node 4 sebagai anggota N karena bertetangga dengan
node 2. Sekarang dipilih tetangga node 2 yang lainya yaitu node 3.
Perbandingan yang terjadi:
Pada D4
Via node 2 --> D2 + C24 = 2 + 1 = 3
Via node 3 --> D3 + C34 = 5 + 7 = 12
Maka entry yang dipertahankan adalah via node 2 dengan jarak 3.
Pada D5
Via node 4 --> D4 + C45 = 3 + 4 = 7
Via node 3 --> D3 + C35 = 5 + 3 = 8
Maka entry yang dipertahankan adalah via node 4 dengan jarak 7.
Singkat cerita, tabel hasil
akhirnya adalah sebagai berikut
Daftar pustaka
Tidak ada komentar:
Posting Komentar