Saat ini sudah banyak algoritma yang bisa digunakan untuk menemukan pencarian rute terpendek, dan tidak bisa di pungkiri Djikstra masih menjadi salah satu yang populer dari sekian banyak algoritma tersebut. Pada postingan kali ini kita akan membahas mendetail mulai dari apa itu algoritma djikstra dan dan bagaimana cara kerja algoritma djikstra. Edsger DijkstraAlgortima 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“[1]. Algoritma ini sering digambarkan sebagai algoritma greedy (tamak). Sebagai contoh, ada pada buku Algorithmics (Brassard and Bratley [1988, pp. 87-92]) 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 FlowchartPseudo Code 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 :
Note : Bahkan menurut Andrew Goldberg, peneliti utama di 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,” – Goldberg. “Industri selalu datang dengan aplikasi baru sepanjang waktu, membuat parameter yang berbeda untuk tiap masalah. Teknologi dengan lebih banyak kecepatan dan kapasitas memungkinkan kita untuk memecahkan masalah yang lebih besar, sehingga dalam lingkup masalah jalan terpendek maka akan selalu ada optimasi. Semoga Bermanfaat ! 😉 Daftar Pustaka
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:
Sebagai contoh hitunglah Jarak terdekat dari V1 ke V7 pada gambar berikut ini. Hasil setiap stepnya dapat dilihat pada tabel berikut ini. Dengan demikian jarak terpendek dari V1 ke V7 adalah 16 dengan jalur V1->V2->V3->V5->V6->V7
Algoritma Dijkstra ditemukan oleh Edsger W. Dijkstra merupakan salah satu varian bentuk algoritma populer dalam pemecahan persoalan yang terkait dengan masalah optimasi dan bersifat sederhana. Algoritma ini menyelesaikan masalah untuk mencari lintasan terpendek ( sebuah lintasan yang mempunyai panjang minimum) dari vertex a ke vertex z dalam graf berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh vertex negatif. Dalam mencari solusi, Algoritma Dijkstra menggunakan prinsip greedy, yaitu mencari solusi optimum pada setiap langkah yang dilalui dengan tujuan untuk mendapatkan solusi optimum pada langkah selanjutnya yang akan mengarah pada solusi terbaik. Algoritma ini mencari panjang lintasan terpendek dari vertex a ke z dalam sebuah graf berbobot. Langkah-langkah dalam menentukan lintasan terpendek pada Algoritma Dijkstra adalah sebagai berikut :
Pseudocode Algoritma Dijkstra function Dijkstra(Graph, source): for each vertex v in Graph: // Initializations dist[v] := infinity ; // Unknown distance function from // source to v previous[v] := undefined ; // Previous node in optimal path end for // from source dist[source] := 0 ; // Distance from source to source Q := the set of all nodes in Graph ; // All nodes in the graph are // unoptimized - thus are in Q while Q is not empty: // The main loop u := vertex in Q with smallest distance in dist[] ; // Start node in first case remove u from Q ; if dist[u] = infinity: break ; // all remaining vertices are end if // inaccessible from source for each neighbor v of u: // where v has not yet been // removed from Q. alt := dist[u] + dist_between(u, v) ; if alt < dist[v]: // Relax (u,v,a) dist[v] := alt ; previous[v] := u ; decrease-key v in Q; // Reorder v in the Queue end if end for end while return dist; |