Algorima Dijkstra

Pada tahun 1959 sebuah tulisan sebanyak tiga halaman yang berjudul A Note on Two Problem in Connexion with Graphs diterbitkan oleh jurnal Numerische Mathematic. Pada tulisan ini, Edsger W. Dijkstra, seorang ilmuwan komputer berusia 29 tahun mengusulkan algoritma-algoritma untuk solusi dari dua masalah teoritis graf dasar. The Minimum Weight adalah algoritma dijkstra untuk lintasan terpendek adalah salah satu algoritma yang paling ternama dalam ilmu komputer dan sebuah algoritma paling populer dalam operasi pencarian (OR).

Definisi Algoritma Dijkstra

Pada dasarnya, algoritma ini adalah salah satu bentuk algoritma greedy. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing. Algoritma dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan strategi greedy sebagai berikut :

Untuk setiap simpul pada sumber (source) dalam graf, algoritma ini akan mencari jalur dengan cost minnimum antara simpul tersebut dengan simpul lainnya.

Skema Algoritma Dijkstra

Algoritma Dijkstra diterapkan untuk mencari lintasan terpendek pada graf berarah. Namun, algoritma ini juga benar untuk graf tak berarah. Algoritma Dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip greedy. Prinsip greedy pada algoritma dijkstra menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya dalam himpunan solusi.

Contoh Algoritma Dijkstra

Penerapan  Algoritma Dijkstra pada Jaringan Komputer

Jaringan komputer dapat dimodelkan sebagai sebuah graf, dengan setiap simpul menyatakan sebuah komputer/router dan sisi di dalam graf menyatakan saluran komunikasi (sering disebut link). Setiap sisi mempunyai label nilai ( yang disebut bobot). Bobot tersebut dapat menyatakan jarak geografis(dalam km), kecepatan transfer data, waktu pengiriman).

Mencari lintasan terpendek  dari router asal ke router tujuan dapat diartikan sebagai menentukan lintasan terpendek dari simpul asal ke simpul tujuan di dalam graf yang merepresentasikan jaringan komputer tersebut. Algoritma Dijkstra adalah algoritma yang banyak digunakan untuk mencari lintasan terpendek.