Langsung ke konten utama

ALGORITMA DIJKSTRA


Algoritme Dijkstra, (sesuai penemunya  Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph).
Algoritma ini dioublikasikan pada tahun 1959  jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs” dan dianggap sebagai algoritma greedy.
Permasalahan rute terpendek dari sebuah titik ke akhir titik lain adalah sebuah masalah klasik optimasi yang banyak digunakan untuk menguji sebuah algoritma yang diusulkan. Permasalahan rute terpendek dianggap cukup baik untuk mewakili masalah optimisasi, karena permasalahannya mudah dimengerti (hanya menjumlahkan seluruh edge yang dilalui) namun memiliki banyak pilihan solusi.
Menurut Andrew Goldberg peneliti Microsoft Research Silicon Valley, mengatakan ada banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek. “Jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan”.
Diskripsi matematis untuk grafik dapat diwakili G = {V. E}, yang berarti sebuah grafik (G) didefenisikan oleh satu set simpul (Vertex = V) dan koleksi Edge (E).
Algoritma Dijkstra bekerja dengan membuat jalur ke satu simpul optimal pada setiap langkah. Jadi pada langkah ke n, setidaknya ada n node yang sudah kita tahu jalur terpendek. Langkah-langkah algoritma Dijkstra dapat dilakukan dengan  langkah-langkah berikut:
  1. Tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap.
  2. 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) 2.
  3. Set semua node yang belum dilalui  dan set node awal sebagai “Node keberangkatan”
  4. Dari node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru
  5. Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah dilalui sebagai “Node dilewati”. Node yang dilewati tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
  6. Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah e.

Sebagai contoh hitunglah Jarak terdekat dari V1 ke V7 pada gambar berikut ini.

Komentar

Posting Komentar

Postingan populer dari blog ini

Komponen Pasif Resistor dan Kapasitor

 Penemu Resistor     Resistor yang kita kenal saat ini adalah buah tangan dari seorang  Georg Simon Ohm dilahirkan pada tanggal 16 Maret 1789 di kota Erlangen di Bavaria, yang sekarang Jerman. Dia meninggal pada 6 Juli 1854 di Munich, Bavaria, Jerman. Pengertian Resistor – Resistor merupakan salah satu komponen yang paling sering ditemukan dalam Rangkaian Elektronika. Hampir setiap peralatan Elektronika menggunakannya. Pada dasarnya Resistor adalah komponen Elektronika Pasif yang memiliki nilai resistansi atau hambatan tertentu yang berfungsi untuk membatasi dan mengatur arus listrik dalam suatu rangkaian Elektronika. Resistor atau dalam bahasa Indonesia sering disebut dengan Hambatan atau Tahanan dan biasanya disingkat dengan Huruf “R”. Satuan Hambatan atau Resistansi Resistor adalah OHM (Ω). Sebutan “OHM” ini diambil dari nama penemunya yaitu Georg Simon Ohm yang juga merupakan seorang Fisikawan Jerman. A. Resistor Resistor atau disebut juga d...
1 komentar
Baca selengkapnya

MODEL SOFTWARE DEVELOVMENT LIFE CYCLE (SDLC) MENGENAI BIG BANG MODEL

  MODEL SOFTWARE DEVELOVMENT LIFE CYCLE (SDLC)   PENJELASAN MENGENAI BIG BANG MODEL Pengertian Big Bang Model             Big Bang Model adalah Dimana kita tidak mengikuti proses tertentu. Perkembangan hanya dimulai dengan uang dan usaha yang dibutuhkan sebagai masukan, dan hasilnya adalah perangkat lunak yang dikembangkan yang mungkin atau mungkin tidak sesuai dengan kebutuhan pelanggan. Model Big Bang ini tidak mengikuti dan hanya ada sedikit perencanaan yang diperlukan. Bahkan pelanggan pun tidak yakin dengan apa yang sebenarnya dia inginkan dan persyaratannya diimplementasikan dengan cepat tanpa banyak analisis. Biasanya model ini di implementasi untuk proyek kecil dimana tim developernya sangat sedikit.     Model Big Bang terdiri dari memfokuskan semua sumber daya yang mungkin dalam pengembangan perangkat lunak dan pembuatan code / coding, dengan perencanaan yang sangat sedikit atau tidak sama sekali. Requirement yang dibutuhka...
Posting Komentar
Baca selengkapnya