Konfigurasi Mail Server ClearOS Menggunakan VMware

Read more...

Konfigurasi Samba ClearOS Menggunakan VMware

Read more...

Konfigurasi FTP Server ClearOS Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi FTP Server ClearOS Menggunakan VMware

Read more...

Konfigurasi Web Database ClearOS Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi Web Database ClearOS Menggunakan VMware

Read more...

Konfigurasi DNS Server ClearOS Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi DNS Server ClearOS Menggunakan VMware

Read more...

Konfigurasi DHCP Server ClearOS Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi DHCP Server ClearOS Menggunakan VMware

Read more...

Konfigurasi Ip Address ClearOS Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi Ip Address ClearOS Menggunakan VMware

Read more...

Konfigurasi DHCP Server Debian Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi DHCP Server Debian Menggunakan VMware

Read more...

Instalasi Debian

POLITEKNIK NEGERI TANAH LAUT
Instalasi Debian Menggunakan VMware

Read more...

Konfigurasi Mail Sever dan Web Mail Debian Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi Mail Sever dan Web Mail Debian Menggunakan VMware

Read more...

Instalasi Clear OS

POLITEKNIK NEGERI TANAH LAUT
Instalasi Clear OS

Read more...

Konfigurasi FTP Server Debian Menggunakan Vmware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi FTP Server Debian Menggunakan Vmware

Read more...

Konfigurasi DNS Server Debian Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi DNS Server Debian Menggunakan VMware

Read more...

Konfigurasi Web Server Debian Menggunakan Vmware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi Web Server Debian Menggunakan Vmware

Read more...

Konfigurasi IP Address Debian Menggunakan VMware

POLITEKNIK NEGERI TANAH LAUT
Konfigurasi IP Address Debian Menggunakan VMware

Read more...

DNS dan Web Server

POLITEKNIK NEGERI TANAH LAUT
DNS dan Web  Server

Read more...

WEB SERVER DAN WEB CLIENT

POLITEKNIK NEGERI TANAH LAUT
WEB SERVER DAN WEB CLIENT

2.1  Pengertian Web Server

Web adalah tampilan pada browser dengan alamat domain khusus untuk sistem penelitian ini. Web dapat dibangun dengan menggunakan bahasa HTML dan PHP dengan model tampilan menggunakan bahasa CSS. Web tersebut disimpan pada satu komputer yang disebut server. Server menyimpan program web dan database untuk dapat diakses oleh admin atau client dari browser. Website dapat dibangun menggunakan program notepad/notepad++ atau adobe dreasweaver. Web server adalah sebuah software yang memberikan layanan berbasis data dan berfungsi menerima permintaan dari HTTP atau HTTPS pada client yang dikenal dan biasanya kita kenal dengan nama web browser dan untuk mengirimkan kembali yang hasilnya dalam bentuk beberapa halaman web dan pada umumnya akan berbentuk dokumen HTML. Dalam bentuk sederhana web server akan mengirim data HTML kepada permintaan web browser sehingga akan terlihat seperti pada umumnya yaitu sebuah tampilan website.

Fungsi utama web server adalah untuk melakukan atau akan tranfer berkas permintaan pengguna melalui protokol komunikasi yang telah ditentukan sedemikian rupa. Halaman web yang diminta terdiri dari berkas teks, video, gambar, file dan banyak lagi. pemanfaatan web server berfungsi untuk mentransfer seluruh aspek pemberkasan dalam sebuah halaman web termasuk yang di dalam berupa teks, video, gambar atau banyak lagi.

Beberapa jenis web server di antanya adalah:

1.      Apache Web server / The HTTP Web server

2.      Apache Tomcat

3.      Microsoft windows Server 2008 IIS (Internet Information Services)

4.      Lighttpd

5.      Zeus Web server

6.      Sun Java System Web server

2.2  Web Server Apache

Apache merupakan web server yang paling banyak dipergunakan di Internet. Program ini pertama kali didesain untuk sistem operasi lingkungan UNIX. Namun demikian, pada beberapa versi berikutnya. Apache mengeluarkan programnya yang dapat dijalankan di Windows NT. Apache mempunyai program pendukung yang cukup banyak. Hal ini memberikan layanan yang cukup lengkap bagi penggunanya.

Beberapa dukungan Apache:

