ALGORITMA DIJKSTRA

Algoritma Dijkstra adalah suatu algoritma untuk menentukan jalur terpendek antar node dengan berdasar pada basis penghitungan "dari satu node menuju seluruh node". Algoritma Dijkstra termasuk dalam jenis algoritma Link State, yaitu memperhatikan total jarak dan rute yang akan dilalui.

Keywords: jaringan komputer node shortest path jalur terpendek algoritma dijkstra cara step langkah tabel gambar how to mudah singkat

Pada dasarnya, terdapat beberapa notasi utama dalam pengerjaan Algoritma Dijkstra ini:

·                     Inisialisasi 

Untuk proses inisialisasi, dibentuk suatu array/himpunan N dengan anggota s (s adalah lambang untuk suatu node sumber). Nilai D adalah jarak yang akan tersedia pada tabel hasil algoritma, sementara C adalah nilai jarak pada map yang tersedia. Maka pada tahap inisialisasi ini nilai Dj (jarak pada hasil tabel antara node s dengan node j, dengan j tidak sama dengan s) dimasukkan nilai yang sebenarnya. Jika tidak tersambung secara langsung maka akan dianggap tak terdefinisi. Untuk jarak Ds tentu saja bernilai 0.

·                     Temukan simpul tetangga (node selain sumber) 

Kalau notasi ini apa artinya yaa... -_- saya lupa. Pokoknya nanti untuk perulangan tiap baris dimasukkan node i yang belum termasuk pada array/himpunan N untuk nanti node i tersebut dijadikan sebagai "perpanjangan" dari node s, dengan node i juga merupakan node tetangga dari node s. Node i yang dimasukkan pada himpunan N berdasarkan pada jarak terkecil dengan node s. Dan jika seluruh node sudah masuk dalam himpunan N, maka iterasi akan berhenti.

·                     Update untuk setiap j ϵ N 

Untuk setiap node j (dalam tabel hasil: tiap kolom) diperbaharui nilainya yang paling kecil yaitu membandingkan antara nilai Dj sebelumnya dengan hasil penjumlahan (Di+Cij), yaitu penjumlahan jarak node s ke node i dengan jarak sebenarnya dari node i ke node j.

Mungkin kalau hanya baca teorinya saja pasti pusing ya. Mending langsung kita terapkan ke contoh soal saja ya biar lebih gampang ^^.

Mari kita pakai contoh jaringan yang sama dengan yang ada pada postingan Bellman-Ford yang lalu:

Misalnya kita akan menggunakan algoritma Dijkstra untuk mencari path terpendek dari node 1.

Untuk mempermudah, buatlah tabel seperti berikut ini:

(Notasi dalam tabel algoritma Dijkstra memiliki format (s-j,D), dimana s-j menunjukkan rute dari node s menuju node j, sementara D menunjukkan jarak total antara kedua node tersebut) 

Baris pertama masih berupa inisialisasi, yaitu Dj akan memiliki nilai jika tersambung langsung dan tidak memiliki nilai jika tidak tersambung langsung.

Karena node 1 kebetulan hanya memiliki 1 tetangga yaitu node 2, maka i = 2 dimasukkan pada himpunan N.

Node 2 sudah berperan sebagai "perpanjangan" node sumber (node 1), sehingga sekarang node-node yang terhubung dengan node 2 sudah bisa "dijangkau" oleh node 1 via node 2. Diketahui node 3 dan node 4 terhubung langsung dengan node 2, sehingga rutenya ditulis (1-2-3) dan (1-2-4).

Untuk langkah selanjutnya dipilih node i yang telah tersambung dengan node s namun belum masuk dalam himpunan N. Diketahui yaitu node 3 dan node 4. Node yang dipilih adalah yang memiliki jumlah jarak yang paling minimum, yaitu node 4. Sehingga didapat baris tabel berikutnya seperti berikut.

Seperti langkah yang sebelumnya, sekarang node 4 ikut berperan sebagai "perpanjangan" dari node 1 sehingga node 5 dan node 7 yang terhubung langsung dengan node 4 sudah bisa "dijangkau" oleh node 1 dengan rute yang tertampil.

Sebenarnya disini mulai terjadi perbandingan nilai jarak. Dengan dimasukkannya node 4 dalam himpunan N, maka node 4 berlaku sebagai "penembak sementara" (maafkan saya kalau istilahnya alay -_-). Maksudnya adalah node 4 dapat melakukan perhitungan minimum menuju node tertentu meskipun node tersebut telah diketahui rute dan jaraknya.

Dalam kasus ini dapat diambil node 3. Node 3 sudah diketahui rute dan jaraknya pada baris ke-2. Dengan masuknya node 4 pada himpunan N, maka node 4 akan menghitung jarak minimum antara entry D3 yang terdahulu dengan yang baru. (Perbandingan via node 2 dengan via node 4):

Via node 2 --> D2 + C23 = 2 + 3 = 5

Via node 4 --> D4 + C43 = 3 + 7 = 10

Maka entry yang dipertahankan adalah via node 2 dengan jarak 5.

Sebelumnya telah dipilih node 4 sebagai anggota N karena bertetangga dengan node 2. Sekarang dipilih tetangga node 2 yang lainya yaitu node 3.

Perbandingan yang terjadi:

Pada D4

Via node 2 --> D2 + C24 = 2 + 1 = 3

Via node 3 --> D3 + C34 = 5 + 7 = 12

