PENERAPAN ALGOITMA DIJKSTRA DALAM MENCARI LINTASAN TERPENDEK PADA JARINGAN KOMPUTER

LPPM Politeknik Bengkalis

PENERAPAN ALGOITMA DIJKSTRA DALAM MENCARI LINTASAN TERPENDEK PADA JARINGAN KOMPUTER Sri Mawarni Teknik Elektro Politeknik Bengkalis Jl. Batin Alam, Sei-Alam, Bengkalis-Riau [email protected]

Abstrak Makalah ini membahas tentang salah satu penerapan teori graf dalam kehidupan yaitu penerapan algoritma Dijkstra (yang merupakan bagian teori dalam graf) pada jaringan komputer, jaringan komputer yang dimaksud pada makalah ini hanyalah secara umum (tidak termasuk jaringan internet). Dalam hal ini jaringan komputer digambarkan sebagai sebuah graf. Satu komputer dalam sebuah jaingan dianggap sebagai suatu simpul sedangkan kabel atau penghubung antar komputer dianggap sebagai sisi graf. Sisi didalam graf menyatakan saluran komunikasi (sering disebut link). Setiap sisi di-assign dengan sebuah label nilai yang disebut bobot atau weigh). Bobot tersebut dapat menyatakan jarak geografis (dalam kilometer), kecepatan transfer data, atau delai transmisi (waktu pengiriman). Setiap router memperlihatkan sebuah tabel yang disebut tabel rute (routing table). Tabel rute berisi router asal, router tujuan, dan simpul antara yang dilalui. Mencari lintasan terpendek dari router asal ke router tujuan dapat diartikan sebagai menentukan lintasan terpendek dari simpul asal ke simpul tujuan di graf yang mempresentasikan jaringan komputer tersebut. Algoritma Dijkstra adalah algoritma yang banyak digunakan untuk mencari lintasan terpendek. Tujuan pembuatan makalah ini adalah agar pembaca dapat mengerti dan mereprentasikan jaringan dalam bentuk graf. Dengan demikian pembaca dapat lebih mengerti mengenai aliran data dan juga hubungan antara satu komputer dengan komputer lain yang terjadi dalam satu jaringan. Kata kunci : graf, jaringan komputer, algoritma Dijkstra.

1. PENDAHULUAN Di era taknologi kini, jaringan komputer sudah sangat umum digunakan dalam berbagai aspek kehidupan masyarakat. Hampir setiap perusahaan atau institusi memiliki jaringan komputer yang berfungsi untuk mendukung aliran data dan informasi yang berlangsung dalam perusahaan atau institusi tersebut. Jaringan komputer terdiri dari sejumlah komputer yang terhubung satu sama lain melalui saluran komunikasi (misalnya kabel, serat optic, gelombang mikro, gelombang radio). Antara satu komputer dengan komputer lain sering kali terpisah jauh secara geografis (antar kota atau antar negara) atau berada dalam wilayah yang sama (dalam satu gedung,

dalam satu area, dsb). Pesan yang dikirim dari satu komputer ke komputer lain umumnya dipecah menjadi sejumlah paket data yang berukuran lebih kecil. Saluran komunikasi yang digunakan untuk menghantarkan paket mempunyai keterbatasan kecepatan transmisi (umumnya kecepatan transmisi dinyatakan dalam satuan kbps-kilobit per second). Untuk menyampaikan paket data dari satu komputer ke komputer lainnya, sistem jaringan komputer harus dapat melakukan pemilihan rute yang tepat agar paket dapat sampai ke komputer tujuan dalam waktu yang cepat. Permasalahannya adalah bagaimana menentukan rute yang tepat sehingga paket data dapat sampai ke computer penerima dalam waktu yang sesingkat mungkin. Dengan menggunakan rute tersebut,

Disampaikan Pada Seminar Nasional Industri dan Teknologi [SNIT] 2008 Bengkalis, 03-04 Desember 2008

29


