PENGEMBANGAN SHORTEST PATH ALGORITHM (SPA) DALAM RANGKA PENCARIAN LINTASAN TERPENDEK PADA GRAF BERSAMBUNG BERARAH BERUNTAI

Seminar Nasional Informatika 2012 (semnasIF 2012) UPN ”Veteran” Yogyakarta, 30 Juni 2012

ISSN: 1979-2328

PENGEMBANGAN SHORTEST PATH ALGORITHM (SPA) DALAM RANGKA PENCARIAN LINTASAN TERPENDEK PADA GRAF BERSAMBUNG BERARAH BERUNTAI Oliver Samuel Simanjuntak Jurusan Teknik Informatika UPN “Veteran” Yogyakarta Jl. Babarsari 2 Tambakbayan 55281 Telp (0274) 485323 e-mail : [email protected] Abstrak Secara manual, pencarian jarak dan lintasan terpendek pada graf yang memiliki jumlah verteks, arc dan untai yang sedikit mudah dilakukan. Namun bila graf tersebut memiliki verteks, arc dan untai yang besar, pencarian jarak dan lintasan terpendek akan menjadi sukar. Penelitian berhasil mengembangkan Shortest Path Algorithm (SPA) dalam rangka pencarian jarak dan lintasan terpendek pada graf bersambung berarah beruntai. Aplikasi pengembangan SPA memampukan pencarian jarak dan lintasan terpendek pada graf bersambung berarah secara cepat dan tepat. Pengembangan SPA menjadi solusi dalam membantu memecahkan masalah pencarian lintasan terpendek pada sebuah graf bersambung berarah beruntai. Kata Kunci: SPA, pencarian jarak terpendek, lintasan terpendek, graf bersambung berarah beruntai. 1. PENDAHULUAN Pencarian lintasan terpendek memberi manfaat dalam penghematan waktu, tenaga maupun biaya. Pada kehidupan nyata, distribusi barang atau perjalanan pak pos dari suatu tempat ke tempat lain merupakan contohcontoh pencarian lintasan terpendek. Pencarian lintasan terpendek dapat disajikan dalam bentuk graf bersambung berarah beruntai. Graf bersambung berarah beruntai adalah himpunan tempat/obyek dan rute tersambung yang memiliki arah dan untai. Shortest Path Algorithm (SPA) merupakan metode pencarian lintasan terpendek pada sebuah graf bersambung, berarah dan beruntai. Untuk pencarian lintasan terpendek dari sebuah graf bersambung dan berarah, dapat digunakan perhitungan cara manual atau dengan melalui komputer. Pencarian lintasan terpendek pada graf bersambung berarah yang memiliki jumlah verteks dan arc sedikit melalui cara manual akan mudah. Namun bila graf memiliki verteks dan arc berjumlah besar, pencarian lintasan menjadi sukar. Pencarian lintasan secara mudah dan akurat dapat dilakukan dengan bantuan komputer. Dalam pencarian lintasan terpendek, komputer mengandalkan logika yang kita tuangkan dalam sebuah algoritma pemrograman pencarian lintasannya. Masalah yang diangkat dari penelitian ini adalah pencarian lintasan terpendek pada sebuah graf bersambung berarah beruntai. Untuk itu, akan dibuat sebuah pengembangan metode SPA dalam rangka pencarian lintasan beruntai. Aplikasi pengembangan SPA mampu mencari jarak dan lintasan terpendek pada graf bersambung berarah beruntai. 2. TINJAUAN PUSTAKA 2.1 Graf Graf didefinisikan sebagai graf G=(V,E) yang terdiri dari suatu himpunan objek V=(v1,v2,...vn) yang disebut verteks dan himpunan lain E=(e1,e2,...en) yang elemen-elemennya disebut edge, sedemikian sehingga tiap-tiap edge en diidentifikasikan dengan pasangan verteks tak urut (Even,1979). Menurut Wilson (1990), sebuah edge biasanya akan menghubungkan dua buah verteks yang berlainan, namun akan ada kasus dimana edge menghubungkan 1 verteks yang sama (vi,vi). Lintasan didefinisikan sebagai deret bergantian terhingga dari verteks dan edge. Lintasan dimulai dan diakhiri dengan verteks, sehingga tiap-tiap edge berpengaruh dengan verteks yang mendahului dan mengikutinya. Pada Gambar 2, misalkan V1 a V2 b V3 c V3 d V4 e V2 f V5 adalah lintasan yang ditunjukkan dengan garis tebal. Lintasan tertutup dimana tak ada verteks kecuali verteks awal dan akhir muncul lebih dari sekali disebut untai. Untai ditunjukkan pada Gambar 2, yaitu: V2 b V3 d V4 e V2. Untai juga disebut untai, elementary untai, circular path dan polygon (Gross, 1998). Edge dari sebuah graf mempunyai arti lebih selain sebagai penghubung. Nilai yang dibawa oleh edge dapat mempunyai banyak arti disesuaikan dengan kasus yang direpresentasikan ke graf. Untuk merepresentasikan jarak antara verteks maka pada edge diberi bobot. Suatu graf disebut graf berbobot jika tiap edge yang disebut sebagai bobot dari e, dimana e menghubungkan dua verteks i dan j (Wilson, 1990). Graf berarah (directed graf atau singkatnya digraf) G berisi himpunan verteks-verteks V={v1,v2,...} dan daftar pasangan berurut A={a1,a2,...} dari elemen tersebut yang disebut dengan arc (Wilson, 1990). Jika vi dan vj