Maka entry yang dipertahankan adalah via node 2 dengan jarak 3.

Pada D5

Via node 4 --> D4 + C45 = 3 + 4 = 7

Via node 3 --> D3 + C35 = 5 + 3 = 8

Maka entry yang dipertahankan adalah via node 4 dengan jarak 7.

Singkat cerita, tabel hasil akhirnya adalah sebagai berikut.

Cara Kerja
   

Cara kerja  Algoritma dijkstra memakai strategi greedy, dimana pada setiap langkah di pilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan  simpul yang sudah terpilih dengan simpul lain yang belum terpilih.

 Algoritma Dijkstra membutuhkan parameter tempat asal dan tempat tujuan. Hasil akhir dari algoritma ini adalah jarak terpendek dari tempat asal ke tempat ujuan beserta  rutenya.

contoh:

3.Penerapan Algoritma Dijkstra
  

(Penerapan  Algoritma Dijkstra pada Jaringan Komputer)

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.

 Sumber : 

affanw.algoritma-dijkstra.http://affanw.blogspot.co.id/2013/05/algoritma-dijkstra.html 

aznhy.algoritma-dijkstra.http://aznhy.blogspot.co.id/2012/05/algoritma-dijkstra.html

WEB SERVER UBUNTU

Repository adalah suatu kumpulan dari berbagai macam aplikasi atau program untuk sebuah sistem operasi linux atau ringkasnya adalah suatu paket aplikasi dalam distribusi Linux.

Repository juga dapat diartikan sebagai paket-paket khusus untuk sebuah program sistem operasi yang selanjutnya paket tersebut di install sehingga memperoleh kinerja yang lebih baik dari sebuah sistem operasi.
Fungsi dari repository 

Sebagai penunjang kinerja dari sebuah program, aplikasi dan sebagainya yang di dapat dari Server Mirror, CD/DVD dan media penyimpanan lainnya.

Repository Ubuntu dari Internet

Langkah-Langkahnya :

1. Edit file konfigurasi yang ada di komputer pengakses.

    #nano /etc/apt/sources.list

2. Masukkan alamat repository, contoh menggunakan repository UGM :

    # deb

    http://repo.ugm.ac.id/ubuntu/pool/main/a/apache2/ 

3. Simpan file setelah diedit

4. Lakukan perintah update, ketik perintah : 

    #apt-get update

5.  Instal aplikasi Apache web server

     # apt-get install apache2

maka setelah diinstal kita ketikan " Localhost " di web browser maka akan muncul ' apache ' nya  

6. Buat direktori baru dengan perintah 

    #mkdir /home/web 

7. buat file baru, disini penulis menggunakan LibreOffice Writer
simpan file yang sudah diedit ke direktori /home/web

  

9. dalam direktori /var/www terdapat file index.html
jika file index.html tersebut terkunci, maka perlu adanya Hak Akses File. ketikkan perintah
#chmod 777 /var/www/index.html 

edit file menggunakan bahasa pemrograman html dengan perintah gedit atau klik kanan pada file, pilih open with teks editor 

10 Lakukan #apt-get update

dan setelah itu Buka web browser lalu ketikan IP kalian masing-masing dan setelah di ketikan akan tampil seperti gambar berikut :

buka web broser, ketikkan localhost
maka semua file dalam direktori www akan muncul seperti berikut : 

terima kasih ^_^
selamat mencoba !!!

PROGRAM RAPTOR

Permasalahan

Buatlah flowchart untuk dimasukkan oleh pengguna. Keliling dan luas persegi panjang ditampilkan ke layar.

Contoh:

Masukkan panjang sisi

Luas persegi panjang: 50

Keliling persegi panjang: 25

Cara Penyelesaian Masalah

Untuk menghitung luas dan keliling dari sebuah persegi panjang maka dibutuhkan data berapa panjang sisi dari persegi panjang tersebut, panjang tiap sisi dari persegi panjang tidak sama. Secara sistematis rumus untuk menghitung luas dan keliling persegi panjang adalah :

Luas Persegi : p * l

Keliling Persegi : 2 * p + l

Berikut adalah tampilan cara dari enter input :

- Struktur Data yang Dibutuhkan

·         Sisi : adalah variabel yang menampung panjang sisi persegi dan di definisikan dalam bentuk angka

·         Luas Persegi : adalah variabel penampung hasil perhitungan luas persegi

·         Keliling Persegi : adalah variabel penampung hasil perhitungan keliling persegi

- Input

Masukan yang diperlukan dalam permasalahan ini adalah bilangan yang melambangkan panjang sisi persegi dan disimpan dalam variabel sisi, pada flowchart dapat dibuat sebagai berikut:

- Output

Keluaran permasalahan ini adalah 2 buah nilai yaitu luas dan keliling lingkaran, sehingga output pada flowchart dapat dibuat sebagai berikut:

- Proses Penyelesaian

Terdapat dua buah kegiatan yang terjadi dalam proses dan dilakukan secara berurutan (sequences), yaitu perhitungan luas dan keliling dari persegi sesuai rumus yang telah dideklarasikan sebelumnya. Dalam penulisan flowchart dua kegiatan ini bisa digabung seperti

berikut ini :

Flowchart Keseluruhan dari Study Kasus Sederhana

  Contoh 1

  2. initstr

  3. luasling

4. Peluru2.c

5. Konversi.c

  6.kapital.c

  7. jhari.c

  8. maks31.c

Selamat Mencoba ^_^ !!!