paket data yang sampai ke suatu komputer dapat diarahkan ke komputer tetangga yang tepat sehingga paket menuju komputer penerima dengan delai (delay) waktu yang minimum. Dengan kata lain, kita harus menentukan lintasan terpendek yang akan dilalui oleh paket tersebut dari komputer pengirim ke komputer penerima. Perutean yang diharapkan adalah perutean adaptif (adaptive routing). Perutean adaptif bearti sistem jaringan komputer dapat menentukan rute baru apabila terjadi perubahan topologi jaringan (misalnya ada penambahan router baru, kerusakan pada suatu router sehingga router tersebut tidak bisa dilalui, atau perubahan kecepatan transmisi antar router) Studi mengenai jaringan komputer ini sendiri juga semakin banyak dipelajari dan menjadi suatu topik yang menarik untuk dipelajari. Akan tetapi, karena perubahannya yang sangat pesat, orang-orang yang berusaha untuk melakukan studi-studi tersebut haruslah lebih sering memeriksa perkembangan baru apa saja yang telah terjadi dan diaplikasikan dalam jaringan komputer.

himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. b. Jenis-jenis graf. Graf dapat dikelompokkan menjadi beberapa jenis tergantung dari sudut pandang pengelompokaknya. - Graf sederhana (simple graph), yaitu graf yang tidak mengandung gelang maupun sisi ganda. Pada graf sederhana sisi adalah pasangan tak terurut (unordered pairs), jadi menuliskan sisi (u, v) sama saja dengan (v, u). - Graf tak- sederhana (unsimple graph), yaitu graf yang mengandung sisi ganda atau gelang. Ada dua macam graf tak sederhana yaitu graf ganda dan graf semu. Graf ganda adalah graf yang mengandung sisi ganda. Sedangkan graf semu adalah graf yang mengandung gelang (loop). Gambar 1. Tiga buah graf : (a). graf sederhana, (b). graf ganda, dan (c). graf semu.

2. LANDASAN TEORI 2.1.Teori Graf Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah , bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. a. Definisi Graf Secara matematis graf didefinisikan sebagai berikut : Graf G didefinisikan sebagai pasangan himpunan (V, E) ditulis dengan notasi G = (V, E) yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (verticase atau node) dan E adalah

-

Graf tak- berarah (undirected graph), yaitu graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak berarah urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan, jadi (u, v) = (v, u).

Gambar 2. (a). graf berarah, (b). graf ganda berarah