1.      Kontrol Akses, dapat dijalankan berdasarkan nama host atau nomor IP.

2.      CGI (Common Gateway Interface), yang paling terkenal untuk digunakan adalah PERL (Practical Extraction and Report Language), didukung oleh Apache dengan menempatkannya sebagai modul (mod_perl).

3.      PHP (Personal Home Page/PHP Hypertext Processor) merupakan program dengan metode semacam CGI, yang memproses teks dan bekerja di server. Apache mendukung PHP dengan menempatkannya sebagai salah satu modulnya (mod_php). Hal ini membuat kinerja PHP menjadi lebih baik.

4.      SSI (Server Side Includes) artinya dapat menyertakan sebuah file sebagai sebuah bagian dari dokumen pada saat masih berada di server dan sebelum dieksekusi dan sebelum data dikirimkan ke pengguna.

2.3 Keunggulan Web Server Apache

Web server apache mempunyai kelebihan, yaitu sebagai berikut:

1.      Apache termasuk dalam kategori freeware.

2.      Apache mudah sekali proses instalasinya jika dibanding web server lainnya seperti NCSA, IIS, dan lain-lain.

3.      Mampu beroperasi pada berbagai platform sistem operasi.

4.      Mudah mengatur konfigurasinya, Apache mempunyai hanya empat file konfigurasi.

5.      Mudah dalam menambahkan peripheral lainnya ke dalam platform web servernya.

2.4 Cara Kerja Web Server

Informasi web disimpan dalam dokumen yang disebut dengan halaman-halaman web (web pages). Web pages adalah file-file yang disimpan dalam komputer yang disebut dengan server-server web (web servers). Komputer-komputer membaca web page disebut sebagai web client. Web client menampilkan page dengan menggunakan program yang disebut dengan browser web (web browser). Browser web yang populer antara lain adalah Internet Explorer dan Netscape Navigator. Pada saat client (browser) meminta data web page kepada server, maka instruksi permintaan data oleh browser tersebut akan dikemas di dalam TCP yang merupakan protokol transport dan dikirim ke alamat yang dalam hal ini merupakan protokol berikutnya yaitu Hyper Text Transfer Protocol (HTTP) dan atau Hyper Text Transfer Protocol Secure (HTTPS).

Data yang diminta dari browser ke web server disebut dengan HTTP request yang kemudian akan dicarikan oleh web server di dalam komputer server. Jika ditemukan, data tersebut akan dikemas oleh web server dalam TCP dan dikirim kembali ke browser untuk ditampilkan. Data yang dikirim dari server ke browser dikenal dengan HTTP response. Jika data yang diminta oleh browser tersebut ternyata tidak ditemukan oleh web server, maka web server akan menolak permintaan tersebut dan browser akan menampilkan notifikasi error 404 atau Page Not Found. Meskipun proses atau cara kerja web server diatas seperti sangat rumit, tapi pada prakteknya proses tersebut berlangsung dengan sangat cepat. Bahkan bisa sampai tidak menyadari bahwa pada saat meminta suatu halaman web, ternyata hal itu membutuhkan proses yang sangat panjang sampai halaman tersebut dapat dilihat di browser.

2.5 Pengertian Web Cilent

Client adalah sebuah komputer yang terdapat dalam sebuah jaringan komputer yang meminta dan menggunakan layanan sumberdaya yang disediakan oleh komputer server, singkatnya client adalah pemakai layanan dari server. Sebenarnya client dan server merupakan sebuah sistem yang salig terkait dimana client meminta layanan dan server akan menyediakan layanan yang dapat digunakan oleh client. Web client memiliki hubungan dengan server dengan meminta layanan dari server. Web client merupakan perangkat lunak (software) penyedia interface untuk user. Web client bisa juga diartikan sebagai komputer tergabung dalam jaringanatau internet yang meminta informasi. Untuk dapat mengakses web server, web client menggunakan aplikasi yang disebut Web Browser.

Web client bisa juga disebut sebagai browser. Dengan adanya browser pengguna dapat berinteraksi dengan tulisan, gambar, video dan lain-lain yang terdapat pada halaman web di sebuah situs di WWW atau jaringan LAN lokal. Ada beberapa Web browser yang dapat di gunakan di komputer, yaitu, Mozilla Firefox, Safari, Konqueror, Opera, Flock, Epiphany, K-Meleon dan AOL Explorer. Pada saat ini Firefox merupakan Web browser terbaik yang banyak digunakan di Internet. Bagi mereka yang menggunakan Linux Ubuntu Firefox sudah langsung terinstalasi tanpa perlu menginstalasi lagi.