D-280


ISSN: 1979-2328

adalah verteks dari V, maka ah(vi,vj) adalah arc h dengan bentuk vivj dikatakan berarah dari vi ke vj atau menggabungkan vi ke vj.

V1

V2

e3

V1

e1

g

a

c

b

e4

e5

e2

V5

V3 d

e7

V3

V4

V4

e6

Gambar 1. Graf dengan 5 Verteks dan 7 Edge

4

e 2

a

V2

e

f

h

V5

Gambar 2. Sebuah Lintasan

d

3 3

2 5

c 2

b Gambar 3. Graf Berbobot dengan 5 Verteks

Gambar 4. Graf Berarah dengan 5 Verteks dan 7 Arc

2.2 Metode Pencarian Lintasan Terpendek Metode pencarian lintasan terpendek dengan Algoritma Lintasan Terpendek (Shortest Path Algorithm), jarak terpendek dan rute lintasan dari verteks awal ke verteks yang dituju yaitu verteks akhir dapat ditemukan dengan algoritma (Wilson, 1990): - Langkah pertama: Beri potensial verteks awal = 0. Labelkan tiap verteks v yang dicapai langsung dari verteks awal dengan jarak dari verteks awal ke v . Pilih label terkecil dan dibuat menjadi potensial dari verteks. - Langkah umum: - Pandang verteks sebagai potensial - Untuk tiap verteks v . Lihat verteks w yang dicapai langsung dari v dan masukkan label w , yaitu: w = (potensial v ) + (jarak dari v ke w ), jika w bukan label yang terkecil. - Jika semua verteks w telah dilabelkan pilih label terkecil didalam network yang bukan merupakan potensial. - Ulangi langkah umum dengan potensial baru. - STOP: Bila verteks akhir telah diberi tanda potensial. Ini merupakan jarak terpendek dari verteks awal ke verteks akhir. - Rute Lintasan Terpendek: Mulai menghitung terbalik dari verteks akhir ke verteks awal (dicapai secara backward/mundur) dan verteks vw dimasukkan bila: (potensial w ) – (potensial v ) = (jarak dari v ke w ) 3. PERANCANGAN SISTEM Sebuah graf bersambung berarah beruntai minimal harus memiliki dua buah verteks dan sebuah arc yang menghubungkannya. Sebuah verteks memiliki data-data seperti koordinat x dan koordinat y serta nama yang perlu disimpan. Penyimpanan verteks pada sistem dapat menggunakan penyimpanan larik (array). Penyimpanan arc hampir sama dengan verteks, sama-sama menggunakan larik (array). Data-data arc yang perlu disimpan adalah verteks awal, verteks akhir, bobot dan nama arc yang disimpan. Pencarian lintasan terpendek pada sebuah graf memerlukan data-data. Lintasan terpendek pada graf memiliki data-data seperti besar potensial, besar label, keterangan dan nama verteks. Penyimpanan data-data lintasan terpendek pada sistem menggunakan larik (array). D-281


ISSN: 1979-2328

3.1 Algoritma Pemrograman Langkah pertama yang harus dilakukan adalah memberikan potensial verteks awal = 0. Masing-masing verteks yang terhubung verteks awal graf diberikan label. Pilih label terkecil dan jadikan potensial berikutnya. Langkah umum yang harus dilakukan adalah memberikan label pada verteks yang terhubung dengan verteks potensial. Langkah umum dilakukan selama verteks akhir graf bukan verteks potensial. Verteks potensial merupakan verteks terpilih dengan nilai label terkecil. Gambar 5 merupakan gambar diagram alir algoritma pencarian lintasan terpendek menggunakan metode SPA.

Gambar 5.Diagram Alir Pencarian Lintasan Terpendek

D-282


ISSN: 1979-2328

