ALGORITMA 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).

2.1 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.

2.2 Skema Umum Algoritma Dijkstra

Berikut adalah skema algoritma dijksrta dalam mencari shortest path :

1. Buat 3 buah list yaitu list jarak (1), list simpul-simpul sebelumnya (2), dan list simpul yang sudah dikunjungi (3) serta sebuah variabel yang menampung simpul saat ini (current vertex).

2. Isi semua nilai dalam list jarak dengan tak hingga, kecuali simpul awal diisi 0

3. Isi semua nilai dalam list 2 dengan false

4. Isi semua nilai dalam list 3 dengan null.

5. Current vertex diisi dengan simpul awal (start).

6. Tandai current vertex sebagai simpul yang sudah dikunjungi.

7. Update list 1 dan 2 berdasarkan simpul-simpul yang dapat langsung dicapai dari current vertex.

8. Update current vertex dengan simpul yang paling dekat dengan simpul awal.

9. Ulangi langkah 6 sampai semua simpul dikunjungi.

MAXIMUM FLOW PROBLEM

3.1 Network Flow

Dalam teori graf, sebuah flow network adalah sebuah graf berarah yang tiap sisinya mempunyai bobot dan terdapat arus yang mengalir diantara 2 simpul yang mengapit sisi tersebut. Jumlah arus yang mengalir harus lebih kecil atau sama dengan bobot sisinya.

Pada aplikasinya, sebuah sebuah graf berarah sering disebut network. Setiap arus (fkow) yang ada pada network harus memenuhi sebuah batasan, yaitu arus yang masuk ke simpul harus sama dengan arus yang keluar dari simpul itu, kecuali pada source yang arus keluarnya lebih besar dan pada sink yang arus mauknya lebih besar.