Cara kerja client yaitu melalui hubungan dengan server dengan meminta layanan yang disediakan oleh server. Misal untuk Email, biasanya server akan memberikan layanan dalam bentuk Email Reader. Dan untuk web biasanya server menyediakan layanan dalam bentuk browser.

2.6 Jenis-Jenis Web Client

Berikut adalah jenis-jenis web client:

1. Opera

Dikembangkan oleh Opera Software company adalah salah satu Web Browser dan juga Internet Suite. Jika firefox punya Add-ons, Opera punya “Opera Widgets”, sebuah aplikasi web kecil yang dijalankan bersamaan dengan Opera yang mempunyai kegunaan tertentu, layaknya Add-ons firefox.

2. Internet Exporer

Web browser besutan Microsoft Corporation biasanya dikenal dengan nama pendek IE, sejak 1995 IE mulai di masukan sebagai default sotware pada saat instalasi Sistem Operasi Windows, sejak tulisan ini dibuat IE belum lama ini meluncurkan versi IE8.

3. Mozilla Firefox

Dibuat oleh mozilla corporation, firefox adalah salah satu web browser open source yang dibangun dengan Gecko layout engine. Tak hanya handal firefox juga didukung oleh sejumlah Add-ons yang dapat diinstall terpisah yang memungkinkan pengguna melakukan sesuai dengan kegunaan Add-ons tersebut.

4. Flock

Flock adalab web browser yang dibangun dengan code mozilla frefox yang web browser ini khususkan menyediakan social networking dan Web 2.0. Flock didesain untuk memudahkan aktivitas online pengguna internet mengatur beberapa social networking, web mail, news feeds dan blogs yang mereka miliki.

5. Safari

Dibuat oleh Apple Inc, perusahaan yang juga memproduksi computer Macintosh, iPod, dan juga iPhone. dibangun dengan browser engine WebKit, WebKit juga adalah browser engine pertama yang lulus test Acid3.

6. K-Meleon

K-Meleon salah satu browser gratis dan open source di rilis dibawah Lisensi GNU General Public dan berjalan diplatform Microsoft Windows (Win32) operating systems. Dibangun di atas Gecko layout engine, layout engine yang sama seperti digunakan Mozilla Firefox.

7.      Google Chrome Browser

Fitur utama dari web browser ini adalah teknologi mesin Rendering WibKit yang mendukung platform diberbagai perangkat. Fitur Google Chrome memungkinkan penggunanya untuk menyimpan riwayat internet, riwatyat unduhan, mengelola bookmark, mode penyamaran, mengelola profil, dan lain-lain.

Read more...

TUTORIAL REMASTERING MAKULU LINUX

POLITEKNIK NEGERI TANAH LAUT

TUTORIAL REMASTERING

MAKULU LINUX

TI Politala Sistem Operasi 2B 

Read more...

GUI Pada Windows

POLITEKNIK NEGERI TANAH LAUT

GUI PADA WINDOWS

TI Politala Sistem Operasi 2B

Read more...

GUI Pada Linux

POLITEKNIK NEGERI TANAH LAUT

GUI PADA LINUX

TI Politala Sistem Operasi 2B

Read more...

CLI Pada Linux

POLITEKNIK NEGERI TANAH LAUT

CLI PADA LINUX

TI Politala Sistem Operasi 2B

Read more...

Tutorial Instalasi Linux [DUALBOOT]

POLITEKNIK NEGERI TANAH LAUT

TUTORIAL INSTALASI LINUX

TI Politala Sistem Operasi 2B

Read more...

Command Prompt Pada Windows

POLITEKNIK NEGERI TANAH LAUT

COMMAND PROMPT PADA WINDOWS

TI Politala Sistem Operasi 2B

Read more...

Tutorial Instalasi Windows Mudah

POLITEKNIK NEGERI TANAH LAUT

INSTALASI WINDOWS

TI Politala Sistem Operasi 2B

Read more...

SISTEM OPERASI