3.2 Perancangan Antarmuka Secara umum, kebutuhan terhadap antarmuka yang akan dibuat sebaiknya harus bersifat user friendly (ramah terhadap pengguna / mudah pengoperasiannya) dan interaktif artinya user sebagai pengguna terakhir dapat menggunakan sistem yang dibuat semudah mungkin sehingga user mengoperasikannya dengan mudah. Dengan mempertimbangkan berbagai aspek, maka dibuatlah perancangan antarmuka tampak seperti pada Gambar 6.

Menu Tambah dan Hapus Verteks Bidang Gambar Graf Tambah dan Hapus Arc Matriks berbobot Pilih verteks awal dan akhir graf

Hasil Pencarian Gambar 6. Perancangan Antarmuka

Keterangan gambar : - Menu - Berkas, yang terdiri dari: buka, baru, simpan dan keluar Proses Pengembangan Pencarian Lintasan Terpendek. Tambah dan Hapus Verteks. Terdiri dari sejumlah komponen untuk menambah dan menghapus verteks. Tambah dan Hapus Arc. Terdiri dari sejumlah komponen untuk menambah dan menghapus arc. Pilih Verteks Awal dan Akhir Graf. Terdiri dari sejumlah komponen untuk memilih verteks awal dan verteks akhir lintasan pada graf. Bidang Gambar Graf. Daerah ini digunakan untuk membuat gambar graf secara visual dan manual serta menampilkan gambar graf yang sudah disimpan Hasil Pencarian. Menampilkan jarak dan lintasan terpendek. 4. IMPLEMENTASI DAN ANALISIS SISTEM 4.1 Implementasi Sistem Bila aplikasi dijalankan, maka akan terlihat tampilan awal sistem seperti yang terlihat pada Gambar 7.

Gambar 7. Tampilan Awal Program

D-283


ISSN: 1979-2328

Proses selanjutnya adalah penginputan graf. Untuk menginput graf maka harus ditentukan terlebih dulu verteks dan arc. Aplikasi menyimpan data verteks dan arc. Tampilannya dapat dilihat pada Gambar 8.

Gambar 8. Input Graf Proses setelah input graf adalah pencarian lintasan terpendek. Berdasar penentuan verteks awal dan akhir, aplikasi mencari lintasan terpendek dari verteks awal ke akhir. Tampilan pencarian lintasan terpendek pada graf dengan 19 verteks dan 241 arc dapat dilihat pada Modul Pencarian Lintasan Terpendek. Hasil pencarian lintasan terpendek pada graf dengan 19 verteks dan 241 arc dapat dilihat pada Gambar 9.

D-284


ISSN: 1979-2328

Gambar 9. Pencarian Lintasan Terpendek for o:=1 to jmlarc do begin for p:=1 to jmlgraf2 do besarlabel:=(0+strtoint(arrarc[o].besar)); begin if (besarpotensial)>=(besarlabel) then if (q=(arrarc[o].vakhir)) and besarpotensial:=besarlabel; (((arrarc[o].vawal)=(arrgraf2[p].verteks2))) then end; begin end if ((arrgraf2[p].besarpotensial2)<>'') then end; begin else if ((arrgraf2[p].besarpotensial2)='0') then begin begin besarlabel:=strtoint(arrgraf2[p].besarpotensial if (arrgraf2[p].verteks2<>combobox5.Text) then 2)+strtoint(arrarc[o].besar); begin if (besarpotensial)>=(besarlabel) then besarlabel:=99999999; besarpotensial:=besarlabel; if ((besarpotensial)>=(besarlabel)) then end; besarpotensial:=besarlabel; end; end else if (arrgraf2[p].verteks2=combobox5.Text) then Modul. Pencarian Lintasan Terpendek 4.2 Analisis Sistem Pencarian lintasan terpendek menggunakan pengembangan metode SPA. Proses ini akan menampilkan sajian matiks berbobot dan menampilkan hasil pencarian berupa lintasan terpendek pada graf. Gambar 10 merupakan gambar tampilan proses pencarian lintasan terpendek menggunakan pengembangan metode SPA.

Gambar 10. Pencarian Lintasan Terpendek

D-285


ISSN: 1979-2328

