Implementasi Algoritma Pencarian k Jalur Sederhana Terpendek dalam Graf

JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print)

1

Implementasi Algoritma Pencarian k Jalur Sederhana Terpendek dalam Graf Anggakara Hendra N., Yudhi Purwananto, dan Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia e-mail: [email protected]

Abstrak—Dalam dunia nyata, terdapat permasalahan mencari jalur terpendek yang dapat direpresentasikan dalam graf, tetapi jalur yang didapat kadang tidak bisa digunakan karena adanya suatu halangan pada jalur tersebut. Hal ini menyebabkan dibutuhkannya alternatif berupa jalur-jalur terpendek lain dengan biaya yang dikeluarkan tidak memiliki selisih yang terlalu besar dari jalur terpendek pertama. Beberapa algoritma naif telah ditemukan untuk menyelesaikan permasalahan pencarian k jalur sederhana terpendek dalam graf. Tetapi algoritma naif yang ada masih kurang efisien dalam hal kecepatan dan kebutuhan memori. Dalam artikel ini dilakukan studi dan implementasi algoritma pencarian 𝐤 jalur sederhana terpendek dalam graf dengan bahasa C++. Hasil uji coba menunjukkan program menghasilkan jalur yang benar dan memiliki pertumbuhan waktu eksekusi secara kuadratik dengan kompleksitas waktu 𝐎(𝐤𝐧(𝐦 + 𝐧 𝐥𝐨𝐠 𝐧)) pada n buah verteks, m buah edge, dan urutan k jalur yang dicari. Kata Kunci—Algoritma deviasi, algoritma Dijkstra, jalur sederhana, jalur terpendek.

I. PENDAHULUAN

D

alam permasalahan pencarian jalur terpendek dalam graf, jalur terpendek yang didapat tidak selalu dapat digunakan karena adanya suatu halangan pada jalur tersebut. Hal ini menyebabkan dibutuhkannya pemilihan alternatif jalur lain berupa jalur terpendek berikutnya. Tentu saja, biaya yang dibutuhkan oleh jalur tersebut harus memiliki selisih minimum dengan biaya jalur terpendek sebelumnya. Salah satu algoritma naif yang dapat digunakan untuk mencari sebanyak k buah jalur sederhana adalah dengan melakukan modifikasi pada algoritma Dijkstra [1]. Modifikasi dilakukan dengan menjalankan algoritma Dijkstra secara berulang sampai didapatkan k pasang jalur berbeda yang ditemukan dari verteks sumber menuju verteks tujuan. Tetapi, algoritma naif tersebut masih kurang efisien dalam hal kecepatan dan kebutuhan memori yang dibuktikan pada hasil uji coba. Pada artikel ini dilakukan implementasi algoritma pencarian k jalur sederhana terpendek dalam graf [2] yang lebih efisien daripada algoritma naif yang telah ada. Implementasi dilakukan pada graf berarah dan berbobot dengan batasan bobot masing-masing edge berupa bilangan bulat nonnegatif. Jalur yang dihasilkan pada artikel ini adalah jalur sederhana, yaitu jalur yang tidak mengandung pengulangan verteks

