PENDAHULUAN Latar Belakang Salah satu masalah arus dalam suatu network adalah penentuan path terpendek. Masalah path terpendek ini merupakan masalah pengoptimuman, karena dengan diperolehnya path terpendek diharapkan dapat mengoptimumkan faktor yang lain (misalkan: waktu dan biaya). Secara umum, masalah path terpendek dalam suatu network ini terbagi menjadi 3 tipe, yakni: (1) path terpendek antara suatu simpul dan simpul lainnya, (2) path terpendek antara suatu simpul dengan semua simpul lainnya, dan (3) path terpendek antara semua pasang simpul yang terdapat pada network tersebut. Pada karya ilmiah ini, yang menjadi masalah utama adalah masalah tipe (1), yaitu mencari path terpendek antara suatu simpul, yaitu source dan suatu simpul lainnya, yaitu sink. Terdapat beberapa algoritme yang dapat digunakan untuk mencari path terpendek, salah satunya adalah algoritme dekomposisi. Algoritme dekomposisi dibahas di dalam [Hu, 1981], [Yen, 1968], dan [Shier et al., 1973].
Namun, tiap prosedur yang diperkenalkan memiliki keuntungan yang berbeda. Prosedur yang diperkenalkan oleh Hu akan tepat bila diaplikasikan pada network yang memiliki struktur linear. Prosedur yang diperkenalkan oleh Shier akan tepat bila diaplikasikan pada network dengan struktur tree. Ada pula prosedur yang akan tepat bila diaplikasikan pada network berbentuk star, yaitu algoritme dekomposisi yang diperkenalkan oleh Land dan Stairs [Land & Stairs, 1967]. Dalam karya ilmiah yang merupakan rekonstruksi dari tulisan Jarvis dan Tufekci [Jarvis & Tufekci, 1982] ini, algoritme yang banyak diterapkan adalah algoritme dekomposisi yang diperkenalkan oleh Hu [Hu, 1981]. Dalam karya ilmiah ini juga dilakukan penghitungan kompleksitas dari algoritme dekomposisi yang digunakan.
Tujuan Tujuan penulisan karya ilmiah ini adalah mempelajari penyelesaian masalah path terpendek antara simpul source (s) dan sink (t) dalam sebuah network dengan menggunakan Algoritme Dekomposisi Jarvis-Tufekci.
LANDASAN TEORI
Dalam mencari path terpendek antara source (s) dan sink (t) dalam sebuah network dengan algoritme dekomposisi, diperlukan beberapa konsep sebagai berikut:
Graf Definisi 1 (Graf) Suatu graf adalah pasangan terurut (V,E) dengan V adalah himpunan berhingga dan takkosong dari elemen-elemen graf, yang disebut simpul (node, verteks), dan E adalah himpunan pasangan takterurut dari simpulsimpul di V. Setiap {p,q}∈E (dengan p,q∈V) dan dikatakan disebut sisi (edge)
menghubungkan simpul p dan simpul q. Sisi {p,q} dapat pula dituliskan dengan pq. (Foulds, 1992) Ilustrasi: G: v1
e1
v2
e3
e2 v3
e4 e5
v4
Gambar 1. Graf dengan 4 simpul dan 5 sisi.
Graf G pada Gambar 1 mempunyai himpunan simpul V={v1, v2, v3, v4} dan himpunan sisi E={e1, e2, e3, e4, e5}.
Ilustrasi: G:
Definisi 2 (Incident) Misalkan diberikan graf G=(V,E). Jika sisi e={p,q}∈E, maka simpul p dan q masingmasing dikatakan incident dengan sisi e. Dapat pula dikatakan bahwa sisi e incident dengan simpul p dan q. (Foulds, 1992)
3
5
2
4
6
Gambar 3. Graf dengan 2 komponen. Graf G pada Gambar 3 memiliki 2 buah komponen, yaitu komponen yang mengandung himpunan simpul {1,2,3,4} dan yang mengandung himpunan simpul {5,6}.
Ilustrasi: Berdasarkan graf pada Gambar 1, maka e1 incident dengan simpul v1 dan v2, e2 incident dengan simpul v1 dan v3, e3 incident dengan simpul v2 dan v3, dan seterusnya.
Definisi 5 (Digraf) Suatu graf berarah/digraf (directed graph) D adalah pasangan terurut (V,A) dengan V adalah himpunan takkosong dan hingga, dan A adalah himpunan pasangan terurut elemenelemen di V. Elemen dari A biasa disebut sisi berarah (arc).
Definisi 3 (Subgraf) Suatu graf G’=(V’,E’) adalah suatu subgraf dari G=(V,E) jika V’⊆ V dan E’⊆ E.
Jika (u,v) (seringkali dituliskan dengan uv) adalah suatu sisi berarah pada digraf, maka u dikatakan predecessor dari v, dan v adalah suatu successor dari u. (Foulds, 1992)
(Ahuja et al., 1993) Ilustrasi:
G:
1
1
6
Ilustrasi: D:
2 5
3
2
4
3
5
1
4
Gambar 4. Digraf.
G’: 6
Untuk digraf pada Gambar 4, V={1,2,3,4,5} dan A={(1,2), (1,3), (2,3), (2,4), (2,5), (3,5), (4,5)}.
1 2
5
Pada sisi berarah (1,2), maka simpul 1 adalah predecessor bagi simpul 2, dan simpul 2 adalah successor bagi simpul 1. Hal yang sama berlaku bagi sisi berarah lainnya.
3
Gambar 2. G’ subgraf dari G.
Definisi 4 (Komponen) Suatu subgraf maksimum yang terhubungkan dari graf G disebut komponen dari G. (Foulds, 1992)
Definisi 6 (Walk) Suatu walk pada suatu digraf D=(V,A) adalah suatu subgraf dari D=(V,A) yang berupa suatu barisan dari simpul dan sisi berarah i1−a1−i2− a2−…−ir−1−ar−1−ir dan untuk semua 1≤ k ≤ r−1 berlaku ak=(ik , ik+1)∈A atau dapat ditulis ak=(ik+1, ik) ∈A.
2
Dapat pula dikatakan bahwa walk adalah suatu himpunan (barisan) dari sisi berarah atau simpul-simpul.
Definisi 8 (Subpath) Suatu subpath dari path v0−v1−v2−.....−vk adalah barisan simpul vi−vi+1−......−vj yang terdapat dalam path tersebut sedemikian sehingga 0 ≤ i ≤ j ≤ k. (Cormen et al., 1990)
Walk dapat dibedakan menjadi 2, yakni: a) Walk berarah yaitu suatu walk yang memiliki satu arah, sehingga untuk sembarang 2 buah simpul ik dan ik+1 yang berurutan pada walk tersebut, (ik , ik+1)∈A. b) Walk tidak berarah yaitu suatu walk yang tidak memenuhi definisi walk berarah. (Ahuja et al., 1993)
Ilustrasi: Dengan menggunakan path pada Gambar 6 dapat diperoleh contoh subpath, yakni: 2
Ilustrasi:
1 2
3
5
Gambar 7. Contoh subpath.
1 3
4 Definisi 9 (Cycle) Suatu cycle adalah suatu path i1−i2−...−ir dan mengandung (i1, ir) atau (ir,i1), atau dapat dituliskan sebagai i1−i2−...−ir−i1. Suatu cycle dapat pula didefinisikan sebagai path yang tertutup.
Gambar 5(a). Walk 1−2−3−4−5 adalah contoh walk berarah. 2
5
1 3
Berdasarkan definisi path, maka cycle dapat dibedakan menjadi 2, yakni: 1) Cycle berarah yaitu path berarah i1−i2−...−ir dan mengandung sisi berarah (ir,i1). 2) Cycle tidak berarah yaitu path tidak berarah i1−i2−...−ir dan mengandung sisi berarah (ir,i1). (Ahuja et al., 1993)
4
Gambar 5(b). Walk 1−2−3−4−5 adalah contoh walk tidak berarah.
Definisi 7 (Path) Suatu path dalam suatu digraf adalah suatu walk dengan semua simpulnya berbeda (tidak ada yang berulang).
Ilustrasi: 1
Berdasarkan definisi walk, maka path dapat pula dibedakan menjadi 2, yakni path berarah dan path tidak berarah. (Ahuja et al., 1993)
2
3
Gambar 8(a). Cycle 1−2−3−1 adalah cycle berarah.
Ilustrasi: 2 1
1 3
5
Gambar 6. Path.
2
Path 1−2−3−5 pada Gambar 6 merupakan contoh path yang dimiliki oleh digraf pada Gambar 4. Path ini merupakan contoh path berarah.
3
Gambar 8(b) Cycle 1−2−3−1 adalah cycle tidak berarah.
3
didefinisikan pula bahwa d(u,u)=0, dan d(u,v)=∞ (takhingga) jika tidak ada sisi berarah yang menghubungkan simpul u dan v tersebut. (Cormen et al., 1990)
Definisi 10 (Digraf Terhubungkan) Suatu digraf D=(V,A) dikatakan terhubungkan (connected), jika terdapat paling sedikit satu buah path yang menghubungkan setiap pasang simpul pada digraf tersebut. Jika tidak, maka digraf tersebut dikatakan takterhubung. (Foulds, 1992)
Ilustrasi: Bardasarkan digraf terboboti pada Gambar 10, maka dapat diperoleh: d(1,1)=0 d(2,3)=1 d(1,2)=1 d(2,4)=5 d(1,3)=3 d(3,3)=0 d(1,4)=∞ d(3,4)=1 d(2,2)=0 d(4,4)=0.
Ilustrasi: 1
2
4
3
5
Gambar 9(a). Digraf terhubung. 1
2
4
3
5
Definisi 13 (Panjang path) Misalkan diberikan path p, v0−v1−v2−.....−vk. Panjang path p adalah jumlah semua panjang sisi berarah yang terdapat pada path tersebut, atau dapat dituliskan sebagai: k
d ( p ) = d (v 0 , v k ) = ∑ d (v i −1 , v i ) .
Gambar 9(b). Digraf takterhubung.
i =1
(Cormen et al., 1990) Ilustrasi: Pada Gambar 10, terdapat beberapa path. Berikut ini panjang path-path yang menghubungkan simpul 1 dan simpul 4 pada digraf pada Gambar 10 tersebut: Panjang path 1−2−4 =d(1,4) =d(1,2)+d(2,4) =1+5 =6 Panjang path 1−3−4 =d(1,4) =d(1,3)+d(3,4) =3+1 =4 Panjang path 1−2−3−4 =d(1,4) =d(1,2)+d(2,3)+d(3,4) =1+1+1 =3.
Definisi 11 (Graf terboboti) Suatu graf G=(V,E) atau digraf D=(V,A) dikatakan terboboti jika terdapat fungsi d:E→R atau d:A→R (dengan R adalah himpunan bilangan real) yang memetakan setiap bilangan real (yang disebut bobot) untuk setiap sisi di E (atau A). Setiap bobot d(uv) dengan uv ∈ E (atau uv ∈ A) biasa dituliskan dengan duv. (Foulds, 1992) Ilustrasi: 2 1 1
5 1
3
4 1 3
Definisi 14 (Path terpendek) Path u−v dikatakan sebagai path terpendek jika path yang menghubungkan simpul u dan simpul v tersebut memiliki panjang minimum di antara path-path u−v lainnya. (Hu, 1981)
Gambar 10. Digraf terboboti.
Definisi 12 (Panjang sisi berarah) Misalkan diberikan suatu digraf terboboti dengan fungsi yang memetakan tiap sisi berarah dengan suatu bilangan real. Maka, bobot ini dapat pula dikatakan sebagai panjang sisi berarah. Panjang sisi berarah yang menghubungkan simpul u dengan v duv=d(u,v), dan dinotasikan dengan
Ilustrasi: Berdasarkan digraf terboboti pada Gambar 10, dan panjang path-path yang menghubungkan simpul 1 dan 4 pada Ilustrasi Definisi 13, maka dapat ditentukan path terpendek yang menghubungkan simpul 1 dan 4 adalah path
4
Berdasarkan Gambar 11, cycle 2−4−3−2 merupakan cycle negatif karena memiliki panjang cycle: d(c) = d(2,4) + d(4,3) + d(3,2) = (−11) + 2 +8 = −1 < 0. Sedangkan cycle 1−3−2−1 merupakan cycle taknegatif (dapat pula dikatakan positif), karena memiliki panjang cycle: d(c) = d(1,3) + d(3,2) + d(2,1) = 5 + 8 + (−10) = 3 ≥ 0.
1−2−3−4, karena memiliki panjang minimum di antara path-path 1−4 lainnya, yaitu 3. Dalam karya ilmiah ini, definisi “panjang” dapat pula diartikan sebagai “jarak”.
Definisi 15 (Matriks jarak) Misalkan D=(V,A) adalah suatu digraf dengan V = {v1 , v 2 ,...., v n } dan A = {a1 , a 2 ,...., a m } . Matriks jarak M didefinisikan dengan M=(mij) dengan mij=d(vi,vj). (Chartrand & Oellermann, 1993) Ilustrasi: Dengan menggunakan digraf terboboti pada Gambar 10, maka dapat diperoleh matriks jarak dari digraf tersebut, yakni sebagai berikut:
Network Definisi 17 Kasus khusus digraf terboboti adalah network (jaringan kerja). Beberapa konsep pada network adalah sebagai berikut: 1. Jika a = (vi,vj) adalah suatu sisi berarah pada digraf D=(V,A), maka a dikatakan sebagai sisi berarah yang menjauhi vi dan mendekati vj. 2. Suatu simpul sehingga tidak ada sisi berarah yang mendekati dirinya disebut dengan sumber (source), sedangkan suatu simpul sehingga tidak ada sisi berarah yang menjauhi dirinya disebut dengan sink 3. Suatu network adalah suatu digraf yang mempunyai tepat satu source dan tepat satu sink.
1⎡ 0 1 3 +∞ ⎤ ⎢ 2 +∞ 0 1 5 ⎥⎥ . M= ⎢ 3 ⎢ +∞ +∞ 0 1 ⎥ ⎢ ⎥ 4 ⎣ +∞ +∞ +∞ 0 ⎦ Definisi 16 (Panjang cycle) Misalkan diberikan suatu cycle berarah c, yaitu v0−v1−v2−.....−vk dengan v0 = vk. Panjang cycle berarah c adalah jumlah panjang seluruh sisi berarah yang terdapat pada cycle tersebut, atau dapat dituliskan sebagai: k
d (c) = ∑ [d (vi −1 , vi ) − d (vi , vi −1 )] .
Pada banyak aplikasi network, paling sedikit terdapat satu aliran/flow yang bergerak dari source ke sink. Flow pada network merupakan bobot pada digraf. (Foulds, 1992)
i =1
Panjang cycle dapat dibedakan sebagai berikut: • Panjang cycle dikatakan negatif jika d(c)< 0 • Panjang cycle dikatakan taknegatif jika d(c) ≥ 0 • Panjang cycle dikatakan positif jika d(c) >0. (Ahuja et al., 1993)
Ilustrasi: 1 3
5
1 8
−10
2
5
3
3
t 2
Gambar 12. Network.
2 −11
2
2
3
s
Ilustrasi:
2
1
4 Definisi 18 (Kerapatan network) Kerapatan suatu network adalah perbandingan banyaknya sisi berarah sebenarnya pada network dengan banyaknya sisi berarah
Gambar 11. Digraf yang mengandung cycle.
5
maksimum yang mungkin terdapat pada network tersebut.
Ilustrasi: N:
s
Jika suatu network N = (V,A) terdiri atas n buah simpul dan n(n−1) buah sisi berarah, maka network seperti itu dikatakan memiliki kerapatan sebesar 100%. Namun, jika suatu network memiliki nilai kerapatan yang lebih kecil dari 0,20 maka network tersebut dikatakan longgar. (Jarvis & Tufekci, 1982)
2
3
4
5
Ilustrasi: N:
6
7
a1
s
a2 a3
1
4
a6
X
8 2
t
3
a5
1
a4
Gambar 14(a). Network dengan cut set.
t 5
a7
s
Gambar 13. Contoh network yang longgar. 1
Network N pada Gambar 13 memiliki n=7 buah simpul yaitu {s,1,2,3,4,5,t}, dan 7 buah sisi berarah yaitu {a1,a2,a3,a4,a5,a6,a7). Banyaknya sisi berarah maksimum yang mungkin terdapat pada network tersebut adalah n(n−1)=7(7−1) =42 buah sisi berarah. Maka, kerapatan network tersebut adalah 7 = 0,17 . Nilai kerapatan yang kurang dari 42 0,20 tersebut menunjukkan bahwa network tersebut merupakan network yang longgar.
8
t Gambar 14(b). Network takterhubung setelah cut set dihilangkan. Pada network N pada Gambar 14(a), himpunan simpul X ={2,3,4,5,6,7} merupakan cut set dari himpunan simpul {s,1}, atau cut set dari himpunan simpul {8,t}. Sedangkan Gambar 14(b) menunjukkan network tersebut menjadi takterhubung, jika himpunan simpul yang merupakan cut set tersebut dihilangkan.
Definisi 19 (Cut set) Misalkan diberikan suatu network terhubung N=(V,A) dan misalkan B dan X merupakan himpunan bagian dari V dengan X ≠ B. Himpunan X dikatakan sebagai cut set dari B jika memenuhi kondisi-kondisi berikut: (a) Jika X dan semua sisi berarah yang incident dengan X dihilangkan, maka network N=(V,A) tersebut menjadi takterhubung, (b) Semua simpul pada B berada pada satu komponen yang sama dan tidak terdapat simpul lain yang bukan anggota B pada komponen ini. (Hu & Torres, 1969)
Definisi 20 (Minimal cut set) Misalkan X adalah cut set dari N. Maka, X dikatakan sebagai minimal cut set jika tidak terdapat himpunan bagian sejati dari X yang juga merupakan cut set. (Hu & Torres, 1969)
6
di k ← min {dik , dij + djk} = min {6,3+2} = min {6,5} =5 ∴ di k ← 5.
Ilustrasi:
s 1 2
3
4
5
Secara umum, operasi tripel dapat digunakan untuk lebih dari 3 simpul.
X1
Ilustrasi: 1 6
7
X2
1 2
8
2
1 4
4
5 3
Untuk menentukan jarak terpendek antara simpul 1 dan simpul 5, maka dilakukan operasi tripel sebagai berikut: • d15 ← min {d15, d12 + d25} • d15 ← min {d15, d13 + d35} • d25 ← min {d25, d24 + d45} = min {+∞, 4 + 3} = min {+∞, 7} =7 • d35 ← min {d35, d34 + d45} = min {2, 1 + 3} = min {2, 4} =2 • d15 ← min {d15, d13 + d35} = min {+∞, 3 + 2} = min {+∞, 5} =5 • d15 ← min {d15, d12 + d25} = min {5, 1 + 7} = min {5, 8} = 5.
Gambar 15. Contoh minimal cut set pada suatu network. Berdasarkan Gambar 15, terlihat bahwa X1={2,3} dan X2={6,7} adalah minimal cut set pada network tersebut. Berbeda halnya dengan cut set pada Gambar 14(a) yang tidak dapat dikatakan sebagai minimal cut set karena masih memiliki himpunan bagian sejati yang juga merupakan cut set.
Definisi 21 (Operasi tripel) Misalkan dij menyatakan panjang/jarak antara simpul i dan simpul j pada digraf D. Maka, didefinisikan operasi tripel sebagai berikut: dik ← min {dik, dij + djk} untuk i ≠ j ≠ k dengan lambang “←” menyatakan “digantikan oleh”. (Hu, 1981)
∴ d15 ← 5. Definisi 22 (Network terdekomposisi) Misalkan Xi adalah himpunan simpul dan diketahui Xi ≠ ∅, untuk setiap i. Suatu network N=(V,A) dikatakan terdekomposisi menjadi m buah subnetwork N 1 , N 2 , N 3 ,..... , N m yang bertindih secara linear (linearly overlapping) jika memenuhi kondisi-kondisi berikut: ; i≠ j (1) X i I X j = Ø
Ilustrasi:
j 2
i 6
3
Gambar 17. Contoh path dengan 5 simpul
t
3
3
k
Gambar 16. Contoh path dengan 3 simpul.
m
Untuk menentukan jarak terpendek antara simpul i dan k pada Gambar 16, maka dilakukan operasi tripel, yakni:
(2) U N i = N i =1
7
⎧ X i −1 ; j =i −1 ⎪ (3) N i I N j = ⎨ X i ; j =i +1 ⎪ Ø ⎩ ; j ≠ (i −1),i,(i +1). (Jarvis & Tufekci, 1982)
N1
N2
X1
Nm
N3
X2
..............
X3
Xm−1
Gambar 18. Ilustrasi m buah subnetwork yang bertindih secara linear (linearly overlapping).
subnetwork yang bertindih secara linear (linearly overlapping).
Berikut ini merupakan ilustrasi sebuah network yang terdekomposisi menjadi 3 buah
Ilustrasi: N:
1
3
5
7
2
4
6
t
X1
X2
s
Gambar 19. Contoh network dengan 3 buah subnetwork.
Network pada Gambar 19, terdekomposisi menjadi 3 buah subnetwork N 1 , N 2 , N 3
Ilustrasi: Misalkan diberikan suatu network N=(V,A) yang terdekomposisi menjadi 2 buah subnetwork sebagai berikut:
dengan himpunan simpul di N 1 = {s,1,2,3,4}, N 2 = {3,4,5,6}, dan N 3 = {5,6,7,8}, dengan X1 = {3,4} dan X2 = {5,6}.
N:
Definisi 23 (Persamaan minisumasi) Misalkan diberikan suatu network N=(V,A) yang terdekomposisi menjadi 2 buah subnetwork N 1 dan N 2 , maka N=N1∪X∪N2 dengan X adalah cut set pada network N. Misalkan pula d uv* menyatakan jarak
2
1 2
s 3
1
2
4
3 3
1
t 5
4
X
terpendek antara simpul u dan simpul v.
Gambar 20. Network yang telah terdekomposisi.
Persamaan minisumasi didefinisikan sebagai berikut: min * d ik* = {d ij + d *jk } j dengan i∈N1, j∈X, dan k∈N2. (Hu & Torres, 1969)
Network N pada Gambar 20 mempunyai 2 buah subnetwork dengan N1={s,1}, X={2,3}, dan N2={4,t}.
8
membutuhkan waktu cnm untuk beberapa konstanta c. Pernyataan ini ekuivalen dengan pernyataan bahwa algoritme tersebut membutuhkan waktu O(nm). Secara formal dapat didefinisikan sebagai berikut: “Suatu algoritme dikatakan bekerja dalam waktu O(f(n)) jika untuk beberapa bilangan c dan no, maka waktu yang diperlukan oleh algoritme tersebut paling banyak adalah cf(n) untuk semua n ≥ no”. (Ahuja et al., 1993)
Untuk mengetahui jarak terpendek dari N1 ke N2 dapat ditentukan dengan menggunakan persamaan minisumasi berikut: * * d s*4 = min[( d s*2 + d 24 ), ( d s*3 + d 34 )] = min [(7 + 7), (3 + 1)] = min [14, 4] =4 d st* = min[( d s*2 + d 2*t ), ( d s*3 + d 3*t )] = min [(7 + 1), (3 + 5)] = min [8, 8] =8 * * ), (d 13* + d 34 )] d 14* = min[( d 12* + d 24 = min [(6 + 7), (2 + 1)] = min [13, 3] =3 d 1*t = min[( d 12* + d 2*t ), (d 13* + d 3*t )] = min [(6 + 1), (2 + 5)] = min [7, 7] = 7.
Algoritme Dekomposisi Hu
Hu adalah salah seorang tokoh yang memperkenalkan algoritme dekomposisi. Dalam karya ilmiah ini algoritme dekomposisi yang diperkenalkan oleh Hu berperan dalam penyelesaian masalah path terpendek pada suatu network yang diberikan. Misalkan diberikan suatu network N=(V,A) yang longgar dan memiliki banyak simpul yang cukup besar (berskala besar). Untuk menyelesaikan masalah path terpendek dalam network tersebut, Hu menggunakan algoritme dekomposisi. Langkah pertama pada algoritme dekomposisi Hu ini adalah mendekomposisi network N=(V,A) yang diberikan menjadi m buah subnetwork N 1 , N 2 , N 3 ,..... , N m yang bertindih secara linear (linearly overlapping).
Kompleksitas Algoritme Definisi 24 (Algoritme) Algoritme adalah suatu tahapan/prosedur untuk menyelesaikan suatu masalah.
Langkah-langkah dari suatu algoritme dibedakan sebagai berikut: 1) Langkah penetapan. Contoh: menetapkan beberapa nilai untuk suatu variabel. 2) Langkah aritmatika/penghitungan. Contoh: penjumlahan, pengurangan, perkalian, dan pembagian. 3) Langkah logika. Contoh: membandingkan 2 buah bilangan. (Ahuja et al., 1993)
Tahapan yang perlu dilakukan dalam mendekomposisi network N=(V,A) tersebut adalah: 1) Suatu himpunan simpul yang merupakan himpunan bagian dari V ditandai sebagai N1. 2) Menentukan himpunan simpul yang merupakan minimal cut set dari N1. 3) Menandai himpunan simpul berikutnya yang merupakan cut set (tidak harus merupakan minimal cut set) dari (N1∪X1) sebagai N2. 4) Menentukan himpunan simpul yang merupakan minimal cut set dari (N1∪X1∪N2) sebagai X2. 5) Hal yang sama dilakukan hingga network tersebut terdekomposisi seluruhnya menjadi m buah subnetwork N 1 , N 2 , N 3 ,..... , N m dengan N 1 = N1 U X 1 ,
Definisi 25 (Kompleksitas Algoritme) Fungsi kompleksitas waktu untuk suatu algoritme adalah fungsi dari ukuran masalah dan waktu yang diperlukan oleh algoritme tersebut untuk menyelesaikan masalah yang diberikan. Untuk selanjutnya, fungsi kompleksitas waktu ini disebut dengan kompleksitas algoritme. (Ahuja et al., 1993)
Definisi 26 ( Notasi “big O”) Notasi “big O” adalah suatu ekspresi yang menyatakan bahwa suatu algoritme
N 2 = X1 U N 2 U X 2 , N 3 = X 2 U N 3 U X 3 , seterusnya hingga
9
dilakukan hingga operasi tripel diaplikasikan pada subnetwork N m . Pada akhir tahap (1) ini diperoleh: M N* N ( N 1 ) , M * ( N 1 U N 2 ) , .......,
N m −1 = X m − 2 U N m −1 U X m −1 ,dan N m = X m−1 U N m . Jadi, N=N1∪X1∪N2∪....∪Xm−1∪Nm.
1
i
dari Ni ke Nj, sedangkan M ( N k ) menyatakan matriks jarak terpendek dari Ni ke Nj yang terletak pada N k . Tahapan yang dilakukan dalam algoritme dekomposisi Hu adalah sebagai berikut: (1) Operasi tripel diaplikasikan pada m buah subnetwork N 1 , N 2 , N 3 ,..... , N m −1 , N m secara bertahap. Jarak terpendek yang subnetwork diperoleh dari suatu menggantikan jarak aslinya pada subnetwork berikutnya (yang akan dikenai operasi tripel), misalkan: yang diperoleh akan M X* X ( N 1 )
m −1 m −1
M X* m −1X m−1 ( N − N m ) . Pada akhir tahap (2)
ini dapat diperoleh: M N* N ( N ) ,......, m −1 m −1 M N* 2 N 2 ( N ) , M N* 1 N 1 ( N ) .
(3) Jarak terpendek antara pasangan simpul yang tidak terdapat pada subnetwork yang sama ditentukan dengan menggunakan persamaan minisumasi. (Hu & Torres, 1969)
1 1
jarak
M X1 X1
N2 N2
(2) Operasi tripel diaplikasikan pada m−1 buah subnetwork N m −1 , N m − 2 ....., N 2 , N 1 secara bertahap. Jarak yang diperoleh pada suatu subnetwork menggantikan jarak pada subnetwork selanjutnya (yang akan dikenai opersi tripel), misalkan: M *X X ( N ) akan menggantikan jarak
j
* ij
menggantikan
1
M N* m−1 N m−1 ( N 1 U N 2 U .... U N m −1 ) , M N* m N m ( N ) .
Misalkan didefinisikan N i = N i − ( X i −1 U X i ) , dan misalkan M N N menyatakan matriks jarak
sebelum
operasi tripel dilakukan pada subnetwork N 2 =N1∪X1∪N2. Hal yang sama
PEMBAHASAN
Berikut ini adalah prosedur yang digunakan dalam algoritme dekomposisi Jarvis-Tufekci dalam menyelesaikan masalah path terpendek pada suatu network.
Dekomposisi Network
Dalam bab ini akan diberikan beberapa asumsi yang diperlukan dan prosedur yang digunakan dalam algoritme dekomposisi Jarvis-Tufekci untuk dapat menyelesaikan masalah path terpendek antara source (s) dan sink (t) pada suatu network. Selain itu, akan diberikan pula contoh penerapan algoritme dekomposisi tersebut dalam suatu network yang diberikan. Pada akhirnya akan diuraikan penghitungan kompleksitas dari algoritme dekomposisi ini.
Misalkan diberikan suatu network berskala besar yang longgar N=(V,A) dengan V={v1,v2,....,vn} dan A adalah himpunan sisi berarah yang terdapat pada network tersebut, dengan tiap sisi berarah yang menghubungkan simpul vi dan simpul vj memiliki panjang yang dinotasikan dengan dij=d(vi,vj). Misalkan network N=(V,A) yang diberikan terdekomposisi menjadi m buah subnetwork N 1 , N 2 , N 3 ,..... , N m yang bertindih secara linear (linearly overlapping). Tahapan yang dilakukan dalam mendekomposisi network N yang diberikan tersebut tidak berbeda dengan tahapan yang dilakukan oleh algoritme Hu, sehingga pada akhir tahap diperoleh N=N1∪X1∪N2∪....∪Xm−1∪Nm yang dapat pula diilustrasikan sebagai berikut:
Penentuan path terpendek antara simpul source dan sink pada suatu network berskala besar dengan menggunakan algoritme dekomposisi Jarvis-Tufekci memerlukan beberapa asumsi berikut: 1) Network yang akan didekomposisi merupakan network yang longgar/tidak rapat. 2) Network tersebut tidak memuat cycle yang negatif.
10