Pada graf berarah (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata lain (u, v) ≠ (v, u). untuk busur (u, v) simpul u dinamakan simpul asal (initial vertex) dan


30


simpul v dinamakan smpul terminal (terinal vertex). 2.2. Definisi-definisi. Graf merupakan sesuatu yang sangat penting dalam jaringan, dimana objek utamanya adalah kumpulan simpul dengan hubungan satu atau dua arah di antara simpul-simpul tersebut. Berikut adalah kumpulan definisi dan terminologi yang berkaitan dalam pembahasan lintasan terpendek. Definisi 2.2.1. (Algoritma) Algoritma adalah urutan logis langkah-langkah penyelesaian masalah yang disusun secara sistematis. Yang dapat dinyatakan secara deskriptif atau dengan bahasa pemograman. Definisi 2.2.2. (Graf berbobot) Graf berbobot adalah graf yang setiap sisi nya diberi sebuah harga (bobot). Gambar 3. Graf Berbobot

. Definisi 2.2.3. Lintasan (Path) Lintasan yang panjangnya n dari simpul awal vo ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2, … , vn-1, en, vn, sedemikian sehingga e1 = (v0,v1), e2 = (v1,v2), … , en = (vn-1,vn) adalah sisi-sisi dari graf G. Panjang lintasan adalah jumlah sisi dalam lintasan tersebut.

3. LINTASAN TERPENDEK Persoalan mencari lintasan terpendek (shortest path problem) dalam graf merupakan persoalan optimasi. Pencarian lintasan terpendek termasuk masalah yang paling umum dalam suatu weighted-connected graph. Yang akan dibahas di sini adalah algoritma Dijkstra yaitu mencari lintasan terpendek dari suatu verteks asal tertentu ke setiap verteks lainnya (algoritma ini juga berfungsi sangat optimal pada masalah singledestination). 3.1.Algoritma Dijkstra Algoritma Dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip greedy yang menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukkannya ke dalam himpunan solusi. Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G. Dalam naskah aslinya, algoritma Dijkstra diterapkan untuk mencari lintasan tependek pada graf berarah. Namun algoritma ini juga benar untuk graf tak-berarah. Algoritma Dijkstra dimulai dari sebuah simpul asal dan dalam setiap iterasinya menambahkan sebuah verteks lain ke lintasan terpendek pohon merentang. Verteks ini merupakan titik terdekat ke akar namun masih di luar bagian pohon.: 3.2. Jaringan Komputer Jaringan komputer adalah kumpulan komputer dan peralatan lainnya yang terhubung. Informasi dan data bergerak melalui kabel atau koneksi nirkabel lain, sehingga memungkinkan pengguna jaringan komputer untuk saling bertukar dokumen dan data, mencetak pada printer yang sama, atau bersama sama menggunakan suatu hardware/software yang terhubung dengan jaringan.


31


Tiap komputer, printer, atau periferal yang terhubung dengan jaringan disebut node. Sebuah jaringan komputer dapat memiliki dua, puluhan, ribuan atau bahkan jutaan node. Sebuah jaringan terdiri dari 2 atau lebih komputer yang saling berhubungan diantara satu dengan yang lain, dan saling berbagi sumber daya seperti printer, pertukaran file, atau memungkinkan untuk saling berkomunikasi secara elektronik. Komputer yang terhubung tersebut, dimungkinkan berhubungan dengan media kabel, saluran telepon, gelombang radio, satelit, atau sinar infra merah.

berfungsi sebagai flag atau dengan struktur liked-list. Informasi lintasan dapat diketahui dengan pencatatan predesesor dari setiap verteks yang dilakukan pada saat update harga minpath tersebut (fungsi minimum). Jika minpath[t] di-update dengan (minpath[w] + Weight [w, t]) maka predesesor dari t adalah w. Pada tahap inisialisasi predesesor setiap verteks diisi oleh vs. Algoritma Dijkstra membuat label yang menunjukkan simpulsimpul. Label-label ini melambangkan jarak dari simpul asal ke suatu simpul lain. Dalam graf, terdapat dua macam label, sementara dan permanen. Label sementara diberikan untuk simpul-simpul yang belum dicapai. Nilai yang diberikan untuk label sementara ini dapat beragam.

4. HASIL DAN PEMBAHASAN 4.1. Analisa Algoritma Dijkstra. Pada setiap langkah ambil sisi yang berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan terpendek diantara semua lintasannya ke simpul-simpul yang belum terpilih. Selengkapnya algoritma Dijkstra adalah sebagai berikut : 1. Inisialisasi W berisi mula-mula hanya vs, field minpath tiap verteks v dengan Weight[vs, v], jika ada sisi tersebut, atau, +∞ jika tidak ada. 2. Lalu, dalam iterasi lakukan hingga (V-W) tak tersisa (atau dalam versi lain: jika ve ditemukan) dari field minpath tiap verteks cari verteks w dalam (V-W) yang memiliki minpath terkecil yang bukan tak hingga. Jika ada w maka masukkan w dalam W. Update minpath pada tiap verteks t adjacent dari w dan berada dalam (VW) dengan: minimum (minpath[t], minpath[w] + weight [w, t]).

Label permanen diberikan untuk simpulsimpul yang sudah dicapai dan jarak ke simpul asal diketahui. Nilai yang diberikan untuk label ini ialah jarak dari simpul ke simpul asal. Suatu simpul pasti memiliki label permanen atau label sementara. Tetapi tidak keduanya. Gambar 4 : (a). Simpul A berlabel sementara dengan jarak 0, (b). Simpul B berlabel permanen dengan jarak 5 5

0

A

B

(a)

(b)

Algoritma dimulai dengan menginisialisasi simpul manapun di dalam graf (misalkan simpul A) dengan label permanen bernilai 0 dan simpul-simpul sisanya dengan label sementara bernilai 0. Gambar 5 Inisialisasi awal 0 0

2

B

5

A

Verteks-verteks dalam W dapat dibedakan dari verteks dalam (V-W) dengan suatu field yang

D

3


0

6 C

0

32


Algoritma ini kemudian memilih nilai sisi terendah yang menghubungkan simpul dengan label permanent (dalam hal ini simpul A) ke sebuah simpul lain yang berlabel sementara (misalkan simpul B).

Gambar 8 : Semua nilai simpul menjadi permanent

2

Kemudian label simpul B di-update dari label sementara menjadi label permanen. Nilai simpul B merupakan penjumlahan nilai sisi dan nilai simpul A.

2 B 0 0 D

C

0

Langkah selanjutnya ialah menemukan nilai sisi terendah dari simpul dengan label sementara, baik simpul A maupun simpul B (misalkan simpul C). Ubah label simpul C menjadi permanen, dan ukur jarak ke simpul A. Gambar 7 : Nilai simpul C berubah. 2 B

0

2

5

A

0

D

3

6 C

B

5 6

A

3

C

7 D

3

Lamanya waktu untuk menjalankan Algoritma Dijkstra pada suatu graf dengan E (himpunan sisi) dan V (himpunan simpul) dapat dinyatakan sebagai fungsi E dan V menggunakan notasi Big-O.

Gambar 6 : Nilai simpul B menjadi permanen

A

2

0

3

Waktu yang dibutuhkan algoritma Dijkstra untuk bekerja ialah sebesar O(V*log V + E). Implementasi paling sederhana dari algoritma Dijkstra ialah penyimpanan simpul dari suatu himpunan ke dalam suatu array atau list berkait. 4.1. Lintasan Terpendek Jaringan Komputer.

dari

Routing

Jaringan komputer dapat dimodelkan sebagai sebuah graf terhubung dengan setiap simpul menyatakan sebuah komputer bisa berupa terminal komputer atau router . Router adalah kompute yang didedikasikan untuk mengarahkan pesa, dalam hal ini di asumsikan simpul menyatakan router, sedangkan terminal komputer yang menyatakan end user dianggap cabang dari router). Sisi di dalam graf menyatakan saluran komunukasi (link), setiap sisi di-assign dengan sebuah label nilai (bobot atau weight). Bobot tersebut dapat menyatakan jarak geografis (dalam kilometer), kecepatan transfer data, atau delay transmisi (waktu pengiriman). Perhatikan gambar berikut ini :

