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.

Teknik Divide dan Conquer

   
 Algoritma divide dan conquer diperkenalkan sebagai sumber dari pengendalian proses parallel yang cukup rumit hal ini karena masalah-masalah yang terjadi dapat diatasi secara independen. Banyak arsitektur dana bahasa pemrograman yang mendesain implementasinya (apliasi) dengan struktur dasar dari algoritma divide dan conquer. Pemrograman betanggung jawab atas implementasi suatu solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub-sub masalah yang dapat dikelola. Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :

1.      Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.

2.      Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.

3.      Perancangan representasi elemen-elemen data di memori sehingga memenuhi criteria berikut:

·      Memenuhi keterhubungan logika antara elemen-elemen data.

·      Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.

4.      Pengambilan keputusan mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.

Divide dan conquer itu sendiri adalah pendekatan yang ditandai dengan pembagian suatu masalah ke dalam submasalah yang bentuknya sama dengan masalah yang lebih besar. Pembagian lebih lanjut ke dalam submasalah yang lebih kecil lagi biasanya dilaksanakan dengan penggulungan, sebuah metode yang dikenal oleh programmer sekuensial. Metode rekursif akan terus-menerus membagi masalah sampai tugas itu tidak dapat dipecahkan lagi menjadi bagian yang lebih kecil. Selanjutnya tugas - tugas yang sangat sederhana akan dilaksanakan dan hasilnya kemudian dikombinasikan, dan diteruskan dengan tugas yang lebih besar lagi.

Pada prinsip dasar algoritma perulangan dibutuhkan sebuah kondisi untuk mengakhiri perulangan tersebut. Biasanya untuk mengecek apakah masalah sudah cukup kecil sehingga dapat diselesaikan secara langsung. Selain dibutuhkan sebuah kondisi, kita juga memerlukan fase devide untuk membagi atau memecahkan masalah menjadi sub-sub masalah yang lebih kecil, dan fase combine untuk menggabungkan kembali solusi dari sub-sub masalah menjadi solusi dari masalah awal.

Langkah utama dalam algoritma divide dan conquer adalah :

a)      Divide => Masalah dibagi menjadi beberapa bagian, setiap bagiannya memiliki permasalahan yang serupa dengan masalah utama.

b)      Conquer => Setiap bagian masalah masing-masing dipecahkan (dalam pemrograman dilakukan rekursif).

c)      Combine => Solusi dari masing-masing bagian masalah digabungkan sehingga membentuk solusi untuk masalah utama.

            Selain dari langkah-langkah utama diatas, berikut ini terdapat empat hal penting yang harus dipahami dalam strategi divide dan conquer :

1)                  Branching Factor

     Branching factor dalam suatu algoritma divide dan conquer adalah jumlah dari sub masalah yang akan dibagi dari sebuah masalah awal. Ini adalah langkah nyata dari algoritma divide dan conquer, didalam proses pembagian yang sebenarnya. Pada Branching factor harus memiliki jumlah dua atau lebih karena jika tidak masalah tidak bisa dibagi.

2)                  Balance

     Sebuah algoritma divide dan conquer dikatakan balance jika masalah awal dibagi menjadi sub-sub masalah dengan ukuran yang sama. Hal ini memiliki arti dimana jumlah dari keseluruhan ukuran sub masalah sama dengan sub masalah awal. Algoritma mengesort dan binary tree, dan sama halnya dengan algoritma reduksi dan prefix sum adalah beberapa contoh algoritma divide dan conquer yang seimbang.

3)                  Data Dependence of Divide Function

    Algoritma divide dan conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relative dari sebuah sub masalah tergantung proses input datanya. Salah satu contoh dari algoritma yang tidak seimbang adalah algoritma quicksort yang akan membagi sub masalah dengan fungsi data-dependent divide.

4)                  Control Parallelism of Sequentiality

    Algoritma divide dan conquer dikatakan berurutan (sequential) jika sub masalah di eksekusi dengan perintah program. Parelisasi dari algoritma divide dan conquer yang terurut pertama kali didefinisikan oleh Mou’s Divacon [Mou90],  yang terjadi ketika hasil dari salah satu sub-eksekusi diperlukan oleh sub-eksekusi lain. Dalam kasus ini hasil dari subtree pertama diberikan (passing) kepada proses komputasi subtree kedua, agar hasil akhir tersebut dapat digunakan sebgai nilai awalnya, tetapi sekarang contoh tersebut tidak dapat dijadikan ilustrasi lagi karena teknologi komputer parallel yang semakin canggih dan kompleks.