POLITEKNIK NEGERI TANAH LAUT

SISTEM OPERASI

TI Politala Sistem Operasi 2B

Read more...

Graf dan Pohon Dalam Algoritma Pemrograman C++

POLITEKNIK NEGERI TANAH LAUT

GRAF DAN POHON

TI Politala Algoritma Pemrograman 2B

Pengertian Graf
G membentuk suatu graf jika terdapat pasangan himpunan (V(G), E(G)), dimana V(G) (simpul pada graf G) tidak kosong dan E(G) (rusuk pada graf G). Jika v dan w adalah sepasang simpul yang berbeda di G, melambangkan rusuk di G dan jika e=vw adalah rusuk di maka:

a. v dan w berikatan (adjacent) di G

b. Rusuk e hadir (joining) simpul v dan w di G

c. v dan w adalah simpul ujung rusuk di e

d. Rusuk e hadir (incident) di simpul v dan w atau sebaliknya dikatakan simpul v dan w hadir pada rusuk e.

Menutut Rosen berdasarkan ada tidaknya bobot, graf dikelompokkan menjadi dua jenis yaitu graf berbobot dan graf tak-berbobot.

Jenis-Jenis Graf

a. Berdasarkan ada tidaknya loop atau rusuk ganda pada suatu graf, maka graf digolongkan menjadi dua jenis, yaitu:
1) Graf sederhana (simple graph) yaitu graf yang tidak mengandung loop maupun rusuk ganda. Gambar G1 di bawah ini adalah contoh graf sederhana.

(Gambar 1 Graf Sederhana G1)

2) Graf tak-sederhana (unsimple graph) yaitu graf yang mengandung loop atau rusuk ganda. Gambar Graf G2 di bawah ini adalah contoh graf tidak sederhana yang mengandung rusuk ganda dan Graf G3 adalah contoh graf tidak sederhana yang mengandung loop.

(Gambar 2 Graf Tak Sederhana G2)

(Gambar 2 Graf Tak Sederhana G3)

b. Berdasarkan jumlah titik pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1) Graf berhingga (limited graph) adalah graf yang jumlah titiknya n berhingga.
2) Graf tak berhingga (unlimited graph) adalah graf yang jumlah titiknya n tidak berhingga banyaknya.
c. Berdasarkan orientasi arah pada rusuk, maka secara umum graf dibedakan atas dua jenis:
Graf tak berarah (undirect graph) adalah graf yang rusuknya tidak mempunyai orientasi arah. Urutan pasangan titik yang terhubung oleh rusuk tidak diperhatikan. Sehingga (𝑣1, 𝑣2) = (𝑣2, 𝑣1) adalah rusuk yang sama. Graf tak berarah sering dipakai pada jaringan saluran telepon karena rusuk pada graf tak berarah menyatakan bahwa saluran telepon dapat beroperasi pada dua arah. Graf G4 di bawah ini merupakan contoh graf tak berarah.

 (Gambar 4 Graf Tak Berarah G4)

Keterhubungan
Sebuah graf disebut terhubung jika untuk setiap dua titik terdapat rusuk yang menghubungkan kedua titik tersebut.

a. Jalan (walk), Walk dengan panjang k pada sebuah graf G adalah rangkaian terurut dari k rusuk pada graf G dengan bentuk : 𝑢𝑣, 𝑣𝑤, 𝑤𝑥, … , 𝑦𝑧 ;

Walk tersebut dinyatakan dengan 𝑢𝑣, 𝑣𝑤, 𝑤𝑥, … , 𝑦𝑧 atau dengan kata lain walk antara u sampai z (Robin J. Wilson & John J. Watkin, 1990 : 34).

b. Jejak (Trail) adalah walk dengan semua rusuk dalam barisan adalah berbeda (Munir, 2009 :370).

c. Lintasan (Path) adalah sebuah trail tanpa titik berulang (Robin J. Wilson & John J. Watkin, 1990: 35).

d. Sikel (Cycle) adalah sebuah trail tertutup yang titik awal dan akhir merupakan titik yang sama.

e. Graf Hamilton, Sirkuit Hamilton adalah lintasan yang melalui tiap titik dalam graf tepat satu kali. Graf Hamilton adalah graf yang memiliki sirkuit Hamilton. Contoh sirkuit Hamilton adalah (𝑣1, 𝑣2, 𝑣3, 𝑣4) pada G1. Contoh Graf Hamilton adalah G1.