Gambar 11. Graf Bersambung Berarah Tanpa Untai Dari Gambar 11, metode pencarian lintasan terpendek dari verteks V1 ke verteks V5 dengan beberapa iterasi dapat ditabulasikan sama seperti pada pencarian lintasan terpendek menggunakan pengembangan metode SPA. Metode SPA dikembangkan untuk memecahkan permasalahan metode SPA dalam pencarian lintasan terpendek pada graf bersambung berarah beruntai. Metode pencarian lintasan terpendek dari verteks V1 ke verteks V5 dengan beberapa iterasi dapat ditabulasikan sebagai berikut: - Iterasi 0 Tabel 1. Pencarian lintasan terpendek menggunakan metode SPA (iterasi 0) Verteks Besar Potensial Besar Label Keterangan V1 0 0 V2 3 1 V3 5 1 V4 1 V5 1 Beri nilai besar potensial V1 = 0. Beri nilai 1 pada semua keterangan verteks. Labelkan dengan nilai yang terkecil tiap verteks v bukan potensial yang dicapai dari verteks dengan besar potensial dan keterangan = 1 (verteks V1) yaitu verteks V2 dan verteks V3 dengan jarak dari verteks V1. Keterangan verteks V1 = 0. Pilih verteks berlabel terkecil dari semua label yang ada (verteks V2), jadikan besar labelnya sebagai nilai besar potensial. - Iterasi 1 Tabel 2. Pencarian lintasan terpendek menggunakan metode SPA (iterasi 1) Verteks Besar Potensial Besar Label Keterangan V1 0 0 V2 3 0 V3 5 1 V4 4 1 V5 8 1 Labelkan dengan nilai yang terkecil tiap verteks v bukan potensial yang dicapai dari verteks dengan besar potensial dan keterangan = 1 (verteks V2) yaitu verteks V4 dan verteks V5 dengan jarak dari verteks V2, lalu keterangan verteks V2 = 0. Pilih label terkecil dari semua label yang ada (verteks V4), jadikan besar labelnya sebagai nilai besar potensial. - Iterasi 2 Tabel 3. Pencarian lintasan terpendek menggunakan metode SPA (iterasi 2) Verteks Besar Potensial Besar Label Keterangan V1 0 0 V2 3 0 V3 5 1 V4 4 0 V5 8 1 Labelkan dengan nilai yang terkecil tiap verteks v bukan potensial yang dicapai dari verteks dengan besar potensial dan keterangan = 1 (verteks V4) yaitu verteks V5, lalu keterangan verteks V4 = 0. Pilih label terkecil dari semua label yang ada (verteks V3), jadikan besar labelnya sebagai nilai besar potensial. D-286


-

ISSN: 1979-2328

Iterasi 3 Tabel 4. Pencarian lintasan terpendek menggunakan metode SPA (iterasi 3) Verteks Besar Potensial Besar Label Keterangan V1 0 0 V2 3 0 V3 5 0 V4 4 0 V5 8 1

Labelkan dengan nilai yang terkecil tiap verteks v bukan potensial yang dicapai dari verteks dengan besar potensial dan keterangan = 1 (verteks V3) yaitu verteks V5, lalu keterangan verteks potensial=0. Pilih label terkecil dari semua label yang ada (verteks V5), jadikan besar labelnya sebagai nilai besar potensial. Iterasi dihentikan, verteks V5 telah diberi tanda potensial. Jarak terpendek dari verteks V1 ke verteks V5 = 8. Lintasan terpendek dicapai secara mundur (backward). - Besar potensial V5 – besar potensial V2 = jarak dari V2 ke V5 (8 - 3 = 5). Benar Lintasan terpendek: -V2-V5 - Besar potensial V2 – besar potensial V1 = jarak dari V1 ke V2 (3 - 0 = 3). Benar Lintasan terpendek: V1-V2-V5 Pencarian lintasan dihentikan, lintasan terpendek dari verteks V1 ke verteks V5 adalah V1-V2-V5 5. KESIMPULAN DAN SARAN Bedasar hasil analisis penelitian dan pengujian pada aplikasi ini dapat disimpulkan beberapa hal sebagai berikut: - Pengembangan SPA berhasil mencari jalur terpendek pada graf bersambung berarah beruntai. - Aplikasi komputer pada pengembangan SPA berhasil mencari jalur terpendek secara cepat dan tepat berbanding pencarian secara manual. Pada penelitian ini masih banyak terdapat kekurangan yang perlu diteliti lebih lanjut sebagai bahan untuk pengembangan sistem. Beberapa saran yang dapat diberikan guna pengembangan penelitian selanjutnya: - Penambahan arc dikembangkan dengan cara visual. - Penambahan jumlah maksimum penginputan verteks yang diijinkan. - Penambahan besar bobot arc yang diijinkan. DAFTAR PUSTAKA Buckley, Fred. 2002. A Friendly Introduction To Graph Theory. New Jersey: Pearson Education, Inc. Even, Shimon. 1979. Graph Algorithms. United State of America : Computer Science Press. Gross, Jonathan. 1998. Graph Theory and Its Applications. Florida: CRC Press. Wilson, Robin J. 1990. Graphs: An Introductory Approach. Canada : John Wiley & Sons.

D-287

PENGEMBANGAN SHORTEST PATH ALGORITHM (SPA) DALAM RANGKA PENCARIAN LINTASAN TERPENDEK PADA GRAF BERSAMBUNG BERARAH BERUNTAI

Recommend Documents