penyusun. Artikel ini bertujuan untuk membuktikan kebenaran hasil implementasi algoritma pencarian k jalur sederhana terpendek dalam graf, serta membandingkan kecepatan algoritma tersebut dengan algoritma naif. II. METODOLOGI A. Definisi Ditentukan sebuah graf 𝐺 = (𝑉, 𝐸) dengan 𝑉 = {𝑣1 , 𝑣2 , … , 𝑣𝑛 } adalah himpunan verteks dan 𝐸 = {𝑒1 , 𝑒2 , … 𝑒𝑚 } adalah himpunan edge yang menyusun graf 𝐺. Masing-masing edge dalam 𝐸 memiliki bobot yang dinotasikan sebagai 𝑐(𝑒). Sebuah edge yang terhubung dari verteks 𝑣𝑖 ke verteks 𝑣𝑗 untuk 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑛, dan 𝑣𝑖 ≠ 𝑣𝑗 , dapat dinotasikan sebagai �𝑣𝑖 , 𝑣𝑗 �. Jika diketahui 𝑖 dan 𝑗 adalah verteks dalam 𝑉, maka sebuah jalur 𝑝 dari verteks 𝑖 menuju verteks 𝑗 dalam graf 𝐺 adalah urutan verteks dengan bentuk 𝑝 = {𝑣 ′1 , 𝑣 ′ 2 , … , 𝑣′𝑙 } dengan ketentuan sebagai berikut: • 𝑣 ′ 𝑘 ∈ 𝑉, untuk setiap 𝑘 ∈ {1 … 𝑙}; • (𝑣 ′ 𝑘 , 𝑣 ′ 𝑘+1 ) ∈ 𝐸 untuk setiap 𝑘 ∈ {1 … 𝑙 − 1}; • 𝑖 = 𝑣′1 dan 𝑗 = 𝑣′𝑙 . Jika 𝑃𝑖𝑗 merupakan himpunan jalur-jalur dari verteks 𝑖 menuju verteks 𝑗 dalam graf 𝐺, kemudian verteks 𝑥 dan verteks 𝑦 adalah verteks penyusun jalur 𝑝 ∈ 𝑃𝑖𝑗 , maka 𝑞 ∈ 𝑃𝑥𝑦 disebut sebagai subjalur dari 𝑝 apabila memiliki rangkaian verteks yang sama dengan 𝑝 dari 𝑥 sampai 𝑦. Jalur tersebut dinotasikan sebagai 𝑠𝑢𝑏𝑝 (𝑥, 𝑦). Penggabungan dua jalur, 𝑝 ∈ 𝑃𝑖𝑗 dan 𝑞 ∈ 𝑃𝑗𝑙 , dinotasikan sebagai 𝑝 ⋄ 𝑞 dan merupakan jalur dari verteks 𝑖 menuju verteks 𝑙 yang terbentuk dari jalur 𝑝 yang diikuti dengan jalur 𝑞. Jika diketahui sebuah bilangan bulat positif 𝐾, maka permasalahan 𝐾 jalur sederhana terpendek bertujuan menentukan sebuah himpunan jalur 𝑃𝐾 = {𝑝1 , … , 𝑝𝐾 } ⊆ 𝑃, dengan ketentuan sebagai berikut: • 𝑝𝑘 adalah jalur sederhana, untuk setiap 𝑘 ∈ {1 … 𝐾}; • 𝑤(𝑝𝑘 ) ≤ 𝑤(𝑝𝑘+1 ), untuk setiap 𝑘 ∈ {1 … 𝐾 − 1}; • 𝑤(𝑝𝐾 ) ≤ 𝑤(𝑝), untuk setiap jalur sederhana 𝑝 ∈ 𝑃 ∖ 𝑃𝐾 ; • 𝑝𝑘 ditentukan sebelum 𝑝𝑘+1, pada setiap 𝑘 ∈ {1 … 𝐾 − 1} B. Algoritma Deviasi Algoritma pencarian k jalur terpendek antara dua verteks mengacu pada pembuatan "pseudo"-tree yang

JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print) merepresentasikan hubungan antara jalur-jalur dalam 𝑃𝑘 sebagai sebuah struktur pohon (tree) [3]. Jika terdapat sebuah jalur 𝑞1 dari verteks 𝑠 menuju verteks 𝑡 dalam graf 𝐺, maka 𝑞1 membentuk sebuah pohon yang terdiri dari satu buah jalur. Jika ada jalur lain 𝑞𝑘+1 dari verteks s menuju verteks t dalam graf 𝐺, maka dapat dipastikan bahwa 𝑞𝐾+1 memiliki rangkaian verteks yang sama dengan 𝑞1 , … , 𝑞𝑘 dari verteks sumber 𝑠, sampai verteks tertentu (yang dapat berarti 𝑠), yaitu letak jalur 𝑞𝑘+1 menyimpang dari himpunan jalur tersebut [2]. Pada verteks-verteks tersebut, verteks terjauh dari verteks sumber disebut dengan verteks deviasi pada 𝑞𝑘+1 dan dinotasikan sebagai 𝑑(𝑞𝑘+1 ). Verteks deviasi pada jalur 𝑞𝑘+1 merupakan posisi jalur 𝑞𝑘+1 menyimpang dari jalur-jalur sebelumnya, yaitu 𝑞1 , … , 𝑞𝑘 . Kemudian, jika berdasar pada asumsi bahwa himpunan jalur 𝑞1 , … , 𝑞𝑘 membentuk "pseudo"-tree, maka himpunan jalur 𝑞1 , … , 𝑞𝑘 , 𝑞𝑘+1 juga membentuk "pseudo"-tree dengan 𝑘+1 jalur [4]. Sebuah "pseudo"-tree yang terdiri dari jalur-jalur sederhana disebut sebagai pohon jalur sederhana. Pada algoritma deviasi digunakan sebuah himpunan jalur 𝑋 yang berisi kandidat-kandidat jalur sederhana. Pada tiap langkah, algoritma deviasi memilih jalur dalam 𝑋 dengan bobot terkecil, membuat jalur sederhana baru dari jalur tersebut, lalu terakhir memperbarui 𝑋. Ketika algoritma dijalankan, jalur-jalur dalam 𝑋 merepresentasikan beberapa jalur dalam struktur pohon yang sedang dibuat. Prosedurprosedur tersebut diulang hingga 𝑝𝑘 ditemukan, yaitu ketika jalur-jalur yang diambil dari 𝑋 adalah 𝑝1 , 𝑝2 , … , 𝑝𝑘 . Pada setiap 𝑘 ∈ {1, … , 𝐾}, ketika 𝑝𝑘 ditentukan, kandidat-kandidat untuk jalur 𝑝𝑗 dengan 𝑗 > 𝑘 telah dihitung, dan untuk menghindari jalur-jalur dihitung kembali, maka rangkaian verteks yang dianalisa hanya yang terdapat pada 𝑠𝑢𝑏𝑝𝑘 (𝑑(𝑝𝑘 ), 𝑡). Selain itu, ketika menganalisa 𝑑(𝑝𝑘 ), edgeedge yang berasal dari 𝑑(𝑝𝑘 ) dan termasuk dalam jalur-jalur sederhana lain yang sudah ditetapkan tidak boleh digunakan. C. Algoritma Yen [5] Algoritma Yen adalah algoritma deviasi yang dapat digunakan hanya untuk menentukan jalur sederhana. Pada tiap verteks 𝑣𝑖𝑘 , algoritma tersebut menghitung jalur sederhana terpendek 𝑝 yang menyimpang dari 𝑝𝑘 . Kemudian, 𝑝𝑘 disebut sebagai parent dari 𝑝 dan 𝑣𝑖𝑘 disebut sebagai verteks deviasi pada 𝑝𝑘 . Dengan tujuan hanya untuk mencari jalur sederhana, 𝑘 maka verteks-verteks pada 𝑠𝑢𝑏𝑝𝑘 (𝑠, 𝑣𝑖−1 ) tidak boleh diulang. Oleh karena itu, verteks-verteks tersebut dihapus sementara dari graf 𝐺, kemudian mencari jalur sederhana terpendek dari verteks 𝑣𝑖𝑘 menuju verteks 𝑡 pada graf yang sudah dimodifikasi. Pada implementasi algoritma Yen, setiap verteks pada 𝑝𝑘 dari 𝑑(𝑝𝑘 ) sampai 𝑣𝑙𝑘𝑘 −1. Pada masing-masing verteks, misal 𝑣𝑖𝑘 , jalur sederhana terpendek 𝑝 ∈ 𝑃 yang akan dihitung akan memiliki bentuk 𝑝 = 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑖𝑘 � ⋄ 𝑞, dengan 𝑞 merupakan 𝑘 ) dan jalur dalam 𝑃𝑣𝑘 𝑡 yang edge pertamanya bukan (𝑣𝑖𝑘 , 𝑣𝑖+1 𝑖

belum dihitung sebelumnya. Untuk mendapatkan jalur 𝑝 dengan kondisi tersebut, maka graf yang digunakan harus

2

dimodifikasi terlebih dahulu, yaitu dengan menghapus semua 𝑘 𝑘 verteks dalam 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑖−1 �, edge (𝑣𝑖𝑘 , 𝑣𝑖+1 ), serta semua 𝑘 edge yang berasal dari 𝑣𝑖 yang sebelumnya telah dihapus saat menghitung 𝑝𝑘 . Kemudian, jalur 𝑞 dapat diperoleh dengan mencari jalur terpendek dari 𝑣𝑖𝑘 menuju verteks 𝑡 pada graf yang telah dimodifikasi. Setelah jalur 𝑝 didapat, graf dikembalikan seperti keadaan semula. D. Rangkaian Proses

Jika diketahui 𝑣𝑙𝑘𝑘 −1 adalah verteks pertama yang akan dianalisa pada 𝑝𝑘 , maka 𝑝 adalah jalur sederhana yang memiliki bentuk 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑙𝑘𝑘 −1 � ⋄ 𝑞, dengan 𝑞 adalah jalur sederhana terpendek dari 𝑣𝑙𝑘𝑘 −1 menuju 𝑡 tanpa verteks-verteks dalam 𝑠𝑢𝑏𝑝𝑘 (𝑠, 𝑣𝑙𝑘𝑘 −2 ) dan tanpa edge (𝑣𝑙𝑘𝑘 −1 , 𝑡). Dengan kata lain, verteks-verteks dan edge tersebut dihapus dari graf 𝐺 sebelum jalur 𝑞 ditentukan. Kemudian, dengan menggunakan algoritma pencarian jalur terpendek, akan terbentuk sebuah struktur pohon jalur sederhana terpendek dari 𝑖 ke 𝑡, untuk setiap 𝑖 ∈ 𝑉, yang disebut pohon terpendek berakar pada 𝑡, dapat dihitung dan digunakan untuk menentukan jalur sederhana 𝑞. Struktur pohon terpendek berakar pada 𝑥 ∈ 𝑉 dinotasikan sebagai 𝑇𝑥 dan jalur sederhana dari 𝑖 ∈ 𝑉 menuju 𝑥 dinotasikan sebagai 𝑇𝑥 (𝑖). Bobot jalur 𝑇𝑖 (𝑖) dinotasikan sebagai 𝜋𝑖 dan disebut sebagai label dari 𝑖, untuk setiap 𝑖 ∈ 𝑉. Terdapat sebuah verteks sembarang 𝑣𝑖𝑘 di dalam 𝑝𝑘 dengan 𝑘 𝑘 𝑣𝑖𝑘 ≠ 𝑑(𝑝𝑘 ), dan sebuah jalur 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑖+1 � ⋄ 𝑇𝑡 (𝑣𝑖+1 ) yang akan dicari, dengan 𝑇𝑡 menggunakan acuan graf yang didapat setelah menghapus verteks-verteks pada jalur 𝑠𝑢𝑏𝑝𝑘 (𝑠, 𝑣𝑖 ) dan 𝑘 𝑘 , 𝑣𝑖+2 ) dari graf 𝐺. menghapus edge (𝑣𝑖+1 Langkah selanjutnya adalah mengembalikan edge 𝑘 𝑘 �𝑣𝑖+1 , 𝑣𝑖+2 � ke dalam graf. Proses pengembalian edge tersebut termasuk memperbaiki 𝑇𝑡 yang berarti memperbaiki label dari beberapa node pada struktur pohon tersebut. Kemudian, 𝑘 𝑘 setelah mengembalikan �𝑣𝑖+1 , 𝑣𝑖+2 �, semua verteks 𝑥 pada graf yang telah dimodifikasi tersebut dianalisa sehingga 𝑘 setidaknya ada satu jalur sederhana dari verteks 𝑥 menuju 𝑣𝑖+1 dalam graf tersebut. Pada langkah selanjutnya dilakukan pengembalian verteks 𝑣𝑖𝑘 dalam graf yang telah dimodifikasi, jika terdapat edge-edge yang berasal dari verteks tersebut, maka dilakukan penghitungan label dari 𝑣𝑖𝑘 . Perubahan label 𝑣𝑖𝑘 termasuk melakukan pengubahan label-label lain yang berhubungan dengan label tersebut, kemudian dilakukan analisa verteks 𝑥 dalam graf sehingga setidaknya ada satu jalur sederhana dari 𝑥 menuju 𝑣𝑖𝑘 . Jika setelah dua langkah tersebut nilai 𝜋𝑣𝑘 dapat 𝑖

ditentukan, maka 𝑇𝑡 (𝑣𝑖𝑘 ) telah ditetapkan dan jalur sederhana baru yang didapat memiliki bentuk 𝑝𝑘 = 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑖𝑘 � ⋄ 𝑇𝑡 (𝑣𝑖𝑘 ). Namun jika sebaliknya, maka tidak mungkin ada jalur sederhana yang dapat dibuat. Beberapa hal yang perlu diperhatikan adalah ketika 𝑣𝑖𝑘 = 𝑑(𝑝𝑘 ), prosedur yang sama dilakukan, tetapi ketika 𝑘 melewati edge (𝑑(𝑝𝑘 ), 𝑣𝑖+1 ), semua edge yang dihapus ketika


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

𝑝 ← jalur sederhana terpendek dari 𝑠 ke 𝑡 dalam 𝐺 𝑑(𝑝) ← 𝑠; 𝑋 ← {𝑝}; 𝑘 ← 0; while (𝑋 ≠ ∅ and 𝑘 ≤ 𝐾) do 𝑘 ← 𝑘 + 1; 𝑝𝑘 ← jalur sederhana terpendek dalam 𝑋; 𝑋 ← 𝑋 − {𝑝𝑘 }; hapus 𝑠𝑢𝑏𝑝𝑘 (𝑠, 𝑣𝑙𝑘𝑘−1 ) dalam graf; hapus edge-edge (𝑑(𝑝𝑘 ), 𝑖), untuk 𝑖 ∈ 𝑉 pada 𝑝1 , … , 𝑝𝑘−1 dalam graf; 𝑇𝑡 ← pohon jalur terpendek dengan akar 𝑡; for �𝑣𝑖𝑘 ∈ �𝑣𝑙𝑘𝑘−1 , … , 𝑑(𝑝𝑘 )�� do

3

1 𝑙𝑖𝑠𝑡 ← {𝑥}; 2 repeat 3 𝑖 ← elemen dari 𝑙𝑖𝑠𝑡; 𝑙𝑖𝑠𝑡 ← 𝑙𝑖𝑠𝑡 − {𝑖}; 4 for ((𝑗, 𝑖) ∈ 𝐸) do if (𝜋𝑗 > 𝜋𝑖 + 𝑐(𝑗, 𝑖)) then 5 𝜋𝑗 ← 𝜋𝑖 + 𝑐(𝑗, 𝑖); 6 7 if (𝑗 ∉ 𝑙𝑖𝑠𝑡) then 𝑙𝑖𝑠𝑡 ← 𝑙𝑖𝑠𝑡 ∪ {𝑗}; 8 endif 9 endfor 10 until (𝑙𝑖𝑠𝑡 = ∅); Gambar. 3. Pseudocode algoritma reverse star form

kembalikan node 𝑣𝑖𝑘 pada graf; hitung 𝜋𝑣 𝑘 dengan forward star form; 𝑖

if (𝜋𝑣 𝑘 ditetapkan) then 𝑖

perbaiki label semua verteks penerus dari 𝑣𝑖𝑘 dengan reverse star form; 𝑝 ← 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑖𝑘 � ⋄ 𝑇𝑡 �𝑣𝑖𝑘 �; 𝑑(𝑝) ← 𝑣𝑖𝑘 ; 𝑋 ∪ {𝑝}; Endif 𝑘 kembalikan (𝑣𝑖𝑘 , 𝑣𝑖+1 ) pada graf; 𝑘 if (𝜋𝑣𝑘𝑖 > 𝜋𝑣 𝑘 + 𝑐(𝑣𝑖𝑘 , 𝑣𝑖+1 )) then 𝜋𝑣𝑘𝑖

𝑖+1

← 𝜋𝑣 𝑘 + 𝑖+1

Gambar. 4. Representasi graf dari data masukan pada uji coba kebenaran

𝑘 𝑐(𝑣𝑖𝑘 , 𝑣𝑖+1 );

Perbaiki label semua verteks penerus 20 dari 𝑣𝑖𝑘 dengan reverse star form; endif 21 endfor 22 kembalikan verteks dan edge dalam jalur 𝑝𝑘 23 dari 𝑠 sampai 𝑑(𝑝𝑘 ) dalam graf; kembalikan edge-edge (𝑑(𝑝𝑘 ), 𝑖), untuk 𝑖 ∈ 𝑉 24 pada 𝑝1 , … , 𝑝𝑘−1 dalam graf; endwhile 25 Gambar. 1. Pseudocode algoritma pencarian jalur sederhana terpendek dalam graf 1 for ((𝑖, 𝑗) ∈ 𝐸) do if (𝜋𝑖 > 𝜋𝑗 + 𝑐(𝑖, 𝑗)) then 2 𝜋𝑖 ← 𝜋𝑗 + 𝑐(𝑖, 𝑗); 3 4 endif 5 endfor Gambar. 2. Pseudocode algoritma forward star form

𝑝𝑘 dibuat, juga harus dihapus dari graf. Pada Gambar 1 ditunjukkan pseudocode algoritma untuk mendapatkan jalur sederhana terpendek ke-𝑘 sesuai langkah-langkah pada subbab ini. Proses memperbaiki label 𝜋𝑖 menggunakan algoritma yang disebut forward star form, dan proses memperbaiki label verteks-verteks penerus 𝑣𝑖𝑘 menggunakan algoritma yang disebut reverse star form. Pseudocode algoritma forward star form ditunjukkan pada Gambar 2, dan pseudocode algoritma reverse star form ditunjukkan pada Gambar 3. Pada implementasi algoritma dalam artikel ini, implementasi proses algoritma forward star form dilakukan dengan cara memberi label pada verteks-verteks yang terdapat pada 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑖𝑘 � ketika melakukan penghapusan subjalur sebelum melakukan proses reverse star form. Kemudian, karena proses algoritma reserver star form hanya dilakukan pada verteksverteks yang merupakan penerus (successor) dari verteks 𝑣𝑖𝑘 , maka implementasi algoritma tersebut dapat dilakukan dengan cara melakukan algoritma Dijkstra pada graf yang telah

No. 1 2 3 4

Tabel 1. Data jumlah verteks dan edge pada graf acak Judul Graf Jumlah Verteks Jumlah Edge Graf A Graf B Graf C Graf D

51 50 730 6.551

1.183 2.450 5.762 47.322

dimodifikasi, dengan menambah batasan berupa verteksverteks pada 𝑠𝑢𝑏𝑝𝑘 �𝑠, 𝑣𝑖𝑘 �. III. UJI COBA A. Data Uji Coba Data uji coba yang digunakan pada uji coba ini terdiri dari tiga macam data uji coba. Tiga data uji coba tersebut adalah data graf yang dibuat secara manual, data masukan pada situs Sphere Online Judge (SPOJ), dan data graf acak dengan jumlah verteks dan edge yang beragam. Pada Tabel 1 ditunjukkan data jumlah verteks dan edge dari graf-graf acak yang digunakan untuk uji coba. Sedangkan untuk data masukan pada situs SPOJ menggunakan data uji coba yang tersedia pada server situs SPOJ. B. Uji Coba Kebenaran Uji coba dilakukan dengan memberi masukan ke program dengan data masukan yang dapat direpresentasikan menjadi graf sesuai pada Gambar 4. Pada graf di Gambar 4, jalur keempat yang ditemukan oleh program dari verteks 1 menuju verteks 5 adalah jalur dengan rangkaian verteks {1,3,4,5}. Setelah dianalisa secara manual, dari graf tersebut terdapat empat jalur yang berbeda dari verteks 1 menuju verteks 5, yaitu dengan urtan 𝑝1 = {1,3,5}, 𝑝2 = {1,2,4,5}, 𝑝3 = {1,2,5}, dan 𝑝4 = {1,3,4,5}. Karena hasil keluaran program sama dengan verteks-verteks penyusun 𝑝4 dari graf pada Gambar 4, maka terbukti bahwa hasil implementasi program dalam artikel ini adalah benar.


4

Gambar. 5. Hasil pengujian pada situs SPOJ

Gambar. 7. Grafik hasil uji coba kecepatan pada graf acak

Gambar. 6. Grafik hasil uji kecepatan pada situs SPOJ No. Tabel 2. Hasil uji coba pada graf acak No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

𝑘 100

500

1000

5000

Judul Graf A B C D A B C D A B C D A B C D

Waktu (detik) 0,024 0,035 0,588 94,856 0,115 0,161 3,030 448,342 0,227 0,328 6,165 888,671 1,114 1,562 32,113 4486,230

C. Uji Coba pada Situs Penilaian Daring SPOJ Pada uji coba ini, digunakan bantuan sebuah situs penilaian daring bernama Sphere Online Judge (SPOJ). Uji coba dilakukan dengan menggugah kode sumber hasil implementasi artikel ini pada salah satu soal di SPOJ yang berjudul "Kth Shortest Path" [6]. Pemilihan soal "Kth Shortest Path" dilakukan karena deskripsi soal sesuai dengan permasalahan pada artikel ini, yaitu pencarian k jalur sederhana terpendek pada graf. Pengujian dilakukan beberapa kali untuk mendapat rata-rata waktu eksekusi program pada soal "Kth Shortest Path". Pada Gambar 5 ditunjukkan hasil salah satu pengujian pada situs SPOJ yang juga membuktikan kebenaran hasil implementasi algoritma pada artikel. Data graf-graf yang digunakan pada uji coba ini memiliki batasan jumlah verteks sebanyak 50 buah, jumlah edge sebanyak 2450 buah, dan jumlah jalur maksimal yang dicari sebanyak 200 jalur. Pada Gambar 6 ditunjukkan grafik hasil beberapa kali uji coba pada situs SPOJ. Dari grafik pada Gambar 6, didapatkan rata-rata waktu eksekusi program pada situs SPOJ sebesar 2,76 detik dengan standar deviasi sebesar 0,3 detik.

1 2 3 4 5 6 7 8

Tabel 3. Hasil uji coba pada algoritma naif Waktu Judul Graf 𝑘 (detik) A 0.296 100 B 0.561 A 1.294 500 B 3.104 A 2.62 1000 B 6.24 A 14.461 5000 B 30.576

D. Uji Coba pada Graf Acak Pada uji coba ini dilakukan beberapa kali pengujian dengan data masukan berupa graf dengan jumlah verteks dan edge yang berbeda untuk masing-masing pengujian. Uji coba ini bertujuan mengetahui perbedaan waktu eksekusi program dengan berdasar pada perbedaan jumlah verteks, jumlah edge, dan urutan jalur (𝑘) yang dicari pada graf. Pada Tabel 2 ditunjukkan hasil uji coba yang dilakukan untuk masing-masing graf pada Tabel 1 dengan pengelompokan berdasarkan urutan jalur yang dicari dan graf yang berbeda. Kemudian pada Gambar 7 ditunjukkan grafik ilustrasi hasil uji coba dari Tabel 2 dengan sumbu-x menunjukkan urutan jalur yang dicari dan sumbu-y menunjukkan nilai waktu dalam detik dengan skala nilai logaritma berbasis 10. E. Uji Coba Perbandingan Algoritma Pada uji coba ini dilakukan perbandingan kecepatan eksekusi antara program hasil implementasi artikel ini dan algoritma naif yang lebih dahulu ditemukan, dengan data uji yang digunakan adalah data graf A dan B pada Tabel 1. Algoritma naif yang digunakan sebagai pembanding pada uji coba ini adalah modifikasi dari algoritma Dijkstra untuk mencari jalur sederhana terpendek ke-𝑘. Hasil uji coba pada algoritma naif dapat dilihat pada Tabel 3. Pada Gambar 8 ditunjukkan grafik hasil perbandingan uji coba pada algoritma dalam artikel ini yang mengacu pada Tabel 2 dan hasil uji coba pada algoritma modifikasi dari algoritma Dijkstra yang ditunjukkan pada Tabel 3. Pada grafik di Gambar 8, sumbu-x menunjukkan urutan jalur yang dicari


Gambar. 8. Grafik perbandingan algoritma

dan sumbu-y menunjukkan nilai waktu dalam detik dengan skala nilai logaritma berbasis 10, dengan "TA" merupakan hasil algoritma dalam artikel ini dan "Naif" merupakan hasil algoritma modifikasi dari algoritma Dijkstra. IV. KESIMPULAN Berdasarkan hasil uji coba yang telah dilakukan, terdapat tiga kesimpulan yang bisa diambil, yaitu: 1. Pada hasil uji coba kebenaran dan hasil uji coba pada situs SPOJ, ditunjukkan bahwa jalur yang dihasilkan program sesuai dengan jalur yang diminta pada permasalahan. Hal tersebut membuktikan bahwa hasil implementasi algoritma pencarian 𝑘 jalur sederhana terpendek pada artikel ini dapat menghasilkan keluaran yang benar. 2. Pertumbuhan waktu eksekusi program bersifat kuadratik dengan kompleksitas Ο(𝑘𝑛(𝑚 + 𝑛 log 𝑛) pada 𝑛 buah verteks, 𝑚 buah edge, dan 𝑘 jalur yang dicari. 3. Algoritma pada artikel ini lebih efisien daripada algoritma naif yang telah ditemukan sebelumnya Pada artikel ini ini, struktur heap yang digunakan untuk menyimpan kandidat jalur merupakan struktur heap pada pustaka standar C++, yaitu menggunakan struktur heap biner. Kemudian untuk pengembangan, dapat dilakukan studi mengenai struktur heap Fibonacci beserta implementasinya pada program, untuk mempercepat pemrosesan kandidat jalur. DAFTAR PUSTAKA [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd ed., The MIT Press, 2001. [2] E. d. Q. V. Martins and M. M. B. Pascoal, "A New Implementation of Yen's Ranking Loopless Paths Algorithm," 40R: A Quartery Journal of Operations Research, vol. 1, no. 2, pp. 121-133, 2003. [3] D. Eppstein, "Finding the k Shortest Paths," SIAM Journal on Computing, vol. 5, pp. 83-89, 1998. [4] E. d. Q. V. Martins, M. M. B. Pascoal and J. L. E. Santos, "Deviation Algorithms for Ranking Shortest Paths," International Journal of Foundations of Computer Science, vol. 10, no. 3, pp. 247-261, 1999. [5] J. Y. Yen, "Finding the K Shortest Loopless Paths in a Network," Management Science, vol. 17, no. 11, pp. 712-716, 1971. [6] Sphere Research Labs, "SPOJ - Problem MKTHPATH," 2013. [Online]. Available: http://www.spoj.com/problems/MKTHPATH/.

5

Implementasi Algoritma Pencarian k Jalur Sederhana Terpendek dalam Graf

Recommend Documents