Vehicle Routing Problem (VRP)

Vehicle Routing Problem (VRP) dapat didefinisikan sebagai permasalahan mencari rute dengan biaya minimum dari suatu depot ke pelanggan yang letaknya tersebar dengan jumlah permintaan yang berbeda-beda. Rute dibuat sedemikian rupa sehingga setiap pelanggan dikunjungi hanya satu kali oleh satu kendaraan. Seluruh rute berawal di depot, dan jumlah permintaan dalam satu rute tidak boleh melebihi kapasitas kendaraan.

VRP diperkenalkan pertama kali oleh Dantzig dan Ramzer pada tahun 1959 memegang peranan penting dalam pengaturan distribusi dan menjadi salah satu masalah yang dipelajari secara luas.VRP merupakan perhitungan formulasi dengan mempertimbangkan masalah jumlah kendaraan dan rute yang akan dilalui. Tujuan yang ingin dicapai dalam VRP di antaranya (Toth & Vigo, 2002):

1. Meminimalkan ongkos perjalanan secara keseluruhan yang dipengaruhi oleh keseluruhan jarak yang ditempuh dan jumlah kendaraan yang digunakan.

2. Meminimalkan jumlah kendaraan yang digunakan untuk melayani semua pelanggan.

3. Menyeimbangkan rute.

4. Meminimalkan keluhan pelanggan.

Pengertian Pohon

Graf T merupakan sebuah pohon jika dan hanya jika ada satu jalur sederhana pada setiap pasang simpul (i, j). Jika N = |V|, maka ada N 1 sisi (busur) dan semuanya terhubung, tanpa ada kalang (loop). Setiap simpul dapat menjadi akar pada pohon tersebut. Sebuah pohon dapat direpresentasikan dengann menyusun simpulsimpul dalam suatu urutan tertentu yang dimulai dari akar. Beberapa definisi pada pohon adalah sebagai berikut:

1. Setiap simpul (kecuali akar) hanya memiliki satu simpul orang tua.

2. Setiap simpul memiliki 0 atau lebih anak.

3. Sebuah sisi dengan 0 anak adalah merupakan daun.

Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit.

Hutan (forest) adalah kumpulan pohon yang saling lepas, atau graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon. Pohon mempunyai bilangan kromatis = 2.

Sifat-sifat Pohon:

1. Teorema. Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen:

a. G adalah pohon.

b. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

c. G terhubung dan memiliki m = n – 1 buah sisi.

d. G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi.

e. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

f. G terhubung dan semua sisinya adalah jembatan.

2. Teorema di atas dapat dikatakan sebagai definisi lain dari pohon.

Pohon Merentang (Spanning Tree)

1. Pohon merentang dari graf terhubung adalah upagraf merentang yang berupa pohon.

2. Pohon merentang diperoleh dengan memutus  sirkuit di dalam graf.

3. Setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang.

4. Graf tak-terhubung dengan k komponen mempunyai k buah hutan merentang yang disebut hutan merentang (spanning forest).

Aplikasi Pohon Merentang

1. Jalan-jalan seminimum mungkin yang menghubungkan semua kota sehingga setiap kota tetap terhubung satu sama lain.

2. Perutean (routing) pesan pada jaringan komputer.

Pohon Rentang Minimum

1. Graf terhubung-berbobot mungkin mempunyai lebih dari 1 pohon merentang.

2. Pohon rentang yang berbobot minimum – dinamakan pohon merentang minimum (minimum spanning tree).

Graf Pohon
Graf pohon (tree) adalah suatu graf terhubung yang tidak memuat siklus. Suatu graf yang setiap titiknya mempunyai derajat satu disebut daun (pendant vertex)

Selanjutnya, akan diberikan definisi beberapa kelas graf pohon. Suatu graf bintang K, n (star) adalah suatu graf terhubung yang mempunyai satu titik berderajat n yang disebut pusat dan titik lainnya berderajat satu (Chartrand dkk., 1998).

Graf pohon disebut graf bintang ganda (double star) jika graf pohon tersebut mempunyai tepat dua titik x dan y berderajat lebih dari satu. Jika x dan y berturutturut berderajat a+1 dan b+1, dinotasikan dengan Sa,b , (Chartrand dkk., 1998)

