Algoritma Dijsktra

Pada tahun 1959 sebuah tulisan sepanjang tiga halaman yang berjudul A Note on Two Problems in Connexion with Graphs diterbitkan padajurnal Numerische Mathematik. Padatulisanini, Edsger W. Dijkstra - seorangilmuwan computer berumur duapuluh sembilantahun mengusulkan algoritma-algoritma untuk solusi dari dua masalah teoritis graf dasar: the minimum weight Algoritma Dijkstra untuk masalah jalan terpendek adalah satu dari algoritma - algoritma paling ternama pada ilmu komputer dan sebuah algoritma paling popular pada oparasi pencarian (OR).

Implementasi algoritma dijkstra. 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. Algoritma ini menggunakan prinsip greedy yang digunakan untuk menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya ke dalam himpunan solusi. Akan tetapi bobot dari graf tersebut harus bernilai bilangan positif (bobot >= 0). Algoritma ini untuk menggambarkan jarak kedua tempat dengan jarak yang digambarkan secara singkat .

contoh skema algoritma dijsktra

   Properti Algoritma Djikstra

1.      Matriks Ketetangga M [mij]

mij = bobot sisi (i,j) ; pada graf tak berarah mij = mji

mii = 0

mij = , jika tidak ada sisi dari simpul i ke simpul j

2.      Larik S = [si] yang dalam hal ini,

si = 1, jika simpul i termasuk ke dalam lintasan terpendek

si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek

3.      Larik / tabel D = [di] yang dalam hal ini, di = panjang lintasan dari simpul awal s ke simpul I.

Maximum Flow Problem ( Network Flow )

Flow network adalah sebuah graf berarah yang tiap sisinya memiliki kapasitas/bobot dan pada tiap sisi tersebut terdapat arus (flow) yang mengalir antara 2 simpul yang mengapit sisi tersebut. Jumlah arus yang mengalir pada tiap sisi harus lebih kecil atau sama dengan kapasitas sisi tersebut.Pada aplikasinya, sebuah graf berarah sering disebut dengan network. Jumlah arus yang mengalir pada tiap sisi harus lebih kecil atau sama dengan kapasitas sisi tersebut. Pada aplikasinya, sebuah graf berara sering disebut dengan network. Setiap arus (flow) yang ada dalam network, harus memenuhi sebuah batasanya itu arus yang masuk pada suatu simpul harus sama dengan arus yang keluar pada simpul tersebut, kecuali pada source, yang keluarnya lebih besar dari arus masuk, dan sink, yang arus masuknya lebih besar dari arus keluar Sebuah network biasanya digunakan untuk memodelkan sistem lalu lintas, saluran pipa, sirkuitelektrik.

Pencarian rute terpendek merupakan salah satu persoalan dalam teori graf. Persoalan ini bisa diselesaikan dengan algoritma dijkstra karena lebih mudah dan menarik, adapun beberapa keuntungan yang kita peroleh dari Algoritma Dijkstra yaitu :

1.    Algoritma Dijkstra dapat menentukan jalur tercepat dengan waktu yang lebih cepat dibandingkan algoritma lainnya.

2.  Menggunakan Algoritma Dijkstra mempermudah kita dalam mengetahui jarak atau lintasan terpendek dari suatu titik tertentu ke semua titik yang lain.

3.    Menggunakan Algoritma Dijkstra dalam penerapan di dalam sistem geografis akan menampilakan   visualisasi data dalam bentuk peta

4.    Pada penampilan rute atau peta Algoritma Dijkstra lebih mudah di baca dan di pahami.

5.    Pada rute atau peta dan lintasannya dapat diberikan warna, sehingga penampilan Algoritma Dijkstra lebih menarik dan lebih mudah untuk membedakan dari suatu titik tertentu ke titik yang lain.