Algoritma Dijkstra

Algoritme Dijkstra

~ ~ SIDS ~ ~

Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

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. Berikut Pseudo Code dan Flowchart Algoritma Djikstra:

Djikstra Flowchart

Urutan logika algoritma Dijkstra :

1.  Greader berikan nilai bobot Guntuk setiap titik hingga ke titik yang lain, berikan nilai 0 pada node awal dan nilai tak hingga terhadap node yang lain.

2.  Setelah itu Greader berikan nilai pada semua node dan berikan node awal sebagai node keberangkatan.

3.  Dari node keberangkatan, hitung nilai jarak antara node keberangkatan ke node yang lain.

4.  Berikan pertimbangan untuk setiap node / langkah dari node keberangkatan ke node yang di tuju, dan berikan tanda yang gunanya untuk menandai agar node yang telah di lalui, tidak terlalui kembali. Setelah itu simpan hasil nilai bobot jarak terakhir dan gunakan bobot yang paling minimal.

5.  Carilah node yang belum dilalui dengan jarak terkecil dari node keberangkatan itu, lanjutkan kembali langkah ke 3.

6.  Kompleksitas algoritma Dijkstra merupakan O(n2), n merupakan simpul pada graf. Kompleksitas ini bisa diperbaiki dengan penggunaan struktur data senarai ketanggan atau antrian prioritas guna untuk memperoleh kompleksitas O((m+n) log n).

Contoh penerapan Algoritma Dijkstra dalam kehidupan sehari-hari :

1.  Aplikasi Pencarian Lokasi Rumah Kos Dan Jalur Terpendek Menggunakan Algoritma Dijkstra.

2.  Pencarian Solusi Maksimum Flow Problem Dengan Penerapan Algoritma Dijkstra.

3.  Penggunaan Algoritma Dijkstra Terhadap Sebuah Sistem Informasi Geografis

4.  Sekolah Luar Biasa Kota Pekanbaru Berbasis Online.

5.  Menemukan Jarak Terdekat Dari Lokasi Pengguna ke Lokasi Taman Yang Di Tuju Berbasis Android (Studi Kasus Taman Raya Kantor Gubernur Pekanbaru, Riau).

6.  Animasi 3D Lintasan Terpendek Menggunakan Algoritma

7.  Penggunaan Algoritma Dijkstra Dalam Mencari dan Menghindari Jalur Kemacetan Di Kota pekanbaru.

8.  Pencarian Rute Terpendek Angkutan Kota Dengan Menggunakan Algoritma Dijkstra (Studi Kasus Kota Medan).

9.  Menetukan Rute Terpendek Dalam Pengambilan Sampah (Studi Kasus Kecamatan Singingi, Kabupaten Kuantan Singingi).

10.  Penggunaan Algoritma Dijkstra Dalam Menentukan Jalur Terpendek Dalam Pencarian Lokasi Rumah Sakit Awal Bross (Studi Kasus Di Kota Sumatera Barat).

11.  Penerapan Algoritma Dijkstra Untuk Pencarian Rute Bus Transmetro Pekanbaru.

12.  Aplikasi Untuk Mengetahui Lokasi Tempat Ibadah Umat Muslim Dengan Menggunakan Algoritma Dijkstra (Studi Kasus Kota Bandung, Jawa Barat).

13.  Implementasi Algoritma Dijkstra Dalam Mencari dan Menentukan Rumah Makan Terdekat Dari Lokasi Pengguna.

14.  Menentukan Rute Terpendek Tempat Wisata Di Kota Malang Berbasis Android Dengan Menggunaan Algoritma Dijkstra.

15.  Implementasi Algoritma Dijkstra Dalam Perencanaan Rute Evakuasi Bencana Gempa Bumi Di Lombok Berbasis Android.

16.  Penggunaan Algoritma Dijkstra Dalam Pencarian Ojek Online Terdekat dari Lokasi Pengguna Berbasis Android.