Graf ulat (caterpillar graf) adalah graf pohon yang memiliki sifat apabila dihapus semua daunnya akan menghasilkan lintasan (Chartrand dkk., 1998).

Graf dan Algoritma Routing

Pada jaringan komputer, aliran setiap paket dapat dimodelkan dengan menggunakan graf yang memiliki bobot. Simpul pada graf merepresentasikan router, sedangkan busur pada graf merepresentasikan subnet. Routing adalah proses untuk meneruskan paket dari suatu simpul ke simpul yang lainnya dengan berdasarkan asas jalur terpendek. Tujuannya adalah agar pengiriman paket tersebut dapat dilakukan secara efektif dan efisien. Algoritma routing untuk mendapatkan jalur terpendek diantaranya adalah algoritma Dijkstra dan algoritma Kruskal.

Algoritma Routing

1. Algoritma Dijkstra (Pencarian Jalur Terpendek)

Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama-tama tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap. Inilah urutan logika dari algoritma Dijkstra:

1. Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi).

2. Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.

3.Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru.

4. Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

5. Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

Dibawah ini penjelasan langkah per langkah pencarian jalur terpendek secara rinci dimulai dari node awal sampai node tujuan dengan nilai jarak terkecil.

1. Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai

2. Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).

3. Node 2 diset menjadi node keberangkatan dan ditandai sebagi node yang telah terjamah. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terjamah. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).

4. Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11(9+2).

5. Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-36-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai

2. Algoritma Kruskal

Algoritma Kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum tree untuk sebuah graf berbobot yang terhubung. Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik, dimana dimana berat total dari semua tepi diatas pohon diminimalkan. Jika grafik tidak terhubung, maka mmenemukan hutan rentang minimum (pohon rentan minimum untuk setiap komponen terhubung). Algoritma Kruskal juga tergolong algoritma Greedy dalam teori graf yang digunakan untuk mencari minimum spanning tree. Algoritma ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan oleh Joseph Kruskal. Dasar pembentukan algoritma Kruskal berasal dari analogi glowing forest. Glowing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf G adalah dengan cara mengambil satu persatu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakain sedikit. Algoritma Kruskal akan terus menambah sisi-sisi kedalamm hutan yang sesuai hingga akhirnya tidak akan ada lagi forest, melainkan hanyalah sebuah pohon yang merentang minimum. Secara umum Algoritma Kruskal ditulis:

1. T masih kosong
2. Pilih sisi (i, j) dengan bobot minimum
3. Pilih sisi (i, j) dengan bobot minimum yang berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T
4. Ulangi langkah 3 sebanyak (n-2) kali
5. Total langkah (n-1) kali
6. Karakteristik Algoritma Kruskal

a. Sifat Algoritma Kruskal
1. Bekerja tidak hanya dengan grafik diarahkan.
2. Bekerja dengan bobot dan tidak grafik tertimbang. Tapi yang lebih menarik, apabila tepi yang berbobot.
3. Kruskal adalah jenis algoritma yang menghasilkan solusi optimal MST.
4. Langkah-Langkah Algoritma Kruskal
Langkah-langkah algoritma Kruskal adalah sebagai berikut:
1. Atur tepi berat: pling berat pertama dan terberat terakhir.
2. Pilih yang ringan tidak diperiksa tapi dari diagram.
3. Tambahkan tepi memilih ini ke pohon, hanya jika hal itu tidak membuat siklus.
4. Menghentikan proses kapanpun n-1 tapi lebihditambahkan kepohon.

Contoh algoritma Kruskal sebagai berikut:
Berikut adalah graf berbobot yang akan dicari pohon merentang minimum nya,dengan bobot sebesar 90.

AD dan CE adalah sisi dengan bobot terkecil, pilih sembarang antara AD dan CE, pilih AD.
Karena CE sisi terkecil berikutnya, pilih CE

 Selanjutnya, pilih sisi DF dengan bobot 6.

AB dan BE adalah sisi dengan bobot terkecil yang belum dipilih, pilih sembarang antara AB dan BE, pilih AB.

Karena BE sisi terkecil berikutnya, pilih BE