Proses ini berulang hingga semua label simpul menjadi permanen.


33


Gambar 9. Jaringan Komputer 6

1 2 3 4 5 6

6,4,1 6,4,2 6,3 6,4 6,3,5 -

Hasil pembentukan tabel rute (berdasarkan hasil algoritma Djikstra) ditunjukkan pada gambar 10. Gambar 10. Jaringan Komputer Dengan Tabel Rute Pada Setiap Router.

Lintasan terpendek yang dihasilkan dari algoritma Dijkstra (berdasarkan delai) untuk jaringan komputer pada gambar 9 ditabulasikan dalam tabel 1 berikut. Tabel 1. Lintasan TerpendekJaringan Komputer pada gambar .9. Router Asal

1

2

3

4

5

Router Tujuan 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

Lintasan Terpendek 1,4,2 1,4,6,3 1,4 1,4,2,5 1,4,6 2,4,1 2,4,6,3 2,4 2,5 2,4,6 3,6,4,1 3,6,4,2 3,6,4 3,5 3,6 4,1 4,2 4,6,3 4,2,5 4,6 5,2,4,1 5,2 5,3 5,2,4 5,3,6

5. KESIMPULAN [a]

[b] [c] [d]

[e]

[f]

Jaringan komputer dapat dimodelkan sebagai sebuah graf terhubung dengan setiap simpul menyatakan sebuah komputer. Menentukan lintasan terpendek pada routing jaringan komputer merupakan persoalan optimasi. Pencarian lintasan terpendek menggunakan graf berbobot. Algoritma Dijkstra merupakan algoritma yang paling sering digunakan dalam mencari lintasan terpendek, karena paling efisien (mangkus), tidak membutuhkan waktu yang banyak. Salah satu implementasi dari algoritma Dijkstra ialah penyimpanan simpul dari suatu himpunan ke dalam suatu array atau list berkait. Waktu yang dibutuhkan algoritma Dijkstra untuk bekerja ialah O(V*log V + E).


34


DAFTAR REFERENSI Munir, R. 2005. Buku Teks Ilmu Komputer Matematika Diskrit”, Informatika. Bandung. http://www.informatika org/rinaldi/matdis/2007-2008/makalah (23 Juni 2008) http://www.uty.ac.id/weekend-ti/suparmanmtmk%20diskret/matematika-diskrit-10.doc (23 Juni 2008) http://www,rkaligi.net/php/algoritma djikstramencari jarak terpendek-11.html. (23 Juni 2008) http://id,wikipidia.org/wiki/algoritma-Djikstra. (23 Juni 2008)


35

PENERAPAN ALGOITMA DIJKSTRA DALAM MENCARI LINTASAN TERPENDEK PADA JARINGAN KOMPUTER

Recommend Documents