Simpul G adalah simpul terakhir yang belum dipilih, oleh karena itu pilih sisi yang terhubung dengan simpul G, yaitu GE dan GF, karena GE memiliki bobot lebih kecil, pilih GE.

Karena semua simpul telah dipilih, maka pohon merentang minimum ditunjukkan dengan warna hijau. Dengan bobot sebesar 39. Dengan menggunakan struktur data sederhana kompleksitas waktu algoritma ini adalah O (E log E) yang ekuivalen dengan O (E log V).

Keduanya ekuivalen karena:

- E bernilai maksimal V² dan log V² = 2 x logV = O (log V)
- Jika kita tidak menghiraukan simpulsimpul yang terisolasi, V <= 2E, jadi log V adalah O (log E)

Hasil tersebut diperoleh dengan melalui beberapa tahap, pertama, urutkan sisi-sisi dengan menggunakan comparison sort dengan waktu O (E log E). Kemudian, gunakan himpunan struktur data yang disjoint untuk menjaga tempat simpul yang mana ada di komponen mana. Kemudian, tunjukkan O(E) operasi, untuk menemukan operasi- operasi dan kemungkinan satu union untuk setiap sisi. Sehingga, waktu total adalah O (E log E) = O (E log V). Misalkan sisi-sisi yang ada telah diurutkan atau bisa diurut dalam waktu yang linear (dengan counting sort atau radix sort), algoritma ini dapat menggunakan himpunan struktur data yang disjoint dengan lebih rumit, sehingga memiliki kompleksitas waktu O (E α(V)), dimana α adalah inverse dari fungsi Ackermann yang bernilai single, dan tumbuh dengan sangat lambat.
Berikut adalah contoh dari algoritma Dijikstra :

#include <iostream>

#define INF 99999

using namespace std;

main()

{

    int n=10,i,j,start;

    int G[n][n],tempGraf[n][n],jarak[n]={0,0,0,0,0,0,0,0,0,0},visit[n],temp[n],count;

    G[0][0]=0;    G[0][1]=3000; G[0][2]=4780;  G[0][3]=0;   G[0][4]=0;    G[0][5]=5600; G[0][6]=0;   G[0][7]=0;   G[0][8]=0;   G[0][9]=0;

    G[1][0]=3000; G[1][1]=1800; G[1][2]=400;   G[1][3]=0;   G[1][4]=0;    G[1][5]=0;    G[1][6]=0;   G[1][7]=0;   G[1][8]=0;   G[1][9]=0;

    G[2][0]=4780; G[2][1]=1800; G[2][2]=0;     G[2][3]=0;   G[2][4]=0;    G[2][5]=0;    G[2][6]=1350;G[2][7]=0;   G[2][8]=900; G[2][9]=0;

    G[3][0]=0;    G[3][1]=400;  G[3][2]=0;     G[3][3]=0;   G[3][4]=600;  G[3][5]=0;    G[3][6]=1340;G[3][7]=0;   G[3][8]=0;   G[3][9]=0;

    G[4][0]=0;    G[4][1]=0;    G[4][2]=0;     G[4][3]=600; G[4][4]=0;    G[4][5]=1370; G[4][6]=0;   G[4][7]=0;   G[4][8]=0;   G[4][9]=0;

    G[5][0]=5600; G[5][1]=0;    G[5][2]=0;     G[5][3]=0;   G[5][4]=1370; G[5][5]=0;    G[5][6]=1450;G[5][7]=0;   G[5][8]=0;   G[5][9]=3320;

    G[6][0]=0;    G[6][1]=0;    G[6][2]=1350;  G[6][3]=1340;G[6][4]=0;    G[6][5]=1450; G[6][6]=0;   G[6][7]=150; G[6][8]=0;   G[6][9]=2530;

    G[7][0]=0;    G[7][1]=0;    G[7][2]=0;     G[7][3]=0;   G[7][4]=0;    G[7][5]=0;    G[7][6]=150; G[7][7]=0;   G[7][8]=400; G[7][9]=1330;

    G[8][0]=0;    G[8][1]=0;    G[8][2]=900;   G[8][3]=0;   G[8][4]=0;    G[8][5]=0;    G[8][6]=0;   G[8][7]=400; G[8][8]=0;   G[8][9]=0;

    G[9][0]=0;    G[9][1]=0;    G[9][2]=0;     G[9][3]=0;   G[9][4]=0;    G[9][5]=3320; G[9][6]=2530;G[9][7]=1330;G[9][8]=0;   G[9][9]=0;

    for(i = 0;i < n ;i++)

    {

        for (j=0;j<n;j++)

        {

            cout<<"Matriks "<<"["<<i<<"]"<<"["<<j<<"]"<<" : ";

            cout<<G[i][j]<<endl;

        }

    }

    cout<<"Masukan Vertex Asal : ";

    cin>>start; 

    for(i=0;i<n;i++)

    {

        for (j=0;j<n;j++)

        {

            if (G[i][j] == 0)

            {

                tempGraf[i][j] = INF;

            }

            else{

                tempGraf[i][j] = G[i][j];

            }

        }

    }

    for (i = 0;i<n;i++)

    {

        jarak[i] = tempGraf[start][i];

        temp[i] = start;

        visit[i] = 0;

    }

    jarak[start] = 0;

    visit[start] = 1; 

    count =1; ///dimulai dari 1 karena kita tidak akan menghitung vertex asal lagi

    ///proses untuk menghitung vertex yang dikunjungi

    int jarakmin,nextvertex;

    while (count < n-1)

    {

        jarakmin = INF;

        for (i=0;i<n;i++)

        {

            ///jika jarak lebih kecil dari jarak minimum dan vertex belum dikunjungi

            /// maka jarak minimum adalah jarak yang sudah dibandingkan sebelumnya dengan jarakmin

                if(jarak[i] < jarakmin && visit[i]!=1)

                {

                    jarakmin = jarak[i];

                    nextvertex = i; ///untuk memberikan vertex pada jarak minimum

                }

        } 

        /// untuk mengecek vertex selanjutnya yang terhubung dengan vertex lain yang memiliki jarak minimum

        visit[nextvertex] = 1;

        for(i = 0;i<n;i++)

        {

            if(visit[i]!=1)

            {

                if(jarakmin+tempGraf[nextvertex][i]<jarak[i])

                {

                    jarak[i] = jarakmin+tempGraf[nextvertex][i];

                    temp[i] = nextvertex;

                }

            }

        }

    count++;

    }

    ///nenampilkan jalur dan jarak untuk setiap vertex

    int a[n+1],k;

    for (i = 0; i < n ;i++)

    {

        if(i!=start)

        {

            cout<<"\nHasil jarak untuk vertex ke-"<<i<<" adalah "<<jarak[i]<<endl;

            j=i;

            cout<<"<-"<<i<<" ";

            while(j!=start)

            {

                j=temp[j];

                cout<<j;

                if(j!=start)

                {

                    cout<<"<-";

                }

            }

        }

        jarak[i]+=jarak[i];

    }

    cout<<"\nTotal Jaraknya adalah "<<jarak[n-1];

    return 0;

}

Jika ingin contoh program yang lainnya, silahkan download pada link :
Algoritma pohon :
https://drive.google.com/file/d/1CBT0Sw5U2J3hIn6dT-9t_YDxK6JZ45BT/view?usp=sharing
Algoritma Graf :
https://drive.google.com/file/d/1T0GCpQ5stzW2Xh_NVzl54sNe-3wTUJZH/view?usp=sharing
Algoritma Djikstra :
https://drive.google.com/file/d/1VlTE9zMMRZo0RJlN03QX9gdpLgR0pNr3/view?usp=sharing
Algoritma Kruskal :
https://drive.google.com/file/d/1n7jGdNuK5pzuKEuUnJ-WwUtgRp_-5juY/view?usp=sharing

DAFTAR PUSTAKA

Muhidin, Asep. 2010. Modul Kuliah Pemrograman Bahasa C++, Bekasi; Penerbit Zeyrank Offset.

Hasmawati. 2015. “BAHAN AJAR TEORI GRAF”. Fakultas Matematika Dan Ilmu Pengetahuan Alam Universitas Hasanuddin.

Siregar, Indra. 2009. “Penerapan Graf Pada Algoritma Routing”. Jurnal. Program Studi Teknik Teknik Informatika, Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung.

 
https://kaazima.blogspot.com/2013/12/contoh-program-c-program-tree-c-sederhana.html
https://galehfatmaea.blogspot.com/2014/05/graph-c.html

Read more...